Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2023

Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms

Lélia Blin
Gabriel Le Bouder

Résumé

Given a boolean predicate Π on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for Π 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 Π. 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 Ω(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.
Fichier principal
Vignette du fichier
main-lower-bound.pdf (322.97 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-03536828 , version 1 (20-01-2022)
hal-03536828 , version 2 (21-05-2023)

Identifiants

Citer

Lélia Blin, Laurent Feuilloley, Gabriel Le Bouder. Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms. Discrete Mathematics and Theoretical Computer Science, 2023, LIPIcs, 25 (1), pp.5. ⟨10.46298/dmtcs.9335⟩. ⟨hal-03536828v2⟩
122 Consultations
71 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More