Theory Seminar

Revisionist Simulations: A New Technique for Proving Space Lower Bounds

Leqi (Jimmy) ZhuUniversity of Toronto

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.

Sponsored by

Theory Group

Faculty Host

Seth Pettie