文章基本信息

标题：Communication Efficient Self-Stabilizing Leader Election
本地全文：下载
作者：Xavier Dfago ; Yuval Emek ; Shay Kutten 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-19
DOI：10.4230/LIPIcs.DISC.2020.11
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 OÌf (n) messages, each of constant size, till stabilization, while stabilizing in OÌf (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.
关键词：self-stabilization; leader election; communication overhead