### Lower bounds for distributed coin-flipping and randomized consensusLower bounds for distributed coin-flipping and randomized consensus

Access Restriction
Subscribed

 Author Aspnes, James Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1998 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Consensus ♦ Impossibility ♦ Randomization Abstract We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip. An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to $\textit{t}$ local coin flips. We show that to guarantee at most constant bias, $ω(\textit{t}2)$ local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately wheter to hide or reveal each local coin, and (c) the game can detect which local coins have been hidden. If the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in $\textit{t},$ $ω(\textit{t}2/log2\textit{t})$ local coins are needed. Combining this fact with an extended version of the well-known Fischer-Lynch-Paterson impossibility proof of deterministic consensus, we show that given an adaptive adversary, any $\textit{t}-resilient$ asynchronous consensus protocol requires $ω(\textit{t}2/log2\textit{t})$ local coin flips in any model that can be simulated deterministically using atomic registers. This gives the first nontrivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors. 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 1998-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 45 Issue Number 3 Page Count 36 Starting Page 415 Ending Page 450

#### Open content in new tab

Source: ACM Digital Library