LĂ©lia Blin, Gabriel Le Bouder Laurent Feuilloley

*OPODIS 2021: Conference on Principles of Distributed Systems, 13-15 December 2021, Strasbourg, France.*

doi: 10.4230/LIPIcs.OPODIS.2021.22

LĂ©lia Blin, Gabriel Le Bouder Laurent Feuilloley

doi: 10.4230/LIPIcs.OPODIS.2021.22

Given a boolean predicate $\Pi$ on labeled networks (e.g., proper
coloring, leader election, etc.), a self-stabilizing algorithm for
$\Pi$ is a distributed algorithm that can start from any initial
configuration of the network (i.e., every node has an arbitrary
value assigned to each of its variables), and eventually converge
to a configuration satisfying $\Pi$.
It is known that leader election does not have a deterministic
self-stabilizing algorithm using a constant-size register at each
node, i.e., for some networks, some of their nodes must have
registers whose sizes grow with the size $n$ of the networks.
On the other hand, it is also known that leader election can be
solved by a deterministic self-stabilizing algorithm using
registers of $O(\log\ log n)$ bits per node in any $n$-node
bounded-degree network. We show that this latter space complexity
is optimal. Specifically, we prove that every deterministic
self-stabilizing algorithm solving leader election must use
$\Omega(\log\log n)$-bit per node registers in some $n$-node networks.
In addition, we show that our lower bounds go beyond leader
election, and apply to all problems that cannot be solved by
anonymous algorithms.

This paper first appeared as a
brief announcement at
DISC 2019, then as a full paper at OPODIS.

Gabriel presented the paper as a BA at DISC 2019, and as a full paper
at OPODIS 2021.
The paper received the best student paper at OPODIS 2021.

The paper received the best student paper at OPODIS 2021.