arXiv preprint ·
Efficient Stable Word-RAM Simulation by Population Protocols
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Distributed & Parallel Computing
CHARM+: Cross-Hardware Attention with Re-Merge Multistream Mechanism
KOSMOS: Self-scheduling Persistent Kernels for Communication-Compute Overlap
A Controlled Experimental Evaluation of Configuration and Cache Architecture in LLM Serving Engines
ZYFA: Speed and Accuracy of FP8 FlashAttention on AMD CDNA4
Shallow Encoding Emits Deep Memories
Get the few papers worth your time in Distributed & Parallel Computing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.