Lélia Blin ; Laurent Feuilloley ; Gabriel Le Bouder - Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms

dmtcs:9335 - Discrete Mathematics & Theoretical Computer Science, March 1, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.9335
Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election AlgorithmsArticle

Authors: Lélia Blin ; Laurent Feuilloley ; Gabriel Le Bouder

    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.


    Volume: vol. 25:1
    Section: Distributed Computing and Networking
    Published on: March 1, 2023
    Accepted on: February 13, 2023
    Submitted on: April 12, 2022
    Keywords: Computer Science - Distributed, Parallel, and Cluster Computing,Computer Science - Data Structures and Algorithms

    Consultation statistics

    This page has been seen 651 times.
    This article's PDF has been downloaded 546 times.