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.2021.34
URN: urn:nbn:de:0030-drops-148362
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14836/
Go to the corresponding LIPIcs Volume Portal

Schwartzman, Gregory ; Sudo, Yuichi

Smoothed Analysis of Population Protocols

pdf-format:
LIPIcs-DISC-2021-34.pdf (0.9 MB)

Abstract

In this work, we initiate the study of smoothed analysis of population protocols. We consider a population protocol model where an adaptive adversary dictates the interactions between agents, but with probability p every such interaction may change into an interaction between two agents chosen uniformly at random. That is, p-fraction of the interactions are random, while (1-p)-fraction are adversarial. The aim of our model is to bridge the gap between a uniformly random scheduler (which is too idealistic) and an adversarial scheduler (which is too strict).
We focus on the fundamental problem of leader election in population protocols. We show that, for a population of size n, the leader election problem can be solved in O(p^{-2}n log³ n) steps with high probability, using O((log² n) ⋅ (log (n/p))) states per agent, for all values of p ≤ 1. Although our result does not match the best known running time of O(n log n) for the uniformly random scheduler (p = 1), we are able to present a smooth transition between a running time of O(n polylog n) for p = 1 and an infinite running time for the adversarial scheduler (p = 0), where the problem cannot be solved. The key technical contribution of our work is a novel phase clock algorithm for our model. This is a key primitive for much-studied fundamental population protocol algorithms (leader election, majority), and we believe it is of independent interest.

BibTeX - Entry

@InProceedings{schwartzman_et_al:LIPIcs.DISC.2021.34,
  author =	{Schwartzman, Gregory and Sudo, Yuichi},
  title =	{{Smoothed Analysis of Population Protocols}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{34:1--34:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14836},
  URN =		{urn:nbn:de:0030-drops-148362},
  doi =		{10.4230/LIPIcs.DISC.2021.34},
  annote =	{Keywords: Population protocols, Smoothed analysis, Leader election}
}

Keywords: Population protocols, Smoothed analysis, Leader election
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

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