Prasad Jayanti
Abstract
The problem of implementing a shared object of one type from shared objects of other types has been extensively researched. Recent focus has mostly been on wait-free implementations, which permit every process to complete its operations on implemented objects, regardless of the speeds of other processes. It is known that shared objects of different types have differing abilities to support wait-free implementations. It is therefore natural to want to arrange types in a hierarchy that reflects their relative abilities to support wait-free implementations. In this paper, we formally define robustness and other desirable properties of hierarchies. Roughly speaking, a hierarchy is robust if each type is “stronger” than any combination of lower level types. We study two specific hierarchies: one, that we call hrm in which the level of a type is based on the ability of an unbounded number of objects of that type, and another hierarchy, that we call hr1, in which a type's level is based on the ability of a fixed number of objects of that type. We prove that resource bounded hierarchies, such as hr1 and its variants, are not robust. We also establish the unique importance of hrm: every nontrivial robust hierarchy, if one exists, is necessarily a “coarsening” of hrm.
- BAZZI, R. A., NEIGER, G., AND PETERSON, G. L. 1994. On the use of registers in achieving wait-free consensus. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (Los Angeles, Calif., Aug. 14-17). ACM, New York, pp. 354-363. Google Scholar
- BOROWSKY, E., AND GAFNI, E. 1993. The implication of the Borowski-Gafni simulation on the set consensus hierarchy. Tech. Rep. 930021. Computer Science Dept., Univ. California at Los Angeles, Los Angeles, Calif.Google Scholar
- BOROWSKY, E., GAFNI, E., AND AFEK, Y. 1994. Consensus power makes (some) sense! In Proceedings of the 13th Annual A CM Symposium on Principles of Distributed Computing (Los Angeles, Calif., Aug. 14-17). ACM, New York, pp. 363-372. Google Scholar
- CHANDRA, T., HADZlLACOS, V., JAYANI, P., AND TOUEG, S. 1994. Wait-freedom vs. t-resilency and the robustness of wait-free hierarchies. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (Los Angeles, Calif., Aug. 14-17). ACM, New York, pp. 334-343. Google Scholar
- CHAUDHURI, S. 1990. Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing (Quebec City, Que., Canada, Aug. 22-24). ACM, New York, pp. 311-324. Google Scholar
- CHOR, B., ISRAELI, A., AND LI, M. 1987. On processor coordination using asynchronous hardware. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 10-12). ACM, New York, pp. 86-97. Google Scholar
- DOLEV, D., DWORK, C., AND STOCKMEYER, L. 1987. On the minimal synchronism needed for distributed consensus. J. ACM 34, 1 (Jan.), 77-97. Google Scholar
- HERLIHY, M. P. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13, 1 (Jan.), 124-149. Google Scholar
- HERLIHY, M., AND RAJSBAUM, S. 1994. Set consensus using arbitrary objects. In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (Los Angeles, Calif., Aug. 14-17). ACM, New York, pp. 324-333. Google Scholar
- HERLIHY, M., AND SHAVIT, N. 1993. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the 25th ACM Symposium on the Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 111-120. Google Scholar
- HERLIHY, M. P., AND WING, J.M. 1990. Linearizability: A correctness condition for concurrent objects. ACM Trans. Prog. Lang. Syst. 12, 3 (July), 463-492. Google Scholar
- JAYANTI, P. 1993. On the robustness of Herlihy's hierarchy. In Proceedings of the 12th AnnualACM Symposium on Principles of Distributed Computing (Ithaca, N.Y., Aug. 15-18). ACM, New York, pp. 145-158. Google Scholar
- JAYANTI, P. 1995. Wait-free computing. In Proceedings of the 9th International Workshop on Distributed Algorithms (Le Mont-Saint-Michel, France, Sept.). Lecture Notes in Computer Science, vol. 972. Springer-Verlag, New York, pp. 19-50. Google Scholar
- JAYANTI, P., AND TOUEG, S. 1992. Some results on the impossibility, universality, and decidability of consensus. In Proceedings of the 6th Workshop on Distributed Algorithms (Haifa, Israel, Nov.). Lecture Notes in Computer Science, vol. 647. Springer-Verlag, New York. Google Scholar
- KLEINBERG, J. M., AND MULLAINATHAN, S. 1993. Resource bounds and combinations of consensus objects. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (Ithaca, N.Y., Aug. 15-18). ACM, New York, pp. 133-144. Google Scholar
- Lo, W. K., AND HADZlLACOS, V. 1997. All of us are smarter than any of us: Wait-free hierarchies are not robust. In Proceedings of the 29th ACM SIGACT Symposium on Theory of Computing (El Paso, Tex., May). Google Scholar
- LOUI, M. C., AND ABU-AMARA, H.H. 1987. Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163-183.Google Scholar
- LYNCH, N., AND TUTTLE, M. 1988. An introduction to input/output automata. Tech. Rep. HIT/ LCS/TM-373. Lab. Comput. Sci., Mass. Inst. Tech., Cambridge, Mass.Google Scholar
- MORAN, S., AND RAPPOPORT, L. 1996. On the robustness of hm#. In Proceedings of the lOth Workshop on Distributed Algorithms (Bologna, Italy, Oct.). Lecture Note in Computer Science, Vol. 1151. Springer-Verlag, New York, pp. 344-361. Google Scholar
- PETERSON, G. L., BAZZI, R. A., AND NEIGER, G. 1994. A gap theorem for consensus types. In Proceedings of the 13th Annual A CM Symposium on Principles of Distributed Computing (Los Angeles, Calif., Aug. 14-17). ACM, New York, pp. 344-353. Google Scholar
- PLOTKIN, S.A. 1989. Sticky bits and universality of consensus. In Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (Edmonton, Alb., Canada, Aug. 14-16). ACM, New York, pp. 159-175. Google Scholar
- RACHMAN, O. 1994. Anomalies in the wait-free hierarchy. In Proceedings of the 8th Workshop on Distributed Algorithms (Terschelling, The Netherlands, Sept.-Oct.). Lecture Notes in Computer Science, vol. 857. Springer-Verlag, New York, pp. 156-163. Google Scholar
- SAKS, M., AND ZAHAROGLOU, F. 1993. Wait-free k-set agreement is impossible: The topology of public knowledge. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, Calif., May 16-18). ACM, New York, pp. 101-110. Google Scholar
- SCHENK, E. 1997. The consensus hierarchy is not robust. (Brief Announcement). In Proceedings of the 16th ACM Symposium on Principles of Distributed Computing. ACM, New York. Google Scholar
Index Terms
- Robust wait-free hierarchies
Recommendations
Fault-tolerant wait-free shared objects
Wait-free implementations of shared objects tolerate the failure of processes, but not the failure of base objects from which they are implemented. We consider the problem of implementing shared objects that tolerate the failure of both processes and ...
On deterministic abortable objects
PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computingWe define deterministic abortable (DA) objects, which guarantee that operations complete normally if executed solo, but may abort if executed concurrently with other operations. An operation that aborts has no effect on the object. This simple and ...
Comments