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.ICALP.2019.147
URN: urn:nbn:de:0030-drops-107239
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10723/
Go to the corresponding LIPIcs Volume Portal

Kowalski, Dariusz R. ; Mosteiro, Miguel A.

Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader

pdf-format:
LIPIcs-ICALP-2019-147.pdf (0.5 MB)

Abstract

Counting the number of nodes in {Anonymous Dynamic Networks} is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [Michail et al., 2013], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [Dariusz R. Kowalski and Miguel A. Mosteiro, 2018]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one.
In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them.

BibTeX - Entry

@InProceedings{kowalski_et_al:LIPIcs:2019:10723,
  author =	{Dariusz R. Kowalski and Miguel A. Mosteiro},
  title =	{{Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{147:1--147:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10723},
  URN =		{urn:nbn:de:0030-drops-107239},
  doi =		{10.4230/LIPIcs.ICALP.2019.147},
  annote =	{Keywords: Anonymous Dynamic Networks, Counting, distributed algorithms}
}

Keywords: Anonymous Dynamic Networks, Counting, distributed algorithms
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

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