Abstract
We introduce an N-process deterministic concurrent object for N ≥ 3 processes, called the conditional consensus object. This object, denoted as W, is hard-wired in the sense that each process P can access it using a single fixed port (though P can use different ports in different copies of W). We prove that W satisfies the following properties:
-
There is no consensus protocol for three processes which uses many shared registers and many copies of W (and does not use any other object); but
-
There is a consensus protocol for N processes which uses one copy of W and ( N3 ) copies of CO3, where CO3 is the standard consensus object for three processes.
This implies that the hierarchy h r m is not robust for deterministic hardwired objects.
This work was supported by the France-Israel cooperative project: Graph Theoretical Methods in Distributed Computing 4474-2-93.
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
E. Borowsky, E. Gafni, and Y. Afek. Consensus power makes (some) sense! In Proc. 13th ACM Symp. on Principles of Distributed Computing, August 1994.
O. Biran, S. Moran, and S. Zaks. A combinatorial characterization of the distributed 1-solvable tasks. Journal of Algorithm 11, pages 420–440, 1990. A preliminary versions appeared in Proc. 7th ACM Symp. on Principles of Distributed Computing, August 1988.
R. Bazzi, G. Neiger, and G. Peterson. On the use of registers in achieving wait-free consensus. In Proc. 13th ACM Symp. on Principles of Distributed Computing, August 1994.
T. Chandra, V. Hadzilacos, P. Jayanti, and S. Toueg. The h r m hiererachy is not robust. Manuscript, August 1994.
T. Chandra, V. Hadzilacos, P. Jayanti, and S. Toueg. Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies. In Proc. 13th ACM Symp. on Principles of Distributed Computing, August 1994.
B. Chor, A. Israeli, and M. Li. On processor coordination using asynchronous hardware. In Proc. 6th ACM Symp. on Principles of Distributed Computing, pages 86–97, 1987.
R. Cori and S. Moran. Exotic behaviour of consensus numbers. In Proceedings of 8-th International Workshop on Distributed Algorithms, September 1994.
M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
M. Herlihy. Impossibility results for asynchronous Pram. In Proc. 3rd ACM Symp. on Algorithms and Architectures, pages 327–336, 1991.
M. P. Herlihy. Impossibility results for asynchronous Pram. In Proc. 3rd ACM Symp. on Algorithms and Architectures, pages 327–336, 1991.
P. Jayanti. On the robustness of herlihy hierarchy. In Proc. 12th ACM Symp. on Principles of Distributed Computing, August 1993.
P. Jayanti. Wait-free computing. In Proc. 9th International Workshop on Distributed Algorithms, September 1995.
C. M. Loui and H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163–183, 1987.
L. Lamport. On interprocess communication, parts I and II. Distributed Computing, 1(2):77–101, 1986.
R. Lubitch and S. Moran. Closed schedulers: A novel technique for analyzing distributed protocols. Distributed Computing, 8(4):203–210, 1995. An extended preliminary version appeared in “Closed Schedulers: Constructions and Applications to Consensus Protocols”, Proceedings of 6-th International Workshop on Distributed Algorithms, 1992 and in TR #796, Dept. of Computer Science, Technion, January 1994.
G. Peterson, R. Bazzi, and G. Neiger. A gap theorem for consensus types. In Proc. 13th ACM Symp. on Principles of Distributed Computing, August 1994.
Ophir Rachman. Anomalies in the wait-free hierarchy. In Proc. 8th International Workshop on Distributed Algorithms, 1994.
G. Taubenfeld, S. Katz, and S. Moran. Impossibility results in the presence of multiple faulty processes. Information and Computation, 1994. Preliminary version appeared in 9th FCT-TCS Conference, Bangalore, India, December, 1989, Lecture Notes in Computer Science, vol. 405 (eds.:C.E. Veni Madhavan), Springer Verlag 1989, pages 109–120.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moran, S., Rappoport, L. (1996). On the robustness of h r m . In: Babaoğlu, Ö., Marzullo, K. (eds) Distributed Algorithms. WDAG 1996. Lecture Notes in Computer Science, vol 1151. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61769-8_22
Download citation
DOI: https://doi.org/10.1007/3-540-61769-8_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61769-3
Online ISBN: 978-3-540-70679-3
eBook Packages: Springer Book Archive