Fully polynomial Byzantine agreement in t + 1 rounds

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fully polynomial Byzantine agreement in t + 1 rounds

Full text

Pdf (1.10 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 31 - 41

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Juan A. Garay
Yoram Moses

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	BD	A. Bar-Noy , D. Dolev, Families of consensus algorithms, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	BDDS	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 [doi>10.1145/41840.41844]
	BG1	P. Berman and J.A. Garay, "Cloture Votes: n/4-resilient Distributed Consensus in t q- 1 Rounds," in special issue of Mathematical Systems Theory (ed. Ray Strong) dedicated to distributed agreement, Vol. 26, No. 1 (1993).
	BG2	Piotr Berman , Juan A. Garay, Efficient Distributed Consensus with n = (3 + epsilon) t Processors (Extended Abstract), Proceedings of the 5th International Workshop on Distributed Algorithms, p.129-142, October 07-09, 1991
	BGP1	P. Berman, J.A. Garay and K.J. Perry, "Towards Optimal Distributed Consensus," Proc. 30th FOCS, pp. 410-415, October/November 1989. A revised version appears as {BG1}.
	BGP2	Piotr Berman , Juan A. Garay , Kenneth J. Perry, Optimal Early Stopping in Distributed Consensus (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.221-237, November 02-04, 1992
	C	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 [doi>10.1145/10590.10596]
	DRS	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 [doi>10.1145/96559.96565]
	DFFLS	D. Dolev, M. Fisher, R. Fowler, N. Lynch and H.R. Strong, "An Effeicient Algorithm for Byzantine Agreement without Authentication," Information and Control, Vol. 52 (1982), pp. 257-274.
	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]
	DM	Cynthia Dwork , Yoram Moses, Knowledge and common knowledge in a byzantine environment: crash failures, Information and Computation, v.88 n.2, p.156-186, Oct. 1990 [doi>10.1016/0890-5401(90)90014-9]
	F	M. J. Fischer, "The consensus problem in unreliable distributed systems (a brief survey)," Yale University Technical Report YALEU/DCS/RR-273, 1983.
	FL	M. J. Fischer and N. A. Lynch, "A Lower Bound for the Time to Assure Interactive Consistency," Information Processing Letters, Vol. 14, No. 4 (1982), pp. 183-186.
	FM	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 [doi>10.1145/62212.62225]
	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]
	MW	Y. Moses and O. Waarts, "Coordinated Traversal: (tq-1)-Round Byzantine Agreement in Polynomial Time," J. of Algorithms, to appear. An extended abstract appeared in Proc. 29th FOCS, pp. 246-255, October 1988.
	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]
	R	M. Rabin "Randomized Byzantine Generals," Proc. 24th FOCS, pp. 403-409, 1983.
	TPS	Sam Toueg , Kenneth J. Perry , T. K. Srikanth, Fast distributed agreement, SIAM Journal on Computing, v.16 n.3, p.445-457, June 1987 [doi>10.1137/0216031]
	W	O. Waarts, "Coordinated Traversal: Byzantine Agreement in polynomial time," M.Sc. thesis, Weizmann Institute of Science, Rehovot, Israel, August 1988.
	Z	A. Zamsky, "New Algorithms for Agreement in Synchronous Distributed Networks," M.Sc. thesis, Technion - Israel Institute of Technology, April 1992.

CITED BY 6

	Ziv Bar-Joseph , Michael Ben-Or, A tight lower bound for randomized synchronous consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.193-199, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Michael Ben-Or , Avinatan Hassidim, Fast quantum byzantine agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Mattias Fitzi , Ueli Maurer, From partial consistency to global broadcast, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.494-503, May 21-23, 2000, Portland, Oregon, United States
	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
	Brian A. Coan, Efficient agreement using fault diagnosis, Distributed Computing, v.7 n.2, p.87-98, December 1993
	Josh Benaloh , Dwight Tuinstra, Receipt-free secret-ballot elections (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.544-553, May 23-25, 1994, Montreal, Quebec, Canada