Message-optimal protocols for byzantine agreement (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Message-optimal protocols for byzantine agreement (extended abstract)

Full text

Pdf (1.37 MB)

Source

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

Montreal, Quebec, Canada

Pages: 309 - 323

Year of Publication: 1991

ISBN:0-89791-439-2

Authors

Vassos Hadzilacos	Computer Systems Research Institute, University of Toronto, 10 King's College Road, Toronto, Ontario M5S 1A4 CanadaComputer Systems Research Institute University of Toronto 10 King's College Road Toronto, Ontario M5S 1A4 Canada
Joseph Y. Halpern	IBM Almaden Research Center, Department K53/802, 650 Harry Road, San Jose, California

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): 9, Citation Count: 3

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/112600.112626 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	Amdur, E.S, S.M. Weber, and V. Hadzilacos. "On the Message Complexity of Binary Byzantine Agreement Under Crash Failures". Submitted for publication, March 1990.
	2	Attiya, H., N.A. Lynch and N. Shavit. "Are Wait-Free Algorithms Fast?". In Proc. of the 31st Syrup. on Foundations of Computer Science, pp. 55-64, Oct. 1990.
	3	Berman, P., J. A. Garay, and K. J. Perry. "Recursive Phase King Protocols for Distributed Consensus". Penn State Report CS-89-24, 1989.
	4	Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
	5	Coan, B. and J. Welch. "A Byzantine Agreement Protocol with Optimal Message Bit Complexity". In Proceeding~ of the 27th Annual Allerton Conference on Communication, Control, and Computing, pp. 1062-1071, 1989.
	6	Danny Dolev , Rüdiger Reischuk, Bounds on information exchange for Byzantine agreement, Journal of the ACM (JACM), v.32 n.1, p.191-204, Jan. 1985 [doi>10.1145/2455.214112]
	7	Fischer, M.J. "The Consensus Problem in Unreliable Distributed Systems". Research Report RR-273, Department of Computer Science, Yale University, June 1983.
	8	Jim Gray, The cost of messages, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.1-7, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62547]
	9	V. Hadzilacos, On the relationship between the atomic commitment and consensus problems, Fault-tolerant distributed computing, Springer-Verlag, London, 1990
	10	Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
	11	Gil Neiger , Sam Toueg, Automatically increasing the fault-tolerance of distributed algorithms, Journal of Algorithms, v.11 n.3, p.374-419, Sep. 1990 [doi>10.1016/0196-6774(90)90019-B]
	12	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]
	13	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 3

	Arkady Zamsky, An randomized Byzantine agreement protocol with constant expected time and guaranteed termination in optimal (deterministic) time, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.201-208, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Roberto De Prisco , Alain Mayer , Moti Yung, Time-optimal message-efficient work performance in the presence of faults, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.161-172, August 14-17, 1994, Los Angeles, California, United States
	Arkady Zamsky , Amos Israeli , Shlomit S. Pinter, Optimal time Byzantine agreement for t < n/8 with linear-messages, Distributed Computing, v.9 n.2, p.95-108, October 1995