Thumbnail
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 ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Byzantine agreement ♦ Global coin ♦ Randomization ♦ Security ♦ Spectral methods
Abstract We address the problem of Byzantine agreement, to bring processors to agreement on a bit in the presence of a $\textit{strong}$ adversary. This adversary has full information of the state of all processors, the ability to control message scheduling in an asynchronous model, and the ability to control the behavior of a constant fraction of processors that it may choose to corrupt adaptively. In 1983, Ben-Or proposed an algorithm for solving this problem with expected exponential communication time. In this article, we improve that result to require expected polynomial communication time and computation time. Like Ben-Or’s algorithm, our algorithm uses coinflips from individual processors to repeatedly try to generate a fair global coin. We introduce a method that uses spectral analysis to identify processors that have thwarted this goal by flipping biased coins.
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 2016-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 2
Page Count 21
Starting Page 1
Ending Page 21


Open content in new tab

   Open content in new tab
Source: ACM Digital Library