DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2023.11

Making Self-Stabilizing Algorithms for Any Locally Greedy Problem

Authors: Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract

Self-stabilizing algorithms are a way to deal with network dynamicity, as it will update itself after a network change (addition or removal of nodes or edges), as long as changes are not frequent. We propose an automatic transformation of synchronous distributed algorithms that solve locally greedy and mendable problems into self-stabilizing algorithms in anonymous networks. Mendable problems are a generalization of greedy problems where any partial solution may be transformed -instead of completed- into a global solution: every time we extend the partial solution, we are allowed to change the previous partial solution up to a given distance. Locally here means that to extend a solution for a node, we need to look at a constant distance from it. In order to do this, we propose the first explicit self-stabilizing algorithm computing a (k,k-1)-ruling set (i.e. a "maximal independent set at distance k"). By combining this technique multiple times, we compute a distance-K coloring of the graph. With this coloring we can finally simulate Local model algorithms running in a constant number of rounds, using the colors as unique identifiers. Our algorithms work under the Gouda daemon, similar to the probabilistic daemon: if an event should eventually happen, it will occur.

Cite as

Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues. Making Self-Stabilizing Algorithms for Any Locally Greedy Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.SAND.2023.11,
  author =	{Cohen, Johanne and Pilard, Laurence and Rabie, Mika\"{e}l and S\'{e}nizergues, Jonas},
  title =	{{Making Self-Stabilizing Algorithms for Any Locally Greedy Problem}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.11},
  URN =		{urn:nbn:de:0030-drops-179475},
  doi =		{10.4230/LIPIcs.SAND.2023.11},
  annote =	{Keywords: Greedy Problem, Ruling Set, Distance-K Coloring, Self-Stabilizing Algorithm}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2016.11

Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3

Authors: Johanne Cohen, Khaled Maâmra, George Manoussakis, and Laurence Pilard

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract

We present the first polynomial self-stabilizing algorithm for finding a (2/3)-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne et al. and has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a time complexity in O(n^3) moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne et al. algorithm, it only requires a constant amount of memory space (three identifiers and two booleans per node).

Cite as

Johanne Cohen, Khaled Maâmra, George Manoussakis, and Laurence Pilard. Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2016.11,
  author =	{Cohen, Johanne and Ma\^{a}mra, Khaled and Manoussakis, George and Pilard, Laurence},
  title =	{{Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.11},
  URN =		{urn:nbn:de:0030-drops-70808},
  doi =		{10.4230/LIPIcs.OPODIS.2016.11},
  annote =	{Keywords: Self-Stabilization, Distributed Algorithm, Fault Tolerance, Matching}
}

Search Results

Documents authored by Pilard, Laurence

Making Self-Stabilizing Algorithms for Any Locally Greedy Problem

Abstract

Cite as

Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3

Abstract

Cite as

Thanks for your feedback!

Could not send message