Abstract
We consider the the relative power of two important synchronization problems: set agreement and renaming. We show that renaming is strictly weaker than set agreement, in a round-by-round model of computation. We introduce new techniques, including previously unknown connections between properties of manifolds and computation, as well as novel “symmetry-breaking” constructions.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. J. ACM 37(3), 524–548 (1990)
Attiya, H., Rajsbaum, S.: The combinatorial structure of wait-free solvable tasks. SIAM J. Comput. 31(4), 1286–1313 (2002)
Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 1993 ACM Symposium on Theory of Computing, pp. 206–215 (May 1993)
Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: PODC 1993: Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, pp. 41–51. ACM Press, New York (1993)
Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In: PODC 1997: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, pp. 189–198. ACM Press, New York (1997)
Chaudhuri, S.: Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In: Proceedings Of The Ninth Annual ACM Symposium On Principles of Distributed Computing, pp. 311–234 (August 1990)
Fischer, M., Lynch, N.A., Paterson, M.S.: Impossibility of distributed commit with one faulty process. Journal of the ACM 32(2) (April 1985)
Gafni, E.: Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony. In: PODC 1998: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pp. 143–152. ACM Press, New York (1998)
Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: STOC 1993: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pp. 111–120. ACM Press, New York (1993)
Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999)
Herlihy, M.P.: Wait-free synchronization. ACM Transactions On Programming Languages and Systems 13(1), 123–149 (1991)
Munkres, J.R.: Elements Of Algebraic Topology. Addison Wesley, Reading (1984)
Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. In: Proceedings of the 1993 ACM Symposium on Theory of Computing, pp. 101–110 (May 1993)
Saks, M.E., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput. 29(5), 1449–1483 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gafni, E., Rajsbaum, S., Herlihy, M. (2006). Subconsensus Tasks: Renaming Is Weaker Than Set Agreement. In: Dolev, S. (eds) Distributed Computing. DISC 2006. Lecture Notes in Computer Science, vol 4167. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11864219_23
Download citation
DOI: https://doi.org/10.1007/11864219_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44624-8
Online ISBN: 978-3-540-44627-9
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.