Easy impossibility proofs for distributed consensus problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Easy impossibility proofs for distributed consensus problems

Full text

Pdf (920 KB)

Source

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

Minaki, Ontario, Canada

Pages: 59 - 70

Year of Publication: 1985

ISBN:0-89791-168-7

Authors

Michael J. Fischer	Yale University, New Haven, CT
Nancy A. Lynch	Mass. Inst. of Tech., Cambridge, MA
Michael Merritt	AT&T Bell Labs., Murray Hill, NJ and Mass. Inst. of Tech., Cambridge, MA

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

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/323596.323602 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.

	A	Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
	B	J. Bums, "A Formal Model for Message Passing Systems," TR-91, Indiana University, September 1980.
	BL	J. Burns, N. Lynch "Tile Byzantine Firing Squad Problem," submitted for publication.
	CDDS	B A Coan , D Dolev , C Dwork , L Stockmeyer, The distributed firing squad problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.335-345, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22182]
	D	D. l)olcv. "The Byzantine Gencrals Strike Again," Journal of Algorithms, 3, 1982, pp. 14-30.
	DHS	Danny Dolev , Joe Halpern , H. Raymond Strong, On the possibility and impossibility of achieving clock synchronization, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.504-511, December 1984 [doi>10.1145/800057.808720]
	DLPSW	D. Dolev, N. A. Lynch, S. Pinter, E. Stark and W. Weihl, "Reaching Approximate Agreement in the Presence of Faults," Proc. of the 3rd Annual IEEE Syrup. on Distributed Sofware and Databases, 1983.
	IR	A. Itai, M. Rodeh, "The Lord of the Ring or Probabilistic Methods for Breaking Symmetry in Distributive Networks," RJ-3110, IBM Research Report, April 1981.
	L	L. Lamport, The Weak Byzantine Generals Problem, Journal of the ACM (JACM), v.30 n.3, p.668-676, July 1983 [doi>10.1145/2402.322398]
	LSP	Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
	MS	Stephen R. Mahaney , Fred B. Schneider, Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.237-249, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323618]
	PSL	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]

CITED BY 6

	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
	Brian A Coan, A communication-efficient canonical form for fault-tolerant distributed protocols, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.63-72, August 11-13, 1986, Calgary, Alberta, Canada
	Joseph Y. Halpern , Ronald Fagin, A formal model of knowledge, action, and communication in distributed systems: preliminary report, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.224-236, August 1985, Minaki, Ontario, Canada
	T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987
	Shlomo Moran , Manfred Warmuth, Gap theorems for distributed computing, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.131-150, August 11-13, 1986, Calgary, Alberta, Canada
	Alon Itai , Shay Kutten , Yaron Wolfstahl , Shmuel Zaks, Optimal Distributed t-Resilient Election in Complete Networks, IEEE Transactions on Software Engineering, v.16 n.4, p.415-420, April 1990