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.
@InProceedings{defago_et_al:LIPIcs.DISC.2020.11, author = {D\'{e}fago, Xavier and Emek, Yuval and Kutten, Shay and Masuzawa, Toshimitsu and Tamura, Yasumasa}, title = {{Communication Efficient Self-Stabilizing Leader Election}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.11}, URN = {urn:nbn:de:0030-drops-130892}, doi = {10.4230/LIPIcs.DISC.2020.11}, annote = {Keywords: self-stabilization, leader election, communication overhead} }