Agreement is harder than consensus: set consensus problems in totally asynchronous systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Agreement is harder than consensus: set consensus problems in totally asynchronous systems

Full text

Pdf (1.43 MB)

Source

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

Quebec City, Quebec, Canada

Pages: 311 - 324

Year of Publication: 1990

ISBN:0-89791-404-X

Author

Soma Chaudhuri

Department of Computer Science and Engineering, University of Washington, Seattle, Washington

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): 1, Downloads (12 Months): 21, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/93385.93431 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.

	ABND+87	H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, and R. Reischuk. Achievable Cases in an Asynchronous Environment. In IEEE Symposium on Foundations of Computer Science. IEEE, 1987.
	ADG84	Chagit Attiya , Danny Dolev , Joseph Gil, Asynchronous Byzantine consensus, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.119-133, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806740]
	BMZ88	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]
	BO83	Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
	Bra85	G Bracha, An O(lg n) expected rounds randomized Byzantine generals protocol, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.316-326, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22180]
	BW87	Michael F. Bridgland , Ronald J. Watro, Fault-tolerant decision making in totally asynchronous distributed systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.52-63, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41845]
	DDS83	Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
	DLS84	C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the Presence of Partial Synchrony. In A CM Symposium on Principles of Distributed Computing. ACM, 1984.
	FLP83	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]
	Rab83	M. Rabin. Randomized Byzantine Generals. In IEEE Symposium on Foundations of Computer Science. IEEE, 1983.

CITED BY 18

	Maurice Herlihy , Lucia Draque Penso, tight bounds for k-set agreement with limited-scope failure detectors, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.221-221, July 13-16, 2003, Boston, Massachusetts
	Maurice Herlihy , Sergio Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.324-333, August 14-17, 1994, Los Angeles, California, United States
	Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 1997
	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
	Achour Mostéfaoui , Michel Raynal, k-set agreement with limited accuracy failure detectors, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.143-152, July 16-19, 2000, Portland, Oregon, United States
	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
	Yehuda Afek , Gideon Stupp, Delimiting the power of bounded size synchronization objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.42-51, August 14-17, 1994, Los Angeles, California, United States
	Maurice Herlihy , Lucia Draque Penso, Tight bounds for k-set agreement with limited-scope failure detectors, Distributed Computing, v.18 n.2, p.157-166, December 2005
	Achour Mostefaoui , Michel Raynal, Randomized k-set agreement, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.291-297, July 2001, Crete Island, Greece
	Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.90-99, August 20-23, 1995, Ottowa, Ontario, Canada
	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
	Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States
	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
	Lisbeth Fajstrup , Martin Raußen , Eric Goubault, Algebraic topology and concurrency, Theoretical Computer Science, v.357 n.1, p.241-278, 25 July 2006
	Maurice Herlihy , Sergio Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.589-598, May 04-06, 1997, El Paso, Texas, United States
	Eric Goubault, Geometry and concurrency: a user's guide, Mathematical Structures in Computer Science, v.10 n.4, p.411-425, August 2000
	Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
	Gunnar Hoest , Nir Shavit, Towards a topological characterization of asynchronous complexity, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.199-208, August 21-24, 1997, Santa Barbara, California, United States