The Space Complexity of Consensus from Swap
share
Nearly thirty years ago, it was shown that Ω(√(n)) 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 Ω(√(n)) space complexity lower bound actually applies to a class of objects called historyless objects, which includes registers, test-and-set objects, and readable swap objects. However, every known n-process obstruction-free consensus algorithm from historyless objects uses Ω (n) objects. We give the first Ω (n) space complexity lower bounds on consensus algorithms for two kinds of historyless objects. First, we show that any obstruction-free consensus algorithm from swap objects uses at least n-1 objects. More generally, we prove that any obstruction-free k-set agreement algorithm from swap objects uses at least ⌈n/k⌉ - 1 objects. This is the first non-constant lower bound on the space complexity of solving k-set agreement with swap objects when k > 1. We also present an obstruction-free k-set agreement algorithm from n-k swap objects, exactly matching our lower bound when k=1. Second, we show that any obstruction-free binary consensus algorithm from readable swap objects with domain size b uses at least n-2/3b+1 objects. Since any historyless object can be simulated by a readable swap object with the same domain, our results imply that any obstruction-free consensus algorithm from historyless objects with domain size b uses at least n-2/3b+1 objects. For b = 2, we show a slightly better lower bound of n-2. The best known obstruction-free binary consensus algorithm from readable swap objects with domain size 2 uses 2n-1 objects, asymptotically matching our lower bound.
READ FULL TEXT