Abstract
We show that Naming- the existence of distinct IDs known to all- is a necessary assumption of Herlihy’s universality result for Con- sensus. We then show in a very precise sense that Naming is harder than Consensus and bring to the surface some important differences existing between popular shared memory models which usually remain unnoticed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Aspnes, Time-and space-efficient randomized consensus. Journal of Algorithms 14(3):414–431, May 1993.
J. Aspnes, Lower bounds for distributed coin-flipping and randomized consensus. Journal of the Association for Computing Machinery 45(3):415–450, May 1998.
J. Aspnes and M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms 11(3):441–461, September 1990.
J. Aspnes and O. Waarts, Randomized consensus in O(n log n) operations per processor, SIAM Journal on Computing 25(5):1024–1044, October 1996.
A. Attiya, Gorbach, S. Moran, Computing in totally anonymous shared memory systems, DISC 98, LNCS 1499, pp. 49–61
Y. Aumann, Efficient Asynchronous Consensus with the Weak Adversary Scheduler, in Proceedings of the 16th ACM S1GACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 1997), pp. 209–218
A. Bar-Noy and D. Dolev, Shared Memory vs. Message-passing in an Asynchronous Distributed Environment. In Proceedings of the 8th ACM Symposium on Principles of Distributed Computing, 1989, pp. 307–318.
E. Borowsky and E. Gafni, Immediate Atomic Snapshots and Fast Renaming. In Proceedings of the 12th ACM Symposium on Principles of Distributed Computing, 1993, pp. 41–52.
T. D. Chandra, Polylog Randomized Wait-Free Consensus, in Proceedings of the 15th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 1996)
T. D. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving Consensus. Journal of the ACM, 43(4):685–722, July 1996.
T. D. Chandra and S. Toueg, Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267, March 1996.
M. Herlihy, Wait-Free Synchronization, preliminary version in Proceedings of the 7th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 1988)
M. Herlihy and N. Shavit, The Asynchronous Computability Theorem for t-Resilient Tasks. In Proc. 25th ACM Symp. Theory of Computing, 1993, pp. 111–120.
P. Jayanti, Robust wait-free hierarchies. Journal of the ACM, 44(4):592–614, July 1997.
P. Jayanti and S. Toueg, Wake-up under read/write atomicity, WDAG 1990, LNCS 486, pp. 277–288.
S. Kutten, R. Ostrovsky and B. Patt-Shamir. The Las-Vegas Processor Identity Problem (How and When to Be Uniique), Proceedings of the 1st Israel Symposium on Theory of Computing and Systems, 1993.
R.J. Lipton and A. Park, Solving the processor identity problem in O(n) space, Inform. Process. Lett., 36(1990), 91–94.
Wai-Kau Lo and V. Hadzilacos. Using Failure Detectors to Solve Consensus in Asynchronous Shared-Memory Systems, Proceedings of the 8th International Workshop on Distributed Algorithms. Terschelling, The Netherlands, September-October 1994, pp. 280–295.
A. Panconesi, M. Papatriantafilou, P. Tsigas and P. Vitanyi, Randomized naming using wait-free shared variables. Distributed Computing (1998) 11:113–124
A. Pogosyants, R. Segal and Nancy Lynch, Verification of the Randomized Consensus Algorithm of Aspnes and Herlihy: a Case Study, MIT Technical Memo number MIT/LCS/TM-555, June 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buhrman, H., Panconesi, A., Silvestri, R., Vitanyil, P. (2000). On the Importance of Having an Identity or, is Consensus really Universal?. In: Herlihy, M. (eds) Distributed Computing. DISC 2000. Lecture Notes in Computer Science, vol 1914. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-40026-5_9
Download citation
DOI: https://doi.org/10.1007/3-540-40026-5_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41143-7
Online ISBN: 978-3-540-40026-4
eBook Packages: Springer Book Archive