Approximate Majority with Catalytic Inputs

Talley Amir, James Aspnes, John Lazarsfeld

TL;DR

This paper explores distributed computation in chemical-inspired population protocols featuring catalytic inputs (immutable input agents) and transient leaks (spontaneous state corruptions). The authors prove that catalytic inputs impose an $\Omega(n^2)$ lower bound on computing parity—demonstrating a sharp separation from standard population protocols—yet show that approximate majority can still be computed in optimal $O(n \log n)$ time using simple three-state dynamics that are inherently robust against both leaks and Byzantine agents.

What Problem Does This Paper Address?

Population protocols model distributed computation among simple, anonymous, finite-state agents that interact in pairs under a random scheduler. Originally conceived for sensor networks, they are widely used to study chemical reaction networks (CRNs) and DNA strand displacement.

However, real molecular systems deviate from abstract models in two major ways:

  1. Catalysts: Molecules that trigger state transitions without altering their own state (persistent inputs).
  2. Leaks: Low-probability spontaneous reactions that occur without a catalyst.

The authors formally study these mechanisms through the Catalytic Input (CI) model ($n$ read-only input catalysts and $m$ mutable worker agents) and investigate whether fast, robust consensus—specifically approximate majority—is achievable when inputs are unchangeable and interactions are prone to noisy "leaks."

Methods

  • The Super CI Model & Yao's Principle: To establish information-theoretic lower bounds, the authors reduce the CI model to a single, computationally unbounded "super-agent" interacting with the catalysts. Under uniform priors, an interaction acts as sampling with replacement, allowing minimax arguments (Yao’s principle) and binomial tail bounds to lower-bound the sample complexity for parity and majority.
  • DBAM-C Protocol: The authors extend standard three-state dynamics (undecided-state dynamics: $X+B \to 2X$, $Y+B \to 2Y$, $X+Y \to 2B$) with catalytic rules: $I_X + B \to I_X + X$ and $I_Y + B \to I_Y + Y$. Workers can convert blanks to their opinion or cancel opposing opinions, but inputs remain intact.
  • Random Walk & Martingale Analysis: Tracking progress measures $\hat{x} = x + b/2$, $\hat{y} = y + b/2$, and opinion gap $P = \epsilon + \hat{x} - \hat{y}$ through a multi-stage, coupled one-dimensional random walk to bound convergence time.
  • Adversarial Leak Analysis: Leaks are modeled pessimistically as $X \to Y$ (the worst-case distortion against the majority). The authors prove tolerance bounds by balancing non-leak progress against adversarial drift.

Datasets

Not discussed in the paper. The work is primarily theoretical, supplemented by numerical simulations of the DBAM-C protocol with population sizes up to $N = 15{,}000$ to empirically evaluate convergence times and sample error rates under varying leak probabilities ($\beta$).

Key Insights and Ideas

  • Computational Separation via Sampling Limits: In standard population protocols, agents can erase or aggregate input tokens, allowing exact parity in $O(\text{polylog } n)$ parallel time. In the CI model, workers cannot mark visited catalysts; every encounter is a sample with replacement. Consequently, determining parity or exact majority requires distinguishing $p = \frac{1}{2} \pm \frac{1}{2n}$, which fundamentally demands $\Omega(n^2)$ samples.
  • Approximate Majority Remains Fast: While exact consensus is slow, approximate majority does not suffer from this penalty. If the margin between majority and minority inputs is $\Omega(\sqrt{n \log n})$, catalytic three-state dynamics reach complete consensus in $O(n \log n)$ total steps.
  • Duality Between Leaks and Byzantine Faults: The paper shows a formal equivalence in third-state dynamics: experiencing a transient leak rate $\beta$ at every interaction step has the exact same asymptotic impact on error rate and run time as injecting $B = O(\beta N)$ permanently malicious Byzantine agents.

Key Results

  • Parity Lower Bound: Computing input parity with high probability requires $\Omega(N^2)$ total interactions when $m = \Theta(n)$.
  • Input Margin Bound: Any CI protocol converging in $O(N \log N)$ total steps requires an initial margin of at least $\Omega(\sqrt{N})$.
  • DBAM-C Convergence: For $m = \Theta(n)$ and initial margin $\epsilon \ge \Omega(\sqrt{N \log N})$, DBAM-C reaches correct consensus in $O(N \log N)$ steps with high probability ($1 - N^{-c}$), showing the $\Omega(\sqrt{N})$ bound is tight up to a $O(\sqrt{\log N})$ factor.
  • Leak Robustness: Both standard DBAM and DBAM-C tolerate leak rates up to $\beta \le O(\frac{\sqrt{n \log n}}{n})$, achieving a residual sample error of $O(\log n / n)$ for small $\beta$, or $O(\beta)$ for larger $\beta$, within $O(n \log n)$ total interactions.

Limitations and Future Work

  • Input Proportions: Fast convergence proofs currently require the worker population to be at least a constant fraction of the inputs ($m \ge n/10$ or $m = \Theta(n)$). Settings where $m \ll n$ or $n \ll m$ remain partially open.
  • Non-Self-Stabilizing: Unlike some logarithmic-state comparison protocols (e.g., Alistarh et al., 2020), DBAM-C is constant-state and cannot dynamically recover if input majorities change post-convergence.
  • Open Directions: Identifying what other non-trivial predicates can be evaluated in sub-quadratic time within the CI model, and characterizing which general classes of population protocols possess intrinsic robustness to transient leak noise.

Summary updated

Abstract

Population protocols [Dana Angluin et al., 2006] 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 [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 third-state 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 constant-state 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 third-state 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
@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},
}

Loading related content...

Figure