Revisionist Simulations: A New Technique for Proving Space Lower Bounds

In the k-set agreement problem, each process begins with an input value and must produce an output value such that at most k different input values are output. The special case when k = 1 is called consensus. It is impossible to deterministically solve k-set agreement among n > k processes in an asynchronous shared memory system with only registers. However, it is possible to do so using randomization.

We consider the space complexity of solving k-set agreement, i.e. the minimum number of registers needed to solve k-set agreement using randomization. We prove a lower bound of n/k registers. The best algorithms use n-k+1 registers. Prior to our work, the only non-constant lower bound was for consensus.

We briefly explain the previous lower bound for consensus and the difficulties we encountered in attempting to generalize it to k-set agreement. Then we present a new technique, called revisionist simulations, which we used to prove our lower bound.

This is joint work with Faith Ellen and Rati Gelashvili.