Approximate Majority With Catalytic Inputs

Talley Amir, James Aspnes, John Lazarsfeld

Abstract

Population protocols are a class of algorithms for modeling distributed computation in networks of finite-state 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: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents, 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 = \Theta(n)$, we show that computing the exact majority of the input population with high probability requires at least $\Omega(n^2)$ 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 third-state dynamics of Angluin et al. for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in $O(n \log n)$ total steps w.h.p. when the input margin is $\Omega(\sqrt{n \log n})$. We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by Alistarh et al. 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 $\beta \leq O\left(\sqrt{n \log n}/n\right)$, exhibiting a resilience to leaks similar to that of Byzantine agents in previous works.

Introduction

In distributed computing, population protocols model how collections of simple, anonymous, finite-state agents—such as molecules in a test tube or sensors in a network—compute global properties through random pairwise interactions. A classic problem in this domain is Majority: given a population starting in states $X$ or $Y$, can the agents eventually agree on which state was initially more prevalent?

Standard models typically assume every agent can change its state. However, real-world chemical systems often involve catalysts—molecules that trigger changes in others while remaining unchanged themselves. This paper formalizes the Catalytic Input (CI) model, consisting of $n$ catalytic input agents (fixed states) and $m$ worker agents (flexible states), to investigate how these "stubborn" agents influence computational power and resilience to noise.

Methods and Protocol Design

The authors introduce the DBAM-C Protocol, an adaptation of the "Double-B Approximate Majority" (DBAM) protocol for the CI model. In this framework, worker agents transition between states $X$, $Y$, and an "undecided" state $B$.

Reaction rules for the standard DBAM protocol (left) and the adapted DBAM-C protocol for the Catalytic Input model (middle and right).

As shown in the reaction rules above, when $X$ and $Y$ workers meet, they both become undecided ($B$). When an undecided worker meets a decided agent—either another worker or a catalytic input ($I_X$ or $I_Y$)—it adopts that agent's state. To analyze these dynamics, the authors utilize an information-theoretic "Super CI" model and random walk analysis, employing martingales and Chernoff bounds to track the population's progress toward consensus.

Key Results

The Price of Persistence

A primary finding is a "strong separation" between models: while exact majority is solved quickly in standard models ($O(n \text{ polylog } n)$), it requires at least $\Omega(n^2)$ interactions in the CI model. The presence of catalysts makes the final convergence of the last few agents significantly more difficult.

Efficiency of Approximate Majority

Despite the difficulty of exact calculation, approximate majority remains highly efficient. The DBAM-C protocol reaches consensus in $O(n \log n)$ interactions, provided the initial margin between $X$ and $Y$ inputs is at least $\Omega(\sqrt{n \log n})$.

The protocol exhibits remarkable resilience to leaks (spontaneous, noisy state changes). The authors prove a formal equivalence between random leaks and Byzantine agents: a system facing a leak rate $\beta \leq O(\sqrt{n \log n}/n)$ behaves asymptotically the same as a system containing a proportional number of strategically malicious agents. This demonstrates that these distributed chemical-like systems are naturally robust to both stochastic noise and adversarial behavior.

Conclusion

The Catalytic Input model provides a bridge between theoretical population protocols and practical chemical computing. While the persistence of catalysts slows down exact computation, the efficiency and robustness of approximate majority suggest that these systems are well-suited for stable, noise-tolerant distributed tasks. Future research may explore the behavior of the model when the number of catalysts is sub-linear or investigate the computation of more complex predicates beyond majority.

Summary updated

Abstract

Population protocols are a class of algorithms for modeling distributed computation in networks of finite-state 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: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents, 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 = \Theta(n)$, we show that computing the exact majority of the input population with high probability requires at least $\Omega(n^2)$ 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 third-state dynamics of Angluin et al. for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in $O(n \log n)$ total steps w.h.p. when the input margin is $\Omega(\sqrt{n \log n})$. We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by Alistarh et al. 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 $\beta \leq O\left(\sqrt{n \log n}/n\right)$, exhibiting a resilience to leaks similar to that of Byzantine agents in previous works.
BibTeX
@inproceedings{amir2020approximate,
  author = {Talley Amir and James Aspnes and John Lazarsfeld},
  title = {{Approximate Majority With Catalytic Inputs}},
  booktitle = {OPODIS},
  year = {2020},
  url = {https://openreview.net/forum?id=hCD9mYZBbiX},
}
Figure