  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$ registers in 2018, which exactly matches the best
upper bound. The $\Omega(\sqrt{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 $\Omega (n)$ objects.
  We give the first $\Omega (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 $\lceil \frac{n}{k}\rceil - 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 $\frac{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
$\frac{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.
