The Taub Faculty of Computer Science Events and Talks

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. This talk will discuss the main challenges in designing randomized consensus algorithms and proving lower bounds. In particular, we present a tight $\Theta(n^2)$ bound for the total step complexity of randomized consensus, obtained by improving both known upper and lower bounds. We describe additional problems that arise from the study of randomized consensus, including different adversary types, the problem of set agreement, and implementing efficient concurrent data structures. Many open problems will be presented throughout the talk. The talk will be self-contained and will assume no prior knowledge in distributed computing.