Abstract
Population protocols [Dana Angluin et al., 2006] are a class of algorithms for modeling distributed computation in networks of finitestate agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistentstate agents (or catalysts) and spontaneous state changes (or leaks).
Based on models considered in recent protocols for populations with persistentstate agents [Bartlomiej Dudek and Adrian Kosowski, 2018; Alistarh et al., 2017; Dan Alistarh et al., 2020], we assume a population with n catalytic input agents and m worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For m = Θ(n), we show that computing the parity of the input population with high probability requires at least Ω(n²) total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple thirdstate dynamics [Angluin et al., 2008; Perron et al., 2009] for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constantstate protocol for the CI model that solves approximate majority in O(n log n) total steps with high probability when the input margin is Ω(√{n log n}).
We then show the robustness of thirdstate dynamics protocols to the transient leaks events introduced by [Alistarh et al., 2017; Dan Alistarh et al., 2020]. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability β ≤ O(√{n log n}/n). The resilience of these dynamics to leaks exhibits similarities to previous work involving Byzantine agents, and we define and prove a notion of equivalence between the two.
BibTeX  Entry
@InProceedings{amir_et_al:LIPIcs:2021:13504,
author = {Talley Amir and James Aspnes and John Lazarsfeld},
title = {{Approximate Majority with Catalytic Inputs}},
booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
pages = {19:119:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771764},
ISSN = {18688969},
year = {2021},
volume = {184},
editor = {Quentin Bramas and Rotem Oshman and Paolo Romano},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13504},
URN = {urn:nbn:de:0030drops135040},
doi = {10.4230/LIPIcs.OPODIS.2020.19},
annote = {Keywords: population protocols, approximate majority, catalysts, leaks, lower bound}
}
Keywords: 

population protocols, approximate majority, catalysts, leaks, lower bound 
Collection: 

24th International Conference on Principles of Distributed Systems (OPODIS 2020) 
Issue Date: 

2021 
Date of publication: 

25.01.2021 