Show simple item record

dc.contributor.authorBracha, Gabrielen_US
dc.date.accessioned2007-04-23T16:52:53Z
dc.date.available2007-04-23T16:52:53Z
dc.date.issued1984-08en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR84-631en_US
dc.identifier.urihttps://hdl.handle.net/1813/6470
dc.description.abstractByzantine Generals algorithms enable processes to reliably broadcast messages in a system of $n$ processes where up to $t$ of the processes may be faulty. The algorithms are conducted in synchronous rounds of message exchange. For a system where $n = (3 + \delta)t$ we prove the existence of a randomized algorithm whose expected number of rounds is $O(lg n)$. This is an improvement on the lower bound of $t + 1$ rounds required for deterministic algorithms and on the previous result of $t/lg n$ expected number of rounds for randomized algorithms.en_US
dc.format.extent1193556 bytes
dc.format.extent274483 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.titleAn O(lg n) Expected Rounds Probabilistic Byzantine Generals Algorithm (The Bigger They Are, The Harder They Fall)en_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics