Ph.D Thesis

Ph.D StudentCensor Hillel Keren
SubjectProbabilistic Methods in Distributed Computing
DepartmentDepartment of Computer Science
Supervisor PROF. Hagit Attiya
Full Thesis textFull thesis text - English Version


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 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).

In addition to the above result, which holds under a strong adversary, we present 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.

Previously, shared coins were designed to reduce the individual step complexity of any single process. However, this resulted in an increase of 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 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. We present an exact polylogarithmic counter, and construct a framework that uses this to obtain a shared-coin algorithm with an optimal individual step complexity of O(n).

Finally, we present wait-free randomized algorithms for different parameters of the set agreement problem. Here the inputs are drawn from a set of size larger than two, and more than one output is allowed.