All of Us Are Smarter than Any of Us: Nondeterministic Wait-Free Hierarchies Are Not Robust
Authors:
- Wai-Kau LoWLWai-Kau Lo
- Vassos HadzilacosVHVassos Hadzilacos
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (3) , 689-728
Abstract
A wait-free hierarchy ACM Transactions on Programming Languages and Systems, 11 (1991), pp. 124--149; Proceedings of the 12th ACM Symposium on Principles of Distributed Computing, 1993, pp. 145--158] classifies object types on the basis of their strength in supporting wait-free implementations of other types. Such a hierarchy is robust if it is impossible to implement objects of types that it classifies as "strong" by combining objects of types that it classifies as "weak." We prove that if nondeterministic types are allowed, the only wait-free hierarchy that is robust is the trivial one, which lumps all types into a single level. In particular, the consensus hierarchy (the most closely studied wait-free hierarchy) is not robust. Our result implies that, in general, it is not possible to determine the power of a concurrent system that supports a given set of primitive object types by reasoning about the power of each primitive type in isolation.Keywords
This publication has 15 references indexed in Scilit:
- On the robustness of h m rLecture Notes in Computer Science, 1996
- Wait-freedom vs. t -resiliency and the robustness of wait-free hierarchies (extended abstract)1994
- Anomalies in the wait-free hierarchy1994
- Resource bounds and combinations of consensus objects1993
- On the robustness of Herlihy's hierarchy1993
- Some results on the impossibility, universality, and decidability of consensusLecture Notes in Computer Science, 1992
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Solution of a problem in concurrent programming controlCommunications of the ACM, 1965