The consensus problem is a fundamental building block of distributed computing. Solutions to this problem can be found in the large-scale systems that run the Cloud, as well as in the programming librairies of multicore architectures.
Consensus requires the processes to reach an agreement on a common value. In simple terms, this problem can be formulated as follow. Consider a set of processes that communicate by reading/writing a shared memory. Each process may propose a value and eventually it should decide one of the proposed values. The difficulty of consensus lies in two facts. First, (Agreement) the processes should agree on a single value. Second, (Wait-freedom) every process must decide in a finite time, even if the other processes suspend their executions.
At the 48th Annual Symposium on the Theory of Computing (STOC 2016), L. Zhu [1] has presented a lower bound on the space complexity of consensus. His paper proves that in a system of n processes consensus requires (n-1) registers. This lower bound is a large improvement over previous existing results, namely O(n/20) in [2] and O(sqrt{n}) in [3].
However, this bound is not tight. For instance, a system of two processes requires at least two registers. The proof is simple and goes as follows. Assume two processes, say p and q, and by contradiction consider that an algorithm A solves cosnensus with a single register (R). Consider that process p proposes 0 and that q is initially suspended. Since A satisfies Wait-freedom, process p should eventually decide its own value, i.e., 0. Name r this execution of A. Symetrically, we may consider an execution r' where q executes solo and decides 1. Now, let s be the first write made by p in the execution r. In other words, we can write r=a.s.b, where a and b are the steps executed by p before and after step s. We consider the execution a.r'.s.b. In the sequence a, process p never writes to the shared memory. Thus, a.r' is identical to r' for process q and q decides 1 in a.r'.s.b. Observe now that process p overwrites the content of the unique register R after the step s in a.r'.s.b. Hence, this execution is identical to a.s.b for p, and p must decide 0. It follows that a.r'.s.b breaks the Agreement invariant of consensus, and there is no such algorithm A.
The goal of this project is to study the space complexity of consensus. The core question is whether consensus in shared memory requires one register per process. Answering it only necessiates a paper and a pen.
The project is open to students from either IP Paris Masters (PDS, HPDA), or VAP ASR at Telecom SudParis.
As a starter, the student(s) will investigate the case of anonymous systems, where processes are not distinguisable and execute the very same code. In particular, they will study the simpler proof provided in [3]. Then, they will turn their attention to the case of processes with identities, and the proof of Zhu. In trying to generalize the proof of Zhu, the students will first consider small system, e.g., 3 to 4 processes. If they succeed, they will attempt to find a generalization for any number n>0 of processes.
[1] A Tight Space Bound for Consensus, Leqi Zhu, STOC 2016.
[2] On the Optimal Space Complexity of Consensus for Anonymous Processes, Rati Gelashvili, DISC 2016.
[3] On the Space Complexity of Randomized Synchronization, Faith Ellen Fich, Maurice Herlihy, Nir Shavit, PODC 2014.