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

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.
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.
3. James Aspnes and Faith Ellen. Tight bounds for adopt-commit objects. Theory Comput. Syst., 55(3):451--474, 2014.
4. James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441--461, 1990.
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.
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.
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.
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.
11. Rachid Guerraoui and Eric Ruppert. What can be implemented anonymously? In Proc. 19th International Symposium on Distributed Computing (DISC), pages 244--259, 2005.
12. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124--149, 1991.
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.
14. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2012.
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.
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.
18. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. In Proc. 9th Annual European Symposium on Algorithms (ESA), pages 121--133, 2001.
19. Michel Raynal. Concurrent programming: algorithms, principles, and foundations. Springer Science & Business Media, 2012.
20. Eric Ruppert. Determining consensus numbers. SIAM Journal on Computing, 30(4):1156--1168, 2000.
21. Eric Schenk. The consensus hierarchy is not robust. In Proc. 16th ACM Symposium on Principles of Distributed Computing (PODC), page 279, 1997.
22. Gadi Taubenfeld. Synchronization algorithms and concurrent programming. Pearson Education, 2006.
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.

Index Terms

• Theory of computation

  • Models of computation

    • Concurrency