License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.30
URN: urn:nbn:de:0030-drops-100901
URL: http://drops.dagstuhl.de/opus/volltexte/2018/10090/
Go to the corresponding LIPIcs Volume Portal


Sudo, Yuichi ; Ooshita, Fukuhito ; Kakugawa, Hirotsugu ; Masuzawa, Toshimitsu ; Datta, Ajoy K. ; Larmore, Lawrence L.

Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time

pdf-format:
LIPIcs-OPODIS-2018-30.pdf (0.6 MB)


Abstract

A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol. Thus, in our prior work, we introduced the concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage as self-stabilization in practice. Following this work, several loosely-stabilizing leader election protocols are presented. The loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a relatively short time, and keeps the unique leader for an sufficiently long time thereafter. The convergence times of all the existing loosely-stabilizing protocols, i.e., the expected time to reach a safe configuration, are polynomial in n where n is the number of nodes (while the holding times to keep the unique leader are exponential in n). In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, but arbitrarily large polynomial in n.

BibTeX - Entry

@InProceedings{sudo_et_al:LIPIcs:2018:10090,
  author =	{Yuichi Sudo and Fukuhito Ooshita and Hirotsugu Kakugawa and Toshimitsu Masuzawa and Ajoy K. Datta and Lawrence L. Larmore},
  title =	{{Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10090},
  URN =		{urn:nbn:de:0030-drops-100901},
  doi =		{10.4230/LIPIcs.OPODIS.2018.30},
  annote =	{Keywords: Loose-stabilization, Population protocols, and Leader election}
}

Keywords: Loose-stabilization, Population protocols, and Leader election
Seminar: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 21.12.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI