Search Results

Documents authored by Blin, Lélia

Document
DOI: 10.4230/LIPIcs.DISC.2025.17
Deterministic Synchronous Self-Stabilizing BFS Construction with Constant Space Complexity

Authors: Lélia Blin, Franck Petit, and Sébastien Tixeuil

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In this paper, we resolve a long-standing open problem in self-stabilization asking whether it is possible to construct a spanning tree using constant memory per node in a synchronous semi-uniform networks, i.e., networks in which one node is distinguished. We design a synchronous self-stabilizing algorithm that constructs a breadth-first search (BFS) tree in any anonymous semi-uniform network using only a constant number of bits of memory per node. Crucially, our approach operates without any prior knowledge of global network parameters such as maximum degree, diameter, or number of nodes. In contrast to traditional self-stabilizing methods - such as pointer-to-neighbors, distance-to-root, or identifiers - that are unsuitable under strict memory constraints, our solution employs an innovative constant-space token dissemination mechanism. This mechanism effectively eliminates cycles and rectifies errors in the BFS structure, ensuring both correctness and memory efficiency. The proposed algorithm not only meets the stringent requirements of memory-constrained distributed systems, but also opens new avenues for research in the design of self-stabilizing protocols under severe resource limitations: constant space-complexity may not systematically prevent the existence of self-stabilizing algorithms for important non-trivial tasks.
Cite as

Lélia Blin, Franck Petit, and Sébastien Tixeuil. Deterministic Synchronous Self-Stabilizing BFS Construction with Constant Space Complexity. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blin_et_al:LIPIcs.DISC.2025.17,
  author =	{Blin, L\'{e}lia and Petit, Franck and Tixeuil, S\'{e}bastien},
  title =	{{Deterministic Synchronous Self-Stabilizing BFS Construction with Constant Space Complexity}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.17},
  URN =		{urn:nbn:de:0030-drops-248349},
  doi =		{10.4230/LIPIcs.DISC.2025.17},
  annote =	{Keywords: Distributed algorithms, fault-tolerance, transient faults, self-stabilization, memory optimization}
}
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}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.43
Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs

Authors: Lélia Blin and Sébastien Tixeuil

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).
Cite as

Lélia Blin and Sébastien Tixeuil. Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{blin_et_al:LIPIcs.DISC.2017.43,
  author =	{Blin, L\'{e}lia and Tixeuil, S\'{e}bastien},
  title =	{{Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.43},
  URN =		{urn:nbn:de:0030-drops-79829},
  doi =		{10.4230/LIPIcs.DISC.2017.43},
  annote =	{Keywords: Leader Election, Self-stabilization, Memory Complexity, Arbitrary Graphs}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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