Simple constant-time consensus protocols in realistic failure models (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple constant-time consensus protocols in realistic failure models (extended abstract)

Full text

Pdf (1.05 MB)

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: 152 - 162

Year of Publication: 1985

ISBN:0-89791-168-7

Authors

Benny Chor	MIT Cambridge, MA
Michael Merritt	AT&T Bell Labs, Murray Hill, NJ and MIT, Cambridge, MA
David B. Shmoys	Harvard University, 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): 1, Downloads (12 Months): 10, Citation Count: 10

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.323610 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.

	ABCGM	B. Awerbuctl, M. Blum, B. Chor, S. Goldwasscr, and S. Micali, "How to hnplement Bracha's O(logn) Byzantine Agreement Algorithm", unpublished manuscript, MIT.
	ACGS	W. Alcxi, B. Chor, O. Goldreich, and C.P. Schnorr, "RSA/Rabin Bits Are ~ + poly(log N) 1 Secure", Proc. 25tn Annual Symposture on Foundations of Computer Science (1984), pp. 449-457.
	Be	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]
	Br	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]
	BT	Gabriel Bracha , Sam Toueg, Resilient consensus protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.12-26, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806706]
	CC	B. Chor and B. Coan, "A Simple and Efficient Randomized Byzantine Agreement Algn Orithm", Proc. 4ta Symposium on Reliability Distributed Software and Database Systems (1984), pp. 98-106. To appear in IEEE Transactions on Software Engineering.
	DS	Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
	FLP	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588060]
	GM	S. Goldwasser and S. Micali, "Probabilistic Encryption", Jour. of Computer and System Sciences, 28(2) (1984), pp. 270-299.
	GMR	S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
	KY	A.R. Karlin and A.C. Yao, "Probabilistic Lower Bounds for Byzantine Agreement and Clock Synchronizatir;n", unpublished manuscript, Stanford University.
	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]
	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]
	Pi	S. Pinter, Distributed Computation Systems, Ph.D. thesis, Boston University, (1983).
	Ra	M.O. Rabin, "Randomized Byzantine Generals", Proc. 24tn Annual Symposium on Foundations of Computer Science (1983), pp. 403-4O9.
	Ro	Eric C. Rosen, Vulnerabilities of network control protocols: an example, ACM SIGSOFT Software Engineering Notes, v.6 n.1, p.6-8, January 1981 [doi>10.1145/1005920.1005923]
	TC	R. Turpin and B. Coan, "Extending Binary Byzantine Agreement to Multivalucd Byzantine Agreement", Information Processing Letters 18(2)(1984), pp. 73-76.
	Y1	A.C. Yao, "Theory and Applications of Trapdoor Functions", Proc. of the 23rd IEEE Symposium on Foundations of Computer Science, (1982), pp. 80-91.
	Y2	A.C. Yao, private communication.

CITED BY 10

	Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models, Journal of the ACM (JACM), v.36 n.3, p.591-614, July 1989
	Brian Coan , Jennifer Lundelius, Transaction commit in a realistic fault model, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.40-51, August 11-13, 1986, Calgary, Alberta, Canada
	Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States
	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.363-375, August 22-24, 1990, Quebec City, 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
	R. L. Graham , A. C. Yao, On the improbability of reaching Byzantine agreements, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.467-478, May 14-17, 1989, Seattle, Washington, United States
	H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada
	Andrei Z. Broder, A provably secure polynomial approximation scheme for the distributed lottery problem (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.136-148, August 1985, Minaki, Ontario, Canada
	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995
	Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada