Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6426
Title: Randomized Asynchronous Byzantine Agreements
Authors: Toueg, Sam
Keywords: computer science
technical report
Issue Date: Dec-1983
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-587
Abstract: A randomized protocol for reaching Byzantine Agreement in asynchronous systems with $n$ processes was recently proposed in [Rabi83]. This protocol tolerates up to $\lfloor (n-1)/10 \rfloor$ faulty processes, and agreement is reached within an expected number of phases that is a small constant independent of $n$ and the number of faulty processes $t$. In this paper, using the same computation model as in [Rabi83], it is shown that no Byzantine Agreement protocol can overcome more than $\lfloor (n-1)/3 \rfloor$ faulty processes in an asynchronous system, and we describe a protocol that achieves this upper bound. Agreement is also reached within an expected number of phases that is a small constant independent of $n$ and $t$, but the communication complexity is higher than in [Rabi83}.
URI: http://hdl.handle.net/1813/6426
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
83-587.pdf1.16 MBAdobe PDFView/Open
83-587.ps334.02 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us