2026-08-17T19:49:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13089 2024-03-06T10:51:32Z ddc:004 open_access

Communication Efficient Self-Stabilizing Leader Election Défago, Xavier Emek, Yuval Kutten, Shay Masuzawa, Toshimitsu Tamura, Yasumasa self-stabilization leader election communication overhead This paper presents a randomized self-stabilizing algorithm that elects a leader r in a general n-node undirected graph and constructs a spanning tree T rooted at r. The algorithm works under the synchronous message passing network model, assuming that the nodes know a linear upper bound on n and that each edge has a unique ID known to both its endpoints (or, alternatively, assuming the KT₁ model). The highlight of this algorithm is its superior communication efficiency: It is guaranteed to send a total of Õ (n) messages, each of constant size, till stabilization, while stabilizing in Õ (n) rounds, in expectation and with high probability. After stabilization, the algorithm sends at most one constant size message per round while communicating only over the (n - 1) edges of T. In all these aspects, the communication overhead of the new algorithm is far smaller than that of the existing (mostly deterministic) self-stabilizing leader election algorithms. The algorithm is relatively simple and relies mostly on known modules that are common in the fault free leader election literature; these modules are enhanced in various subtle ways in order to assemble them into a communication efficient self-stabilizing algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xavier Défago and Yuval Emek and Shay Kutten and Toshimitsu Masuzawa and Yasumasa Tamura 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.11 urn:nbn:de:0030-drops-130892 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.11 eng https://creativecommons.org/licenses/by/3.0/legalcode