Search Results

Documents authored by Tamura, Yasumasa

Communication Efficient Self-Stabilizing Leader Election

Authors: Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

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.

Cite as

Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura. Communication Efficient Self-Stabilizing Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-130892},
  doi =		{10.4230/LIPIcs.DISC.2020.11},
  annote =	{Keywords: self-stabilization, leader election, communication overhead}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail