License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.18
URN: urn:nbn:de:0030-drops-191442
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19144/
Go to the corresponding LIPIcs Volume Portal

Di Luna, Giuseppe A. ; Viglietta, Giovanni

Optimal Computation in Leaderless and Multi-Leader Disconnected Anonymous Dynamic Networks

pdf-format:
LIPIcs-DISC-2023-18.pdf (2 MB)

Abstract

We give a simple characterization of which functions can be computed deterministically by anonymous processes in dynamic networks, depending on the number of leaders in the network. In addition, we provide efficient distributed algorithms for computing all such functions assuming minimal or no knowledge about the network. Each of our algorithms comes in two versions: one that terminates with the correct output and a faster one that stabilizes on the correct output without explicit termination. Notably, these are the first deterministic algorithms whose running times scale linearly with both the number of processes and a parameter of the network which we call dynamic disconnectivity (meaning that our dynamic networks do not necessarily have to be connected at all times). We also provide matching lower bounds, showing that all our algorithms are asymptotically optimal for any fixed number of leaders.
While most of the existing literature on anonymous dynamic networks relies on classical mass-distribution techniques, our work makes use of a recently introduced combinatorial structure called history tree, also developing its theory in new directions. Among other contributions, our results make definitive progress on two popular fundamental problems for anonymous dynamic networks: leaderless Average Consensus (i.e., computing the mean value of input numbers distributed among the processes) and multi-leader Counting (i.e., determining the exact number of processes in the network). In fact, our approach unifies and improves upon several independent lines of research on anonymous networks, including Nedić et al., IEEE Trans. Automat. Contr. 2009; Olshevsky, SIAM J. Control Optim. 2017; Kowalski-Mosteiro, ICALP 2019, SPAA 2021; Di Luna-Viglietta, FOCS 2022.

BibTeX - Entry

@InProceedings{diluna_et_al:LIPIcs.DISC.2023.18,
  author =	{Di Luna, Giuseppe A. and Viglietta, Giovanni},
  title =	{{Optimal Computation in Leaderless and Multi-Leader Disconnected Anonymous Dynamic Networks}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19144},
  URN =		{urn:nbn:de:0030-drops-191442},
  doi =		{10.4230/LIPIcs.DISC.2023.18},
  annote =	{Keywords: anonymous dynamic network, leaderless network, disconnected network, history tree}
}

Keywords: anonymous dynamic network, leaderless network, disconnected network, history tree
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

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