Optimal Space Lower Bound for Deterministic SelfStabilizing Leader Election Algorithms
Abstract
Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring, leader election, etc.), a selfstabilizing 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 selfstabilizing algorithm using a constantsize 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 selfstabilizing algorithm using registers of $O(\log \log n)$ bits per node in any $n$node boundeddegree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic selfstabilizing 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.
 Publication:

arXiv eprints
 Pub Date:
 May 2019
 arXiv:
 arXiv:1905.08563
 Bibcode:
 2019arXiv190508563B
 Keywords:

 Computer Science  Distributed;
 Parallel;
 and Cluster Computing;
 Computer Science  Data Structures and Algorithms
 EPrint:
 The paper as been rewritten. It appeared in the arxiv, and as a brief announcment at DISC 2019, under the name "Memory Lower Bounds for SelfStabilization"