nach oben

Distributed Computing

Erschienen in:

04.09.2019

A complexity-based classification for multiprocessor synchronization

verfasst von: Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu

Erschienen in: Distributed Computing | Ausgabe 2/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

For many years, Herlihy’s elegant computability-based Consensus Hierarchy has been our best explanation of the relative power of various objects. Since real multiprocessors allow the different instructions they support to be applied to any memory location, it makes sense to consider combining the instructions supported by different objects, rather than considering collections of different objects. Surprisingly, this causes Herlihy’s computability-based hierarchy to collapse. In this paper, we suggest an alternative: a complexity-based classification of the relative power of sets of multiprocessor synchronization instructions, captured by the minimum number of memory locations of unbounded size that are needed to solve obstruction-free consensus when using different sets of instructions.

Vorheriger Artikel The computational structure of progress conditions and shared objects

Nächster Artikel Fast distributed approximation for TAP and 2-edge-connectivity

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

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

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"

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

Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873–890 (1993)CrossRef

Aspnes, J., Attiya, H., Censor-Hillel, K.: Polylogarithmic concurrent data structures from monotone circuits. J. ACM 59(1), 2:1–2:24 (2012)

Aspnes, J., Ellen, F.: Tight bounds for adopt-commit objects. Theory Comput. Syst. 55(3), 451–474 (2014)MathSciNetCrossRef

Aspnes, J., Herlihy, M.: Fast randomized consensus using shared memory. J. Algorithms 11(3), 441–461 (1990)MathSciNetCrossRef

Attiya, H., Welch, J.L.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd edn. Wiley, Hoboken (2004)CrossRef

Bouzid, Z., Raynal, M., Sutra, P.: Anonymous obstruction-free \((n, k)\)-set agreement with \(n-k+1\) atomic read/write registers. Distrib. Comput. 31(2), 99–117 (2018)MathSciNetCrossRef

Bowman, J.R.: Obstruction-free snapshot, obstruction-free consensus, and fetch-and-add modulo k. Technical report TR2011-681, Computer Science Department, Dartmouth College (2011). http://www.cs.dartmouth.edu/reports/TR2011-681.pdf

David, M.: Wait-free linearizable queue implementations. Master’s thesis, University of Toronto (2004)

David, M., Brodsky, A., Fich, F.E.: Restricted stack implementations. In: Proceedings of the 19th International Conference on Distributed Computing, (DISC), pp. 137–151 (2005)

10.

Ellen, F., Gelashvili, R., Shavit, N., Zhu, L.: A complexity-based hierarchy for multiprocessor synchronization:[Extended Abstract]. In: Proceedings of the 35th ACM Symposium on Principles of Distributed Computing, (PODC), pp. 289–298 (2016)

11.

Ellen, F., Gelashvili, R., Zhu, L.: Revisionist simulations: a new approach to proving space lower bounds. In: Proceedings of the 37th ACM Symposium on Principles of Distributed Computing, (PODC), pp. 61–70, (2018)

12.

Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. J. ACM 45(5), 843–862 (1998)MathSciNetCrossRef

13.

Fich, F.E., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free algorithms can be practically wait-free. In: Proceedings of the 19th International Conference on Distributed Computing, (DISC), pp. 78–92, (2005)

14.

Gelashvili, R.: On the optimal space complexity of consensus for anonymous processes. Distrib. Comput. 31(4), 317–326 (2018)MathSciNetCrossRef

15.

Gelashvili, R., Keidar, I., Spiegelman, A., Wattenhofer, R.: Brief announcement: Towards reduced instruction sets for synchronization. In: Proceedings of the 31st International Conference on Distributed Computing, (DISC), pp. 53:1–53:4 (2017)

16.

Giakkoupis, G., Helmi, M., Higham, L., Woelfel, P.: An \(\cal{O}(\sqrt{n})\) space bound for obstruction-free leader election. In: Proceedings of the 27th International Symposium on Distributed Computing, (DISC), pp. 46–60 (2013)

17.

Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3), 165–177 (2007)CrossRef

18.

Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. (TOPLAS) 13(1), 124–149 (1991)CrossRef

19.

Herlihy, M., Ruppert, E.: On the existence of booster types. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pp. 653–663, (2000)

20.

Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Elsevier, Amsterdam (2012)

21.

Intel: Transactional Synchronization in Haswell, (2012). http://software.intel.com/en-us/blogs/2012/02/07/transactional-synchronization-in-haswell

22.

Jayanti, P.: Robust wait-free hierarchies. J. ACM 44(4), 592–614 (1997)

23.

Jayanti, P., Tan, K., Toueg, S.: Time and space lower bounds for nonblocking implementations. SIAM J. Comput. 30(2), 438–456 (2000)MathSciNetCrossRef

24.

Khanchandani, P., Wattenhofer, R.: On the importance of synchronization primitives with low consensus numbers. In: Proceedings of the 19th International Conference on Distributed Computing and Networking, (ICDCN), pp. 18:1–18:10, (2018)

25.

Lo, W.-K., Hadzilacos, V.: All of us are smarter than any of us: nondeterministic wait-free hierarchies are not robust. SIAM J. Comput. 30(3), 689–728 (2000)MathSciNetCrossRef

26.

Perrin, M.: Spécification des objets partagés dans le systèmes répartis sans attente (specification of shared objects in wait-free distributed systems). Ph.D. thesis, University of Nantes, France (2016)

27.

Perrin, M., Mostéfaoui, A., Jard, C.: Causal consistency: beyond memory. In: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, (PPOPP), pp. 26:1–26:12, (2016)

28.

Raynal, M.: Concurrent Programming: Algorithms, Principles, and Foundations. Springer, Berlin (2012)MATH

29.

Ruppert, E.: Determining consensus numbers. SIAM J. Comput. 30(4), 1156–1168 (2000)MathSciNetCrossRef

30.

Schenk, E.: The consensus hierarchy is not robust. In: Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, (PODC), pp. 279, (1997)

31.

Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson Education, London (2006)

32.

Zhu, L.: Brief announcement: tight space bounds for memoryless anonymous consensus. In: Proceedings of the 29th International Conference on Distributed Computing, (DISC), pp. 665, (2015)

33.

Zhu, L.: A tight space bound for consensus. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing, (STOC), pp. 345–350, (2016)

Titel: A complexity-based classification for multiprocessor synchronization
verfasst von: Faith Ellen
Rati Gelashvili
Nir Shavit
Leqi Zhu
Publikationsdatum: 04.09.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Distributed Computing / Ausgabe 2/2020
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-019-00361-3

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+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2020

The computational structure of progress conditions and shared objects

Fast distributed approximation for TAP and 2-edge-connectivity

Deciding and verifying network properties locally with few output bits

The complexity of leader election in diameter-two networks