Thumbnail
Access Restriction
Subscribed

Author Bracha, Gabriel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1987
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Byzantine Generals protocols enable processes to broadcast messages reliably in the presence of faulty processes. These protocols are run in a system that consists of $\textit{n}$ processes, $\textit{t}$ of which are faulty. The protocols are conducted in synchronous rounds of message exchange. It is shown that, in the absence of eavesdropping, without using cryptography, for any ε > 0 and $\textit{t}$ = $\textit{n}/(3$ + ε), there is a randomized protocol with $\textit{O}(log$ $\textit{n})$ expected number of rounds. If cryptographic methods are allowed, then, for ε > 0 and $\textit{t}$ = $\textit{n}/(2$ + ε), there is a randomized protocol with $\textit{O}(log$ $\textit{n})$ expected number of rounds. This is an improvement on the lower bound of $\textit{t}$ + 1 rounds required for deterministic protocols, and on a previous result of $\textit{t}/log$ $\textit{n}$ expected number of rounds for randomized noncryptographic protocols.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1987-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 34
Issue Number 4
Page Count 11
Starting Page 910
Ending Page 920


Open content in new tab

   Open content in new tab
Source: ACM Digital Library