2026-10-20T13:55:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14836 2024-03-06T09:54:58Z ddc:004 open_access

Smoothed Analysis of Population Protocols Schwartzman, Gregory Sudo, Yuichi Population protocols Smoothed analysis Leader election 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gregory Schwartzman and Yuichi Sudo 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.34 urn:nbn:de:0030-drops-148362 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.34 eng https://creativecommons.org/licenses/by/4.0/legalcode