Fast asynchronous Byzantine agreement with optimal resilience

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast asynchronous Byzantine agreement with optimal resilience

Full text

Pdf (1.12 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: 42 - 51

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Ran Canetti
Tal Rabin

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 67, Citation Count: 25

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

	AM	H. Attiya and M. Mavronicolas, "Efficiency of Semi, Synchronous versus Asynchronous Networks," Mathematical Systems Theory, to appear. Preliminary version in proceedings of the 28th annual Allerton Conference on Communication, Control and Computing, October 1990, pp. 578-587.
	BCG	Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167109]
	BE	M. Ben-Or and R. EI-Yaniv, "Interactive Consistency in Constant Time", submitted for publication, 1991
	BGW	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]
	Br	Gabriel Bracha, An asynchronous [(n - 1)/3]-resilient consensus protocol, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.154-162, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806743]
	CR	R. Canetti, and T. Rabin, "Optimal Asynchronous Byzantine Agreement", Technical Report #92-15, CS Department, Hebrew University, 1992.
	CCD	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]
	CGMA	B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, "Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults", 26th FOCS, pp. 383-395, 1985.
	CD	B. Chor and C. Dwork, "Randomization in Bysantine Agreement", Advances in Computing Research, Vol. 5, pp. 443-497, 1989.
	Fe	P. Feldman, "Asynchronous Byzantine Agreement in Constant Expected Time", unpublished manuscript, 1989.
	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]
	F	M. Fischer, "The Concensus Problem in Unreliable Distributed System", Technical Report, Yale University, 1983.
	FLP	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	KY	A. Karlin and A. Yao, "Probabilistic Lower Bounds for Byzantine Agreement", unpublished manuscript, 1986.
	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]
	R1	M. Rabin, "Randomized Byzantine Generals", 24th FOCS, pp. 403-409, 1983.
	R2	T. Rabin , "Robust Sharing Of Secrets When The Dealer Is Honest Or Faulty", Masters Thesis, Hebrew University, submitted for publication to the JA CM.
	RB	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]
	Sh	Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]

CITED BY 25

	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
	Yaron Minsky , Robbert van Renesse , Fred B. Schneider , Scott D. Stoller, Cryptographic support for fault-tolerant distributed computing, Proceedings of the 7th workshop on ACM SIGOPS European workshop: Systems support for worldwide applications, September 09-11, 1996, Connemara, Ireland
	Michael Ben-Or , Boaz Kelmer , Tal Rabin, Asynchronous secure computations with optimal resilience (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.183-192, August 14-17, 1994, Los Angeles, California, United States
	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, Sequential composition of protocols without simultaneous termination, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Shafi Goldwasser, Multi party computations: past and present, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.1-6, August 21-24, 1997, Santa Barbara, California, United States
	Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	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
	Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States
	Christian Cachin, An asynchronous protocol for distributed computation of RSA inverses and its applications, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.153-162, July 13-16, 2003, Boston, Massachusetts
	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
	Matthias Fitzi , Juan A. Garay, Efficient player-optimal protocols for strong and differential consensus, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.211-220, July 13-16, 2003, Boston, Massachusetts
	James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003
	Christian Cachin , Reto Strobl, Asynchronous group key exchange with failures, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Alejandro Hevia , Daniele Micciancio, Simultaneous broadcast revisited, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Roy Friedman , Achour Mostefaoui , Michel Raynal, Simple and Efficient Oracle-Based Consensus Protocols for Asynchronous Byzantine Systems, IEEE Transactions on Dependable and Secure Computing, v.2 n.1, p.46-56, January 2005
	Michael Ben-Or , Ran El-Yaniv, Resilient-optimal interactive consistency in constant time, Distributed Computing, v.16 n.4, p.249-262, December 2003
	Christian Cachin , Klaus Kursawe , Anna Lysyanskaya , Reto Strobl, Asynchronous verifiable secret sharing and proactive cryptosystems, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA
	Roberto Baldoni , Jean-Michel Hélary , Sara Tucci Piergiovanni, A methodology to design arbitrary failure detectors for distributed protocols, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.7, p.619-637, July, 2008
	Bruce Kapron , David Kempe , Valerie King , Jared Saia , Vishal Sanwalani, Fast asynchronous byzantine agreement and leader election with full information, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1038-1047, January 20-22, 2008, San Francisco, California
	Chryssis Georgiou , Seth Gilbert , Rachid Guerraoui , Dariusz R. Kowalski, On the complexity of asynchronous gossip, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Ittai Abraham , Danny Dolev , Joseph Y. Halpern, An almost-surely terminating polynomial protocol forasynchronous byzantine agreement with optimal resilience, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Michael Ben-Or , Danny Dolev , Ezra N. Hoch, Fast self-stabilizing byzantine tolerant digital clock synchronization, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Arpita Patra , Ashish Choudhary , Chandrasekharan Pandu Rangan, Simple and efficient asynchronous byzantine agreement with optimal resilience, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Alptekin Küpçü , Anna Lysyanskaya , James W. Mickens, Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada