From partial consistency to global broadcast

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

From partial consistency to global broadcast

Full text

Pdf (972 KB)

Source

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

Portland, Oregon, United States

Pages: 494 - 503

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Mattias Fitzi	Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, CH-8092 Zurich, Switzerland
Ueli Maurer	Department of Computer Science, Swiss Federal Institute of Technology (ETH), Zurich, CH-8092 Zurich, Switzerland

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 21, 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/335305.335363 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	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]
	2	Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
	3	Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Towards optimal distributed consensus (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, pages 410-415, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.
	4	David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
	5	Brian A. Coan , Jennifer L. Welch, Modular construction of a Byzantine agreement protocol with optimal message bit complexity, Information and Computation, v.97 n.1, p.61-85, March 1992 [doi>10.1016/0890-5401(92)90004-Y]
	6	Ronald Cramer, Ivan Damg~d, Stefan Dziembowski, Martin Hirt, and Tal Rabin. Efficient multiparty computations secure against an adaptive adversary. In Advances in Cryptology ~ EUROCRYPT '99, Lecture Notes in Computer Science, 1999.
	7	Danny Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1): 14-30, 1982.
	8	Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993 [doi>10.1145/138027.138036]
	9	Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and H. Raymond Strong. An efficient algorithm for Byzantine agreement without authentication. Information and Control, 52(3):257-274, March 1982.
	10	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]
	11	Matthew Franklin , Moti Yung, Secure hypergraphs: privacy from partial broadcast, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.36-44, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225077]
	12	Matthew K. Franklin and Rebecca N. Wright. Secure communication in minimal connectivity models. In Kaisa Nyberg, editor, Advances in Cryptology: EURO- CRYPT '98, volume 1403 of Lecture Notes in Computer Science. Springer, 1998.
	13	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 [doi>10.1145/167088.167101]
	14	Juan A. Garay , Kenneth J. Perry, A Continuum of Failure Models for Distributed Computing, Proceedings of the 6th International Workshop on Distributed Algorithms, p.153-165, November 02-04, 1992
	15	Anna Karlin and Andrew C. Yao. Manuscript.
	16	Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	17	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]
	18	T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
	19	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]
	20	Russell Turpin and Brian A. Coan. Extending binary Byzantine Agreement to multivalued Byzantine Agreement. Information Processing Letters, 18(2):73-76, February 1984.

CITED BY 6

	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated byzantine agreement, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	S. Amitanand , I. Sanketh , K. Srinathant , V. Vinod , C. Pandu Rangan, Distributed consensus in the presence of sectional faults, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.202-210, July 13-16, 2003, Boston, Massachusetts
	Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin, The round complexity of verifiable secret sharing and secure multicast, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.580-589, July 2001, Hersonissos, Greece
	Chiu-Yuen Koo, Broadcast in radio networks tolerating byzantine adversarial behavior, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, On the composition of authenticated Byzantine Agreement, Journal of the ACM (JACM), v.53 n.6, p.881-917, November 2006
	Jonathan Katz , Chiu-Yuen Koo, On expected constant-round protocols for Byzantine agreement, Journal of Computer and System Sciences, v.75 n.2, p.91-112, February, 2009