Technical Report PHD-2010-10

Title: Probabilistic Methods in Distributed Computing
Authors: Keren Censor Hillel
Supervisors: Hagit Attiya
Abstract: An inherent characteristic of distributed systems is the lack of centralized control, which requires the components to coordinate their actions. This need is abstracted as the \emph{consensus} problem, in which each process has a binary input and should produce a binary output, such that all outputs agree. A difficulty in obtaining consensus arises from the possibility of process failures in practical systems. When combined with the lack of timing assumptions in asynchronous systems, it renders consensus impossible to solve, as proven by Fischer, Lynch, and Paterson in their fundamental impossibility result, which shows that no deterministic algorithm can achieve consensus in an asynchronous system, even if only a single process may fail.

Being a cornerstone in distributed computing, much research has been invested in overcoming this impossibility result. One successful approach is to incorporate randomization into the computation, allowing the processes to terminate with probability 1 instead of in every execution, while never violating agreement.

Randomized consensus is the main subject of this thesis, which investigates algorithms and lower bounds for this problem. In addition, it addresses problems that arise from the study of randomized consensus, including set agreement, and efficient concurrent data structures.

Our main contribution is in settling the total step complexity of randomized consensus, improving both known lower and upper bounds to a tight $\Theta(n^2)$. The upper bound is obtaining by presenting a new shared coin algorithm and analyzing its agreement parameter and total step complexity by viewing it as a stochastic process. The lower bound relies on considering a restricted round-based set of executions called layers, and using randomized valency arguments to prevent the algorithm for terminating too quickly. It is shown how to remain with high probability in bivalent configurations, or in null-valent configurations. The latter case is modeled as a one-round coin-flipping game, which is analyzed using an isoperimetric inequality.

The above result closes the question of the total step complexity of randomized consensus under a strong adversary, which can observe the values of all shared variables and the local states of all processes (including results of local coin-flips) before making the next scheduling decision. An additional result we present is a bound on the total number of steps as a function of the probability of termination for randomized consensus under a weak adversary, which must decide upon the entire schedule in advance.

Another complexity measure we investigate is the individual step complexity of any single process. In traditional shared coins a single process may have had to perform all the work by itself, which motivated the design of shared coins that reduce the individual step complexity. This had the price of increasing the total step complexity. In this thesis we show how to combine shared-coin algorithms to enjoy the best of their complexity measures, improving some of the known results.

For the specific model of shared multi-writer multi-reader registers, the question of individual step complexity of randomized consensus has been later settled by constructing a sub-linear approximate counter. This raises the interest in additional sub-linear data structures, and specifically in data structures providing exact values. We present an exact polylogarithmic counter, using a data structure which we call a \emph{max register}, which we implement in a polylogarithmic number of steps per operation. We then construct a framework that uses the polylogarithmic exact counter to obtain a shared-coin algorithm with an optimal individual step complexity of $O(n)$.

Finally, another way to circumvent the impossibility proof of consensus is to allow more choices. This is modeled as the problem of \emph{set agreement}, where the inputs are drawn from a set of size larger than two, and more than one output is allowed. We present randomized algorithms for different parameters of the set agreement problem, which are resilient to any number of failures.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2010
To the main CS technical reports page

Computer science department, Technion