AI & ML
Efficient Stable Word-RAM Simulation by Population Protocols
arXiv cs.DC0 views
arXiv:2611.06178v1 Announce Type: new 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=\Theta(\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.
Source:https://arxiv.org/abs/2611.06178PreviousCARE-FL: Federated Fine-Tuning of Multimodal LLMs in Resource-Constrained Edge NetworksNextChiron: Cache Management Empowered by LLM Intelligence for AI Workloads
Related posts
Scalable Source Selection for Machine Learning Tasks
0arXiv cs.DB
AvalancheBench: Evaluating Enterprise Agent-Driven Semantic Query Processing Through Latent World Recovery
0arXiv cs.DB
ConStruM: A Structure-Guided LLM Framework for Context-Aware Schema Matching
0arXiv cs.DB
From Certified Pairs to a Certified Hub: Reasoner-Checked Crosswalks for the Information Exchange Standard
0arXiv cs.DB
A Comparative Study of Importance Attribution to Columns in Deep Learning over Relational Databases
0arXiv cs.DB
Community Search under Member-Specific Tolerances
0arXiv cs.DB