The Space Complexity of Consensus from Swap

Sean Ovens

Nearly thirty years ago, it was shown that $\Omega (\sqrt{n})$ registers are needed to solve obstruction-free consensus among $n$ processes. This lower bound was improved to $n$ register…