2026-07-20T05:41:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22856 2025-10-02T13:35:36Z ddc:004 open_access

Being Efficient in Time, Space, and Workload: a Self-Stabilizing Unison and Its Consequences Devismes, Stéphane Ilcinkas, David Johnen, Colette Mazoit, Frédéric Self-stabilization unison time complexity synchronizer 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stéphane Devismes and David Ilcinkas and Colette Johnen and Frédéric Mazoit 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.30 urn:nbn:de:0030-drops-228568 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.30 eng https://creativecommons.org/licenses/by/4.0/legalcode