### Breaking the $O(n^{2})$ bit barrier: Scalable byzantine agreement with an adaptive adversaryBreaking the $O(n^{2})$ bit barrier: Scalable byzantine agreement with an adaptive adversary

Access Restriction
Subscribed

 Author King, Valerie ♦ Saia, Jared Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2011 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Byzantine agreement ♦ Monte Carlo Algorithms ♦ Peer-to-peer ♦ Samplers ♦ Consensus ♦ Distributed computing ♦ Secret-sharing Abstract We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only $Õ(&sqrt;\textit{n})$ bits, where $\textit{n}$ is the total number of processors. Our algorithm succeeds with high probability against an adaptive adversary, which can take over processors at any time during the protocol, up to the point of taking over arbitrarily close to a 1/3 fraction. We assume synchronous communication but a $\textit{rushing}$ adversary. Moreover, our algorithm works in the presence of flooding: processors controlled by the adversary can send out any number of messages. We assume the existence of private channels between all pairs of processors but make no other cryptographic assumptions. Finally, our algorithm has latency that is polylogarithmic in $\textit{n}.$ To the best of our knowledge, ours is the first algorithm to solve Byzantine agreement against an adaptive adversary, while requiring $o(n^{2})$ total bits of communication. 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 2011-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 58 Issue Number 4 Page Count 24 Starting Page 1 Ending Page 24

#### Open content in new tab

Source: ACM Digital Library