research-article

Public Access

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]

Authors:

Rati Gelashvili,

Leqi ZhuAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 289 - 298

https://doi.org/10.1145/2933057.2933113

Published: 25 July 2016 Publication History

Abstract

For many years, Herlihy's elegant computability based Consensus Hierarchy has been our best explanation of the relative power of various types of multiprocessor synchronization objects when used in deterministic algorithms. However, key to this hierarchy is treating these instructions as distinct objects, an approach that is far from the real-world, where multiprocessor programs apply synchronization instructions to collections of arbitrary memory locations. We were surprised to realize that, when considering instructions applied to memory locations, the computability based hierarchy collapses. This leaves open the question of how to better captures the power of various synchronization instructions.

In this paper, we provide an approach to answering this question. We present a hierarchy of synchronization instructions, classified by their space complexity in solving obstruction-free consensus. Our hierarchy provides a classification of combinations of known instructions that seems to fit with our intuition of how useful some are in practice, while questioning the effectiveness of others. We prove an essentially tight characterization of the power of buffered read and write instructions. Interestingly, we show a similar result for multi-location atomic assignments.

References

[1]

James Aspnes, Hagit Attiya, and Keren Censor. Max registers, counters, and monotone circuits. In Proc. 28th ACM Symposium on Principles of Distributed Computing, pages 36--45, 2009.

Digital Library

[2]

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873--890, 1993.

Digital Library

[3]

James Aspnes and Faith Ellen. Tight bounds for adopt-commit objects. Theory Comput. Syst., 55(3):451--474, 2014.

Digital Library

[4]

James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441--461, 1990.

Digital Library

[5]

Jack R. Bowman. 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.

[6]

Zohir Bouzid, Michel Raynal, and Pierre Sutra. Brief announcement: Anonymous obstruction-free (n;k)-set agreement n - k + 1 atomic read/write registers. In Proc. 29th International Symposium on Distributed Computing (DISC), page 669, 2015.

[7]

Faith Ellen Fich, Maurice Herlihy, and NirShavit. On the space complexity of randomized synchronization. Journal of the ACM, 45(5):843--862, 1998.

Digital Library

[8]

Faith Ellen Fich, Victor Luchangco, Mark Moir, and Nir Shavit. Obstruction-free algorithms can be practically wait-free. In Proc. 19th International Conference on Distributed Computing (DISC), pages 78--92, 2005.

Digital Library

[9]

Rati Gelashvili. On the optimal space complexity of consensus for anonymous processes. In Proc. 29th International Symposium on Distributed Computing (DISC), pages 452--466, 2015.

Digital Library

[10]

George Giakkoupis, Maryam Helmi, Lisa Higham, and Philipp Woelfel. An O(pn) space bound for obstruction-free leader election. In Proc. 27th International Symposium on Distributed Computing (DISC), pages 46--60, 2013.

Digital Library

[11]

Rachid Guerraoui and Eric Ruppert. What can be implemented anonymously? In Proc. 19th International Symposium on Distributed Computing (DISC), pages 244--259, 2005.

Digital Library

[12]

Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124--149, 1991.

Digital Library

[13]

Maurice Herlihy and Eric Ruppert. On the existence of booster types. In Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 653--663, 2000.

Digital Library

[14]

Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2012.

Digital Library

[15]

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

[16]

Prasad Jayanti. On the robustness of herlihy's hierarchy. In Proc. 12th ACM Symposium on Principles of Distributed Computing (PODC), pages 145--157, 1993.

Digital Library

[17]

Wai-Kau Lo and Vassos Hadzilacos. All of us are smarter than any of us: Nondeterministic wait-free hierarchies are not robust. SIAM Journal on Computing, 30(3):689--728, 2000.

Digital Library

[18]

Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. In Proc. 9th Annual European Symposium on Algorithms (ESA), pages 121--133, 2001.

Digital Library

[19]

Michel Raynal. Concurrent programming: algorithms, principles, and foundations. Springer Science & Business Media, 2012.

Digital Library

[20]

Eric Ruppert. Determining consensus numbers. SIAM Journal on Computing, 30(4):1156--1168, 2000.

Digital Library

[21]

Eric Schenk. The consensus hierarchy is not robust. In Proc. 16th ACM Symposium on Principles of Distributed Computing (PODC), page 279, 1997.

Digital Library

[22]

Gadi Taubenfeld. Synchronization algorithms and concurrent programming. Pearson Education, 2006.

Digital Library

[23]

Leqi Zhu. Brief announcement: Tight space bounds for memoryless anonymous consensus. In Proc. 29th International Symposium on Distributed Computing (DISC), page 665, 2015.

[24]

Leqi Zhu. A tight space bound for consensus. In Proc. 48th ACM Symposium on Theory of Computing (STOC), 2016. To appear.

Digital Library

Cited By

Attiya HCastañeda AHendler DPerrin M(2022)Separating Lock-Freedom from Wait-Freedom at Every Level of the Consensus HierarchyJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.01.025Online publication date: Feb-2022
https://doi.org/10.1016/j.jpdc.2022.01.025
Perrin MMostéfaoui ABonin GCourtillat-Piazza L(2022)Extending the wait-free hierarchy to multi-threaded systemsDistributed Computing10.1007/s00446-022-00425-x35:4(375-398)Online publication date: 16-Apr-2022
https://doi.org/10.1007/s00446-022-00425-x
Khanchandani PSchappi JWang YWattenhofer R(2021)On Consensus Number 1 Objects2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00115(875-882)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00115
Show More Cited By

Index Terms

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]
1. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

The space complexity of long-lived and one-shot timestamp implementations
PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing

This paper is concerned with the problem of implementing an unbounded timestamp object from multi-writer atomic registers, in an asynchronous distributed system of n processors with distinct identifiers where timestamps are taken from an arbitrary ...
On the space complexity of randomized synchronization

The “waite-free hierarchy” provides a classification of multiprocessor synchronization primitives based on the values of n for which there are deterministic wait-free implementations of n-process consensus using instances of these objects and read-write ...
Synchronization power depends on the register size
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science

Though it is common practice to treat synchronization primitives for multiprocessors as abstract data types, they are in reality machine instructions on registers. A crucial theoretical question with practical implications is the relationship between the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Natural Sciences and Engineering Research Council of Canada
Department of Energy
National Science Foundation

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
533
Total Downloads

Downloads (Last 12 months)106
Downloads (Last 6 weeks)50

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Attiya HCastañeda AHendler DPerrin M(2022)Separating Lock-Freedom from Wait-Freedom at Every Level of the Consensus HierarchyJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.01.025Online publication date: Feb-2022
https://doi.org/10.1016/j.jpdc.2022.01.025
Perrin MMostéfaoui ABonin GCourtillat-Piazza L(2022)Extending the wait-free hierarchy to multi-threaded systemsDistributed Computing10.1007/s00446-022-00425-x35:4(375-398)Online publication date: 16-Apr-2022
https://doi.org/10.1007/s00446-022-00425-x
Khanchandani PSchappi JWang YWattenhofer R(2021)On Consensus Number 1 Objects2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00115(875-882)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00115
Perrin MMostéfaoui ABonin GEmek YCachin C(2020)Extending the Wait-free Hierarchy to Multi-Threaded SystemsProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405723(21-30)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405723
Golab WScheideler CSpear M(2020)The Recoverable Consensus HierarchyProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400212(281-291)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400212
Khanchandani PWattenhofer R(2020)Two elementary instructions make compare-and-swapJournal of Parallel and Distributed Computing10.1016/j.jpdc.2020.06.005Online publication date: Jun-2020
https://doi.org/10.1016/j.jpdc.2020.06.005
Khanchandani PWattenhofer R(2019)Two Elementary Instructions Make Compare-and-Swap2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00046(365-374)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00046
Ellen FGelashvili RShavit NZhu L(2019)A complexity-based classification for multiprocessor synchronizationDistributed Computing10.1007/s00446-019-00361-3Online publication date: 4-Sep-2019
https://doi.org/10.1007/s00446-019-00361-3
Attiya HCastañeda AHendler DPerrin MNewport CKeidar I(2018)Separating Lock-Freedom from Wait-FreedomProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212739(41-50)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3212734.3212739
Khanchandani PWattenhofer R(2018)On the Importance of Synchronization Primitives with Low Consensus NumbersProceedings of the 19th International Conference on Distributed Computing and Networking10.1145/3154273.3154306(1-10)Online publication date: 4-Jan-2018
https://dl.acm.org/doi/10.1145/3154273.3154306
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents