The Space Complexity of Consensus from Swap
Sean Ovens · 2022
Nearly thirty years ago, it was shown that Ω(√n ) read/write registers are needed to solve obstruction-free consensus among n processes. This lower bound was improved to n registers in 2018, which exactly matches the best upper bound. The Ømega (√n) space complexity lower bound actually applies to a class of objects called historyless objects, which includes read/write registers, test-and-set objects, and readable swap objects. However, every known n-process obstruction-free consensus algorithm from historyless objects uses Ω(n) objects.