On the Space Complexity of Colourless Tasks

Abstract

In this thesis, we prove lower bounds on the number of registers needed to solve colourless tasks in asynchronous shared memory systems. Many fundamental synchronization tasks, such as consensus, k-set agreement, and epsilon-approximate agreement, are colourless. We show that it is possible to transform any nondeterministic solo-terminating algorithm (including any randomized wait-free algorithm) into an obstruction-free algorithm that uses the same number of registers. This result extends to algorithms using any finite number of deterministic objects that support read operations. Hence, we can focus on proving lower bounds for obstruction-free algorithms. We prove a tight lower bound on the number of registers needed to solve obstruction-free consensus. We also prove the first non-constant lower bounds on the number of registers needed to solve obstruction-free k-set agreement and obstruction-free epsilon-approximate agreement. The bound for k-set agreement is asymptotically tight when k is a constant and the bound for epsilon-approximate agreement is asymptotically tight when epsilon is sufficiently small. To prove these bounds, we introduce a new technique, revisionist simulations. This technique allows us to prove a general theorem that yields lower bounds on the number of registers needed to solve any colourless task in an obstruction-free manner. Finally, we define the class of extension-based proofs and show that no extension-based proof can establish the impossibility of deterministically solving k-set agreement among n > k > 1 processes in a wait-free manner using registers.