nach oben

Computing

Erschienen in:

25.04.2018

Waiting in concurrent algorithms

verfasst von: Gadi Taubenfeld

Erschienen in: Computing | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Between the two extremes, lock-based algorithms, which involve “a lot of waiting”, and wait-free algorithms, which are “free of locking and waiting”, there is an interesting spectrum of different levels of waiting. This unexplored spectrum is formally defined and its properties are investigated. New progress conditions, called k-waiting, for \(k\ge 0\), which are intended to capture the “amount of waiting” of processes in asynchronous concurrent algorithms, are introduced. To illustrate the utility of the new conditions, they are used to derive new lower and upper bounds, and impossibility results for well-known basic problems such as consensus, election, renaming and mutual exclusion. Furthermore, the relation between waiting and fairness is explored.

Vorheriger Artikel The out-of-core KNN awakens: the light side of computation force on large datasets

Nächster Artikel A mechanized refinement proof of the Chase–Lev deque using a proof system

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

In the case of a beginning process, “its operation” means the operation that the process is about to start executing.

A set of processes P is maximal with respect to property \(\phi \), if (1) P satisfies \(\phi \), and (2) there is no set Q, such that \(P \subset Q\) and Q satisfies \(\phi \).

Anderson TE (1990) The performance of spin lock alternatives for shared-memory multiprocessor. IEEE Trans Parallel Distrib Syst 1(1):6–16CrossRef

Attiya H, Bar-Noy A, Dolev D, Koller D, Peleg D, Reischuk R (1990) Renaming in an asynchronous environment. J Assoc Comput Mach 37(3):524–548MathSciNetCrossRefMATH

Bar-Noy A, Dolev D (1989) Shared memory versus message-passing in an asynchronous distributed environment. In: Proceedings of the 8th ACM symposium on principles of distributed computing, pp 307–318

Borowsky E, Gafni E (1993) Generalized FLP impossibility result for \(t\)-resilient asynchronous computations. In: Proceedings of the 25th ACM symposium on theory of computing, pp 91–100

Burns JE, Peterson GL (1989) The ambiguity of choosing. In: Proceedings of the 8th ACM symposium on principles of distributed computing, pp 145–158

Castaneda A, Rajsbaum S, Raynal M (2011) The renaming problem in shared memory systems: an introduction. Comput Sci Rev 5(3):229–251CrossRefMATH

Dijkstra EW (1965) Solution of a problem in concurrent programming control. Commun ACM 8(9):569CrossRef

Dwork C, Herlihy MP, Waarts O (1997) Contention in shared memory algorithms. J ACM 44(6):779–805MathSciNetCrossRefMATH

Fischer MJ, Lynch NA, Paterson MS (1985) Impossibility of distributed consensus with one faulty process. J ACM 32(2):374–382MathSciNetCrossRefMATH

10.

Herlihy M (1991) Impossibility results for asynchronous pram. In: Proceedings of the 3rd annual ACM symposium on parallel algorithms and architectures, pp 327–336

11.

Herlihy M, Shavit N On the nature of progress. In: 15th International conference on principles of distributed systems (OPODIS 2011), LNCS 7109. Springer, pp 313–328

12.

Herlihy MP (1991) Wait-free synchronization. ACM Trans Progr Lang Syst 13(1):124–149CrossRef

13.

Herlihy MP, Luchangco V, Moir M (2003) Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23rd international conference on distributed computing systems, p 522

14.

Herlihy MP, Shavit N (1999) The topological structure of asynchronous computability. J ACM 46(6):858–923MathSciNetCrossRefMATH

15.

Herlihy MP, Wing JM (1990) Linearizability: a correctness condition for concurrent objects. ACM Trans Progr Lang Syst 12(3):463–492CrossRef

16.

Imbs D, Raynal M, Taubenfeld G (2010) On asymmetric progress conditions. In: Proceedings of the 29th ACM symposium on principles of distributed computing, pp 55–64

17.

Lamport L (1974) A new solution of Dijkstra’s concurrent programming problem. Commun ACM 17(8):453–455MathSciNetCrossRefMATH

18.

Loui MC, Abu-Amara H (1987) Memory requirements for agreement among unreliable asynchronous processes. Adv Comput Res 4:163–183MathSciNet

19.

Moran S, Wolfstahl Y (1987) Extended impossibility results for asynchronous complete networks. Inf Process Lett 26(3):145–151MathSciNetCrossRef

20.

Saks M, Zaharoglou F (2000) Wait-free \(k\)-set agreement is impossible: the topology of public knowledge. SIAM J Comput 29:1449–1483MathSciNetCrossRefMATH

21.

Styer E, Peterson GL (1989) Tight bounds for shared memory symmetric mutual exclusion problems. In: Proceedings of the 8th ACM symposium on principles of distributed computing, pp 177–191

22.

Taubenfeld G (2006) Synchronization algorithms and concurrent programming. Pearson/Prentice-Hall, p 423. ISBN 0-131-97259-6

23.

Taubenfeld G (Sept. 2010) The computational structure of progress conditions. In: 24th International symposium on distributed computing (DISC 2010). LNCS 6343 Springer 2010, pp. 221–235

24.

Taubenfeld G (2016) Fair synchronization. J Parallel Distrib Comput 97:1–10 (Also in: LNCS 8205, 2013, 179–193, DISC 2013)

25.

Taubenfeld G (2016) Waiting in concurrent algorithms. In: 4th International conference on networked systems (NETYS, 2016) Marrakech, Morocco. LNCS 9944, 2016, 345–360

26.

Taubenfeld G (2017) A closer look at fault tolerance. Theory Comput Syst (To appear) (Also In: Proceedings of PODC 2012, 261–270)

Titel: Waiting in concurrent algorithms
verfasst von: Gadi Taubenfeld
Publikationsdatum: 25.04.2018
Verlag: Springer Vienna
Erschienen in: Computing / Ausgabe 1/2019
Print ISSN: 0010-485X
Elektronische ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-018-0618-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 1/2019

Special Issue on NETYS’2016

Time-efficient read/write register in crash-prone asynchronous message-passing systems

The out-of-core KNN awakens: the light side of computation force on large datasets

A mechanized refinement proof of the Chase–Lev deque using a proof system