  The optimal space complexity of consensus in shared memory is a decades-old
open problem. For a system of $n$ processes, no algorithm is known that uses a
sublinear number of registers. However, the best known lower bound due to Fich,
Herlihy, and Shavit requires $\Omega(\sqrt{n})$ registers.
  The special symmetric case of the problem where processes are anonymous (run
the same algorithm) has also attracted attention. Even in this case, the best
lower and upper bounds are still $\Omega(\sqrt{n})$ and $O(n)$. Moreover, Fich,
Herlihy, and Shavit first proved their lower bound for anonymous processes, and
then extended it to the general case. As such, resolving the anonymous case
might be a significant step towards understanding and solving the general
problem.
  In this work, we show that in a system of anonymous processes, any consensus
algorithm satisfying nondeterministic solo termination has to use $\Omega(n)$
read-write registers in some execution. This implies an $\Omega(n)$ lower bound
on the space complexity of deterministic obstruction-free and randomized
wait-free consensus, matching the upper bound and closing the symmetric case of
the open problem.

Distributed, Parallel, and Cluster Computing