### Tight bounds for asynchronous randomized consensusTight bounds for asynchronous randomized consensus

Access Restriction
Subscribed

 Author Attiya, Hagit ♦ Censor, Keren Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2008 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Distributed computing ♦ Isoperimetric inequality ♦ Lower bound ♦ Randomized algorithms ♦ Shared-memory Abstract A distributed consensus algorithm allows $\textit{n}$ processes to reach a common decision value starting from individual inputs. $\textit{Wait-free}$ consensus, in which a process always terminates within a finite number of its own steps, is impossible in an asynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminate with probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes. This article proves that the total step complexity of randomized consensus is $Θ(n^{2})$ in an asynchronous shared memory system using multi-writer multi-reader registers. This result is achieved by improving both the lower and the upper bounds for this problem. In addition to improving upon the best previously known result by a factor of $log^{2}n,$ the lower bound features a greatly streamlined proof. Both goals are achieved through restricting attention to a set of $\textit{layered}$ executions and using an isoperimetric inequality for analyzing their behavior. The matching algorithm decreases the expected total step complexity by a log $\textit{n}$ factor, by leveraging the multi-writing capability of the shared registers. Its correctness proof is facilitated by viewing each execution of the algorithm as a stochastic process and applying Kolmogorov's inequality. 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 2008-11-05 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 55 Issue Number 5 Page Count 26 Starting Page 1 Ending Page 26

#### Open content in new tab

Source: ACM Digital Library