Search Results

Documents authored by Le Bouder, Gabriel

Document
DOI: 10.4230/LIPIcs.OPODIS.2021.24
Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms

Authors: Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
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.
Cite as

Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder. Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blin_et_al:LIPIcs.OPODIS.2021.24,
  author =	{Blin, L\'{e}lia and Feuilloley, Laurent and Le Bouder, Gabriel},
  title =	{{Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{24:1--24:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.24},
  URN =		{urn:nbn:de:0030-drops-157997},
  doi =		{10.4230/LIPIcs.OPODIS.2021.24},
  annote =	{Keywords: Space lower bound, memory tight bound, self-stabilization, leader election, anonymous, identifiers, state model, ring topology}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.37
Brief Announcement: Memory Lower Bounds for Self-Stabilization

Authors: Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In the context of self-stabilization, a silent algorithm guarantees that the communication registers (a.k.a register) of every node do not change once the algorithm has stabilized. At the end of the 90’s, Dolev et al. [Acta Inf. '99] showed that, for finding the centers of a graph, for electing a leader, or for constructing a spanning tree, every silent deterministic algorithm must use a memory of Omega(log n) bits per register in n-node networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of proof-labeling-scheme, that, for constructing a minimum-weight spanning tree (MST), every silent algorithm must use a memory of Omega(log^2n) bits per register. It follows that requiring the algorithm to be silent has a cost in terms of memory space, while, in the context of self-stabilization, where every node constantly checks the states of its neighbors, the silence property can be of limited practical interest. In fact, it is known that relaxing this requirement results in algorithms with smaller space-complexity. In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary deterministic self-stabilizing algorithms, not necessarily silent. To our knowledge, the only known lower bound on the memory requirement for deterministic general algorithms, also established at the end of the 90’s, is due to Beauquier et al. [PODC '99] who proved that registers of constant size are not sufficient for leader election algorithms. We improve this result by establishing the lower bound Omega(log log n) bits per register for deterministic self-stabilizing algorithms solving (Delta+1)-coloring, leader election or constructing a spanning tree in networks of maximum degree Delta.
Cite as

Lélia Blin, Laurent Feuilloley, and Gabriel Le Bouder. Brief Announcement: Memory Lower Bounds for Self-Stabilization. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 37:1-37:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{blin_et_al:LIPIcs.DISC.2019.37,
  author =	{Blin, L\'{e}lia and Feuilloley, Laurent and Le Bouder, Gabriel},
  title =	{{Brief Announcement: Memory Lower Bounds for Self-Stabilization}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{37:1--37:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.37},
  URN =		{urn:nbn:de:0030-drops-113442},
  doi =		{10.4230/LIPIcs.DISC.2019.37},
  annote =	{Keywords: Space lower bound, memory tight bound, deterministic self-stabilization, leader election, anonymous, identifiers, state model, ring}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact