A communication-efficient canonical form for fault-tolerant distributed protocols

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A communication-efficient canonical form for fault-tolerant distributed protocols

Full text

Pdf (738 KB)

Source

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

Calgary, Alberta, Canada

Pages: 63 - 72

Year of Publication: 1986

ISBN:0-89791-198-9

Author

Brian A Coan

Massachusetts Institute of Technology

Sponsor

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 10, Citation Count: 17

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/10590.10596 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	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]
	2	J. Burns and N. Lynch, "The Byzantine Firing Squad Problem," Advances in .Computing Research: Parallel and Distributed Computing, vol. 4, JAI Press Inc., Greenwich, Connecticut, to appear. (Also available as MIT Technical Report MIT/LCS/TM-275, 1985.)
	3	B. Chor and B. Coan, "A Simple and Efficient Randomized Byzantine Agreement Algorithm," Transactions on Software Engineering, vol. SE-I1, pp. 531- 539, 1985.
	4	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]
	5	D. Dolev, "The Byzantine Generals Strike Again," Journal of Algorithms, vol. 3, pp. 14-30, 1982.
	6	D. Dolev, M. Fischer, R. Fowler, N. Lynch, and H. Strong, "An Efficient Algorithm for Byzantine Agreement without Authentication," Information and Control, vol. 52, pp. 257-274, 1982.
	7	Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
	8	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]
	9	A D Fekete, Asymptotically optimal algorithms for approximate agreement, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.73-87, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10597]
	10	M. Fischer and N. Lynch, "A Lower Bound for the Time to Assure Interactive Consistency," Information Processing Letters, vol. 14, pp. 183-186, 1982.
	11	Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.59-70, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323602]
	12	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]
	13	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]
	14	N. Lynch, M. Fischer', and R. Fowler, "A Simple and Efficient Byzantine Generals Algorithm," Proceedings of the 2 na Symposium on Retzability in Distributed Software and Database Systems, pp. 46-52, 1982.
	15	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]
	16	Kenneth Jay Perry, Early stopping protocols for fault-tolerant distributed agreement, 1985
	17	M. Rabin, "Randomized Byzantine Generals," Procecdings of the 24 th Symposium on Foundations of Computer Science, pp. 403-409, 1983.
	18	T. Srikanth and S. Toueg, "Byzantine Agreement Made Simple: Simulating Authentication without Signatures," Cornell Technical Report 84-623, 1984.
	19	R. Turpin and B. Coan, "Extending Binary Byzantine Agreement to Multivalued Byzantine Agreement," Information Processing Letters, vol. 18, pp. 73-76, 1984.

CITED BY 17

	R. Michel, A categorical approach to distributed systems expressibility and knowledge, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.129-143, June 1989, Edmonton, Alberta, Canada
	Hagit Attiya , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Journal of the ACM (JACM), v.41 n.1, p.122-152, Jan. 1994
	B. A. Coan , J. L. Welch, Modular construction of nearly optimal Byzantine agreement protocols, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.295-305, June 1989, Edmonton, Alberta, Canada
	Joseph Y. Halpern , Yoram Moses , Orli Waalrts, A characterization of eventual Byzantine agreement, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.333-346, August 22-24, 1990, Quebec City, Quebec, Canada
	Juan A. Garay , Yoram Moses, Fully polynomial Byzantine agreement in t + 1 rounds, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.31-41, May 16-18, 1993, San Diego, California, United States
	Danny Dolev , Ruediger Reischuk , H. Raymond Strong, Early stopping in Byzantine agreement, Journal of the ACM (JACM), v.37 n.4, p.720-741, Oct. 1990
	Joseph Y. Halpern , Aleta Ricciardi, A knowledge-theoretic analysis of uniform distributed coordination and failure detectors, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.73-82, May 04-06, 1999, Atlanta, Georgia, United States
	Amotz Bar-Noy , Danny Dolev , Cynthia Dwork , H. Raymond Strong, Shifting gears: changing algorithms on the fly to expedite Byzantine agreement, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.42-51, August 10-12, 1987, Vancouver, British Columbia, Canada
	Rida A. Bazzi , Gil Neiger, Simplifying fault-tolerance: providing the abstraction of crash failures, Journal of the ACM (JACM), v.48 n.3, p.499-554, May 2001
	A D Fekete, Asymptotically optimal algorithms for approximate agreement, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.73-87, August 11-13, 1986, Calgary, Alberta, Canada
	Gil Neiger , Rida Bazzi, Using knowledge to optimally achieve coordination in distributed systems: extended abstract, Proceedings of the 4th conference on Theoretical aspects of reasoning about knowledge, p.43-59, March 22-25, 1992, Monterey, California
	Gil Neiger , Mark R. Tuttle, Common knowledge and consistent simultaneous coordination, Distributed Computing, v.6 n.3, p.181-192, April 1993
	Tal Mizrahi , Yoram Moses, Continuous consensus via common knowledge, Proceedings of the 10th conference on Theoretical aspects of rationality and knowledge, June 10-12, 2005, Singapore
	Brian A. Coan, Efficient agreement using fault diagnosis, Distributed Computing, v.7 n.2, p.87-98, December 1993
	Yi Zhao , Farokh B. Bastani, A self-adjusting algorithm for byzantine agreement, Distributed Computing, v.5 n.4, p.219-226, April 1992
	Joseph Y. Halpern , Aleta Ricciardi, A knowledge-theoretic analysis of uniform distributed coordination and failure detectors, Distributed Computing, v.17 n.3, p.223-236, March 2005
	Kai Engelhardt , Yoram Moses, Single-bit messages are insufficient for data link over duplicating channels, Information Processing Letters, v.107 n.6, p.235-239, August, 2008