arXiv:2611.06178 · v1

Efficient Stable Word-RAM Simulation by Population Protocols

首次提交 2026-11-04 16:57

版本更新 2026-11-04 16:57

雷达观测 2026-11-05 11:10

摘要

Population protocols model computation by indistinguishable agents interacting in uniformly random pairs, with unary inputs and outputs encoded by state counts. Efficiency requires polylogarithmically many states and polylogarithmic stabilisation time, measured as interactions divided by population size $n$. Stability requires eventual stabilisation to the correct output with probability $1$; silence requires that no agent changes state after stabilisation. Fast stable leader election and majority in leaderless populations require growing state spaces. Despite progress on individual problems, the general computational power of efficient stable protocols remains largely unexplored. We show that it extends beyond semilinear predicates, which characterise constant-state stable computation. We give an efficient, stable, and silent simulation of every $\mathcal{P}$-program: a word-RAM program with running time and number of registers polynomial in $w=Θ(\log n)$. Stabilisation takes polylogarithmic time both in expectation and with high probability. The framework supports general word-oriented computations, including multiple outputs. The construction extends MC$+$ protocols, fast Monte Carlo protocols whose failures are eventually detected as anomalies, and the system of weights. MC$+$ majority comparisons against the weights convert unary inputs into binary registers, with one agent per bit. MC$+$ operations on individual bits emulate RAM instructions, after which outputs are converted back to unary. A detected anomaly triggers a new universal rank-based backup that stabilises correctly and silently. These results open a systematic study of computational power and resource trade-offs, including extensions to external or spatial data.