Consensus power makes (some) sense! (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Consensus power makes (some) sense! (extended abstract)

Full text

Pdf (1.00 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing table of contents

Los Angeles, California, United States

Pages: 363 - 372

Year of Publication: 1994

ISBN:0-89791-654-9

Authors

Elizabeth Borowsky	Computer Science Department, University of California, Los Angeles, CA
Eli Gafni	Computer Science Department, University of California, Los Angeles, CA
Yehuda Afek	Computer Science Department, Tel-Aviv University, Israel 69978

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 29, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/197917.198126 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Martín Abadi , Leslie Lamport, The existence of refinement mappings, Theoretical Computer Science, v.82 n.2, p.253-284, May 31, 1991 [doi>10.1016/0304-3975(91)90224-P]
	2	Y. Afek and G. Stupp, "Synchronization Power Dependes on the Register Size," Proc. 3dth Syrup. on Foundations of Computer Science, pages 196-206, 1993.
	3	Yehuda Afek , Eytan Weisberger , Hanan Weisman, A completeness theorem for a class of synchronization objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.159-170, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164071]
	4	Ofer Biran , Shlomo Moran , Shmuel Zaks, A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.263-275, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62590]
	5	Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
	6	Elizabeth Borowsky , Eli Gafni, Immediate atomic snapshots and fast renaming, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.41-51, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164056]
	7	E. Borowsky and E. Gafni, "The Implication of the Borowsky-Gafni Simulation on the Set- Consensus Hierarchy," University of California, Los Angeles, Technical Report 930021, 1993.
	8	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	9	Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987 [doi>10.1145/7531.7919]
	10	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
	11	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
	12	Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167125]
	13	Maurice Herlihy , Nir Shavit, A simple constructive computability theorem for wait-free computation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.243-252, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195144]
	14	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
	15	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	16	Prasad Jayanti , Sam Toueg, Some Results on the Impossibility, Universality, and Decidability of Consensus, Proceedings of the 6th International Workshop on Distributed Algorithms, p.69-84, November 02-04, 1992
	17	Prasad Jayanti, On the robustness of Herlihy's hierarchy, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.145-157, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164070]
	18	Jon Kleinberg , Sendhil Mullainathan, Resource bounds and combinations of consensus objects, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.133-143, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164069]
	19	G. Neiger, Rump Session Talk, 12th ACM Symp. on Principles of Distributed Computing, 1993.
	20	Nir Shavit, personal communication.
	21	Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167122]

CITED BY 8

	Wai-Kau Lo , Vassos Hadzilacos, All of us are smarter than any of us: wait-free hierarchies are not robust, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.579-588, May 04-06, 1997, El Paso, Texas, United States
	Gil Neiger, Failure detectors and the wait-free hierarchy (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.100-109, August 20-23, 1995, Ottowa, Ontario, Canada
	Eric Ruppert, Determining consensus numbers, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.93-99, August 21-24, 1997, Santa Barbara, California, United States
	Eric Shenk, The consensus hierarchy is not robust, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.279, August 21-24, 1997, Santa Barbara, California, United States
	Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 1997
	Rida A. Bazzi , Gil Neiger , Gary L. Peterson, On the use of registers in achieving wait-free consensus, Distributed Computing, v.10 n.3, p.117-127, April 1997
	Maurice Herlihy , Sergio Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, v.291 n.1, p.55-77, 4 January 2003
	Rachid Guerraoui , Petr Kuznetsov, The gap in circumventing the impossibility of consensus, Journal of Computer and System Sciences, v.74 n.5, p.823-830, August, 2008