Show simple item record

dc.contributor.authorBracha, Gabrielen_US
dc.contributor.authorToueg, Samen_US
dc.date.accessioned2007-04-23T16:48:10Z
dc.date.available2007-04-23T16:48:10Z
dc.date.issued1983-06en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR83-559en_US
dc.identifier.urihttps://hdl.handle.net/1813/6399
dc.description.abstractA consensus protocol enables a system of $n$ aynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes can only die, malicious processes can also send false messages. We investigate consensus protocols that terminate within finite time with probability 1 under certain assumptions on the behavior of the system. With fail-stop processes, we show that $\lceil (n + 1)/2 \rceil$ correct processes are necessary and sufficient to reach agreement. In the malicious case, we show that $\lceil (2n + 1)/3 \rceil$ correct processes are necessary and sufficient to reach agreement. This is contrasted with a recent result that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail. We also investigate the possibility of reliable broadcast (Byzantine Agreement) in an asynchronous system. We define the notion of Asynchronous Byzantine Agreement, and show that $\lceil (2n + 1)/3 \rceil$ correct processes are necessary and sufficient to reach Asynchronous Byzantine Agreement.en_US
dc.format.extent2069581 bytes
dc.format.extent418948 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleAsynchronous Consensus and Byzantine Protocols in Faulty Environmentsen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics