### An $\textit{O}(log$ $\textit{n})$ expected rounds randomized byzantine generals protocolAn $\textit{O}(log$ $\textit{n})$ expected rounds randomized byzantine generals protocol

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

Source: ACM Digital Library