License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.20
URN: urn:nbn:de:0030-drops-98090
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9809/
Go to the corresponding LIPIcs Volume Portal

Dufoulon, Fabien ; Burman, Janna ; Beauquier, Joffroy

Beeping a Deterministic Time-Optimal Leader Election

pdf-format:
LIPIcs-DISC-2018-20.pdf (0.4 MB)

Abstract

The beeping model is an extremely restrictive broadcast communication model that relies only on carrier sensing. In this model, we solve the leader election problem with an asymptotically optimal round complexity of O(D + log n), for a network of unknown size n and unknown diameter D (but with unique identifiers). Contrary to the best previously known algorithms in the same setting, the proposed one is deterministic. The techniques we introduce give a new insight as to how local constraints on the exchangeable messages can result in efficient algorithms, when dealing with the beeping model.
Using this deterministic leader election algorithm, we obtain a randomized leader election algorithm for anonymous networks with an asymptotically optimal round complexity of O(D + log n) w.h.p. In previous works this complexity was obtained in expectation only.
Moreover, using deterministic leader election, we obtain efficient algorithms for symmetry-breaking and communication procedures: O(log n) time MIS and 5-coloring for tree networks (which is time-optimal), as well as k-source multi-broadcast for general graphs in O(min(k,log n) * D + k log{(n M)/k}) rounds (for messages in {1,..., M}). This latter result improves on previous solutions when the number of sources k is sublogarithmic (k = o(log n)).

BibTeX - Entry

@InProceedings{dufoulon_et_al:LIPIcs:2018:9809,
  author =	{Fabien Dufoulon and Janna Burman and Joffroy Beauquier},
  title =	{{Beeping a Deterministic Time-Optimal Leader Election}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9809},
  URN =		{urn:nbn:de:0030-drops-98090},
  doi =		{10.4230/LIPIcs.DISC.2018.20},
  annote =	{Keywords: distributed algorithms, leader election, beeping model, time complexity, deterministic algorithms, wireless networks}
}

Keywords: distributed algorithms, leader election, beeping model, time complexity, deterministic algorithms, wireless networks
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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