Search Results

Documents authored by Ilcinkas, David

Document
DOI: 10.4230/LIPIcs.STACS.2025.30
Being Efficient in Time, Space, and Workload: a Self-Stabilizing Unison and Its Consequences

Authors: Stéphane Devismes, David Ilcinkas, Colette Johnen, and Frédéric Mazoit

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We present a self-stabilizing algorithm for the unison problem which is efficient in time, workload, and space in a weak model. Precisely, our algorithm is defined in the atomic-state model and works in anonymous asynchronous connected networks in which even local ports are unlabeled. It makes no assumption on the daemon and thus stabilizes under the weakest one: the distributed unfair daemon. In an n-node network of diameter D and assuming the knowledge B ≥ 2D+2, our algorithm only requires Θ(log(B)) bits per node and is fully polynomial as it stabilizes in at most 2D+2 rounds and O(min(n²B, n³)) moves. In particular, it is the first self-stabilizing unison for arbitrary asynchronous anonymous networks achieving an asymptotically optimal stabilization time in rounds using a bounded memory at each node. Furthermore, we show that our solution can be used to efficiently simulate synchronous self-stabilizing algorithms in asynchronous environments. For example, this simulation allows us to design a new state-of-the-art algorithm solving both the leader election and the BFS (Breadth-First Search) spanning tree construction in any identified connected network which, to the best of our knowledge, beats all existing solutions in the literature.
Cite as

Stéphane Devismes, David Ilcinkas, Colette Johnen, and Frédéric Mazoit. Being Efficient in Time, Space, and Workload: a Self-Stabilizing Unison and Its Consequences. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{devismes_et_al:LIPIcs.STACS.2025.30,
  author =	{Devismes, St\'{e}phane and Ilcinkas, David and Johnen, Colette and Mazoit, Fr\'{e}d\'{e}ric},
  title =	{{Being Efficient in Time, Space, and Workload: a Self-Stabilizing Unison and Its Consequences}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.30},
  URN =		{urn:nbn:de:0030-drops-228568},
  doi =		{10.4230/LIPIcs.STACS.2025.30},
  annote =	{Keywords: Self-stabilization, unison, time complexity, synchronizer}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.11
Framing Algorithms for Approximate Multicriteria Shortest Paths

Authors: Nicolas Hanusse, David Ilcinkas, and Antonin Lentz

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
This paper deals with the computation of d-dimensional multicriteria shortest paths. In a weighted graph with arc weights represented by vectors, the cost of a path is the vector sum of the weights of its arcs. For a given pair consisting of a source s and a destination t, a path P dominates a path Q if and only if P’s cost is component-wise smaller than or equal to Q’s cost. The set of Pareto paths, or Pareto set, from s to t is the set of paths that are not dominated. The computation time of the Pareto paths can be prohibitive whenever the set of Pareto paths is large. We propose in this article new algorithms to compute approximated Pareto paths in any dimension. For d = 2, we exhibit the first approximation algorithm, called Frame, whose output is guaranteed to be always a subset of the Pareto set. Finally, we provide a small experimental study in order to confirm the relevance of our Frame algorithm.
Cite as

Nicolas Hanusse, David Ilcinkas, and Antonin Lentz. Framing Algorithms for Approximate Multicriteria Shortest Paths. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hanusse_et_al:OASIcs.ATMOS.2020.11,
  author =	{Hanusse, Nicolas and Ilcinkas, David and Lentz, Antonin},
  title =	{{Framing Algorithms for Approximate Multicriteria Shortest Paths}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{11:1--11:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.11},
  URN =		{urn:nbn:de:0030-drops-131476},
  doi =		{10.4230/OASIcs.ATMOS.2020.11},
  annote =	{Keywords: Pareto set, multicriteria, shortest paths, approximation}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.10
Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps

Authors: Stéphane Devismes, David Ilcinkas, and Colette Johnen

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

Abstract
We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks under the distributed unfair daemon (the most general daemon) without requiring any a priori knowledge about global parameters of the network. This is the first algorithm for this problem that is proven to achieve a polynomial stabilization time in steps. Namely, we exhibit a bound in O(W_{max} * n_{maxCC}^3 * n), where W_{max} is the maximum weight of an edge, n_{maxCC} is the maximum number of non-root processes in a connected component, and n is the number of processes. The stabilization time in rounds is at most 3n_{maxCC} + D, where D is the hop-diameter of V_r.
Cite as

Stéphane Devismes, David Ilcinkas, and Colette Johnen. Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{devismes_et_al:LIPIcs.OPODIS.2016.10,
  author =	{Devismes, St\'{e}phane and Ilcinkas, David and Johnen, Colette},
  title =	{{Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{10:1--10:16},
  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.10},
  URN =		{urn:nbn:de:0030-drops-70792},
  doi =		{10.4230/LIPIcs.OPODIS.2016.10},
  annote =	{Keywords: distributed algorithm, self-stabilization, routing algorithm, shortest path, disconnected network, shortest-path tree}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact