Access Restriction

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

   Open content in new tab
Source: ACM Digital Library