Efficient Stable Word-RAM Simulation by Population Protocols

Efficient Stable Word-RAM Simulation by Population Protocols Leszek Gąsieniec1 , Tytus Grodzicki2 , and Grzegorz Stachowiak2

arXiv:2611.06178v1 [cs.DC] 4 Nov 2026

1

School of Computer Science and Informatics, University of Liverpool 2 Institute of Computer Science, University of Wrocław

Abstract The population protocol model studies computation by simple, indistinguishable agents whose states evolve through pairwise interactions. We consider the standard probabilistic variant, in which each interacting pair is selected uniformly at random. Inputs and outputs are represented in unary by the numbers of agents in designated states. Complexity is measured by the size of the state space and the stabilisation time, defined as the number of interactions until stabilisation divided by the population size n. A protocol is efficient if both measures are polylogarithmic in n, stable if it eventually stabilises to the correct output with probability 1, and silent if no agent changes state after stabilisation. For fundamental problems such as leader election and majority, fast stable protocols in leaderless populations require a number of states that grows with n. Despite substantial progress on these and other individual problems, including population size estimation, parity, and congruence, the general computational power of efficient stable population protocols remains largely unexplored. We show that efficient stable population computation extends beyond individual problems and beyond the semilinear predicates, which characterise stable computation in the constant-state model. We develop a general framework for simulating P-programs: word-RAM programs whose running time and number of registers are polynomial in the word length w = Θ(log n). Our main result gives an efficient, stable, and silent simulation of every such program using only probabilistically scheduled pairwise interactions, with polylogarithmic stabilisation time both in expectation and with high probability (Theorem 1). The framework supports general wordoriented computations, including multiple outputs, and is not restricted to decision problems. These results open a systematic study of efficient stable population protocols: their computational power, resource trade-offs, and extensions to external or spatial data. Our construction extends the MC+ protocols and system of weights introduced recently. MC+ protocols are fast Monte Carlo protocols whose failures, called anomalies, are eventually detected. Using MC+ majority comparisons against the weights, the protocol converts unary inputs into binary registers, with each bit stored in an individual agent. It maintains and manipulates these registers, directly emulating each RAM instruction through MC+ operations on single bits, before converting the binary outputs back to unary. If an anomaly is detected, it switches to a new universal rank-based backup that simulates the program stably and silently.

1

Introduction

The population protocol model [AAD+ 06] studies computation by populations of simple, indistinguishable entities, called agents, that communicate through pairwise interactions. Each agent stores a single state from a prescribed state space, and an interaction changes the states of the participating agents according to a common deterministic transition function. The initial configuration encodes the input, while the computation is required to stabilise in a configuration representing the solution. We consider the standard probabilistic variant, in which a random scheduler selects an ordered pair of distinct agents, called the initiator and the responder, uniformly at random at each step. The sequential time is the number of interactions until stabilisation, whereas the parallel time, or simply the time, is the sequential time divided by the population size n. We call a protocol efficient if it uses a polylogarithmic number of states and stabilises in polylogarithmic time. A protocol is stable if it eventually stabilises to the correct output with probability 1, and silent if no agent changes state after stabilisation. An event occurs with high probability (whp) if its probability is at least 1 − n−η for any prescribed constant η > 0, with the protocol constants chosen accordingly. Its complement has negligible probability. All logarithms are to base 2. Our simulation is stable and silent, with polylogarithmic stabilisation time both in expectation and whp. We write a transition as A + B −→ A′ + B ′ , meaning that an interaction between an initiator in state A and a responder in state B changes their states to A′ and B ′ , respectively. Some of our protocols use compound states: an agent state is a tuple of components from sets S1 , . . . , Sk , giving the full state space S1 × · · · × Sk .

1.1

Related Work and Results

Population protocols have been studied from two complementary perspectives: which behaviours and predicates emerge from local rules, and how scheduling, state space, agent capabilities, time, and computational power interact. We primarily adopt the latter perspective, seeking general computations that are simultaneously efficient, stable, and silent. Computational power of the classical model. In the original model [AAD+ 06], the state space and transition function are independent of n. Under uniformly random interactions, these protocols can simulate whp counter machines with a constant number of O(n)-bounded unary counters represented by state multiplicities. Under unary encoding, predicates computable with bounded error lie in P and admit randomised logarithmic-space simulations with exponential running time [AAD+ 06]. The stably computable predicates are exactly the semilinear predicates, equivalently those definable in Presburger arithmetic [AAE06, AAER07]. In the closely related model of chemical reaction networks, the stably computable functions are exactly those with semilinear graphs [CDS14]. These characterisations do not imply efficient stabilisation. With a constant number of states, stable leader election [DS15] and broad classes of predicates and functions under leaderless initialisation [BDS17] require Ω(n) expected time. For monotone protocol families, leader election and majority require Ω(n/ polylog n) expected time with at most 12 log log n states [AAE+ 17]. Under the additional output-dominance assumption, majority in expected time O(n1−c ), for any fixed c > 0, requires Ω(log n) states [AAG18]. Our growing state spaces support efficient stable computation beyond the semilinear predicates that characterise constant-state stable computation. Fast stable primitives. Basic coordination tasks become efficiently solvable when the number of states grows slowly with n. The first efficient leader-election protocol was given in [AG15], and the number of states was reduced in [BCER17] and then to the optimal O(log log n) in [GS18], with O(log2 n) time whp. Further work [BKKO18, GSU19, SOI+ 20] culminated in [BGK20], with Θ(log log n) states and optimal O(log n) expected time. 1

For exact majority, early fast protocols [AGV15, BCER17] were followed by an O(log n)state, O(log2 n)-time protocol based on a new leaderless phase clock [AAG18]. Further improvements [BEF+ 21, BNKKP20] culminated in the stable protocol of [DEG+ 21], using O(log n) states and optimal O(log n) expected time. With a sufficiently large initial majority margin, approximate majority can be solved in O(log n) time whp using only three states [AAE08b]. Efficient stable protocols for parity and congruence were obtained only recently [GGJ+ 26]. Fast primitives have also been extended to graphical population protocols, where interactions follow an underlying graph: leader election and exact majority on regular graphs, with overhead depending on conductance [AGR22]; near-optimal stable leader election on general graphs [ARV22]; and space-efficient exact majority on general graphs [RSSV26]. Our simulation assumes a complete graph; extending it to these interaction graphs remains open. Many of these protocols use the one-way epidemic process [AAE08a], whose agents are either susceptible (0) or infected (1), with transition (x, y) → (x, max{x, y}). Lemma 1 (Lemma 2 in [AAE08a]). Starting from a single infected agent, the epidemic reaches all agents in Θ(log n) time whp. This dissemination primitive underlies phase clocks and many fast leader-election and majority protocols; see [GKL+ 25] for a k-contact generalisation. Another key ingredient of these protocols is synchronisation. Phase clocks coordinate successive stages of computation, typically allowing Θ(log n) time for epidemic dissemination. Given a leader or a suitably sized junta, constant-state clocks [AAE08a, GS21] can be nested to measure any fixed polylogarithmic duration. Leaderless constructions use Θ(log n) states, including fixed-resolution clocks [DEG+ 21] and clocks based on the power-of-two-choices process [AAG18]. A different leader-based construction measures Θ(n log n) time whp using a constant number of states [GSS23]. We combine MC+ leader election and majority [GGJ+ 26], whose failures are eventually detected, with epidemics and a leader-based clock to simulate general programs; faster MC+ primitives could sharpen our bounds. Fast protocols also support counting and computing proportions [MAA+ 15, MAS16]. Uniform population-size estimation has also been studied [DE19], including stable protocols that compute either ⌊log n⌋ or ⌈log n⌉ in O(log2 n) time whp [BKR19]; see also [DE21] for a survey of counting. Our simulation assumes known w = Θ(log n); stable size estimation may help remove this assumption. Fast register-machine and program simulations. A close predecessor is the register-machine simulation in [AAE08a]. Given an initial leader, it simulates a machine with a constant number of registers whp, supporting comparison, addition, subtraction, and multiplication or division by constants, with O(log2 n) time per operation after initialisation. The same machinery simulates a logarithmic-space Turing machine. The registers are represented by state multiplicities, rather than explicit binary words, and the general simulation permits a small probability of error. A separate construction in the same work guarantees correct convergence with probability 1 for semilinear predicates. In stochastic chemical reaction networks, a fixed finite reaction network can perform universal computation with arbitrarily small error probability and polynomial slowdown [SCWB08]. The framework of [KU18] uses nested phase clocks and composition to support a restricted imperative language with loops and branching. Every semilinear predicate admits a constant-state protocol with expected polylogarithmic convergence time and high-probability correctness. Its always-correct variants achieve expected O(nε ) convergence time for any fixed ε > 0, with a constant number of states depending on ε, or retain polylogarithmic convergence time using O(log log n) states. These guarantees concern convergence; the always-correct constructions are not silent as 2

presented. Convergence concerns the realised execution; stabilisation rules out every reachable output change. With growing state spaces, we simulate general word-RAM programs on binary registers, combining probability-one correctness and silence with polylogarithmic time in expectation and whp. Presburger computation and succinct protocols. For a quantifier-free Presburger formula of size m as defined in [CGHE24], succinct protocols [BEG+ 20] reduce exponential state complexity to poly(m), at the cost of exponential expected time, as observed in [CGHE24]. Using population computers as an intermediate formalism, the construction of [CGHE24] achieves O(m) states and O(m7 n) expected time for n = Ω(m). Linear time is worst-case optimal for leaderless constant-state protocols, whose predicates are semilinear. For leaderless stable protocols, we propose a relaxed notion of succinctness allowing poly(m) · poly log n states, which our framework achieves with silent stabilisation (Section 5). Expressive power with growing state spaces. Uniform protocols with o(log n) states still decide only semilinear predicates [AAER07, CMN+ 11], whereas protocols with f (n) ∈ Ω(n) states capture NSPACE(n log f (n)) under unary encoding [CMN+ 11]. For the intermediate range, under the constructibility and uniformity assumptions of [CFG25], for f (n) ∈ Ω(log n)∩O(n1−ε ) and fixed ε > 0, uniform and weakly uniform protocols with Θ(f (n)) states decide exactly the predicates whose unary encodings lie in NSPACE(f (n) log n). The construction simulates space-bounded nondeterministic machines through leader-driven counter machines and restarts, potentially providing a backup. The characterisation ensures correctness under fairness, leaving random-scheduler time and silence unanalysed; our word-RAM backup supplies polynomial expected time and silence. Simulating population protocols. Under the uniformity assumptions above, polylogarithmically many states permit only predicates in NSPACE(polylog n), even without a time bound. A complementary time bound follows by simulating protocols on conventional machines, provided their descriptions can be generated in poly(w) time. A randomised w-RAM stores one O(w)-bit count per state and samples interactions. For a silent protocol with expected polylogarithmic stabilisation time, it detects termination by checking every feasible pair of states for a transition that changes either agent’s state. Since w = Θ(log n), the expected number of interactions is n polylog n. They can be simulated by a Las Vegas algorithm using poly(w) space and expected 2O(w) time. Batched simulations [BHK+ 20, HP26] reduce the amortised cost per interaction, but do not by themselves yield a general poly(w)-time simulation. With binary counts as RAM inputs, our poly(w)-time source computations leave a gap to this expected exponential-time reverse simulation; narrowing it remains open. More powerful extensions of population protocols. Several extensions strengthen agent resources or communication. Community protocols [GR09] give agents unique identifiers and allow them to remember a constant number of identifiers, capturing symmetric predicates in NSPACE(n log n). Homonym protocols [BCR18] allow shared identifiers; with the model’s identifier operations, polylogarithmically many distinct identifiers suffice to simulate Turing machines using polylogarithmic space. PALOMA [CMN+ 11] gives agents logarithmic local memory and captures the same class as community protocols. Broadcast consensus protocols capture unary predicates in NL [BEJ19]. The simulation of [CJ21] emulates a randomised logarithmic-space Turing machine of expected running time T in expected O(n log n · T ) interactions. Clocked population protocols [Asp21] provide an idealised signal that sufficient time for convergence has elapsed; absence detectors [MS15] test whether a specified state is absent; and selective population protocols [GGJ+ 24] strengthen partner selection. Our simulation retains anonymous agents and uniformly random pairwise interactions, without these additional capabilities. 3

Complexity-theoretic perspective. Stochastic well-structured transition systems [Asp25] encompass population protocols, chemical reaction networks, and gossip models. Their clocks stop or advance too quickly after polynomially many expected steps, and explicitly terminating computations finish or fail in expected polynomial time. Under bounded-error termination semantics, the unaugmented models capture the symmetric languages in BPL. These fixed-state results concern bounded-error termination; our construction uses polylogarithmically many states and clock rounds, with a clock-independent backup ensuring probability-one correctness. Stability, silence, and the MC+ paradigm. Stable computation guarantees an eventually correct, unchanging output; silence additionally forbids subsequent state changes. The class of well-specified strongly silent protocols introduced in [BEJM21] preserves the classical expressive power and supports more tractable automatic verification. Silence is natural for machine simulation: once the program terminates and its output is decoded, no clock or synchronisation mechanism should continue modifying the population. The framework in [GGJ+ 26] combines MC+ protocols and population weights. A fast probabilistic computation detects violations of its correctness conditions within polynomial expected time. These violations, called anomalies, are absent whp; when one is detected, the protocol switches to an always-correct backup. This yielded efficient, stable, and silent protocols for parity and congruence. We extend this framework to general word-RAM simulation, reducing the leader’s clock component after initialisation by Θ(log n), creating weights in one round, and providing unary–binary conversions for multiple inputs and outputs. Our contribution. The preceding results leave a gap between fast but Monte Carlo register-machine simulations with O(1) registers, efficient stable protocols for individual problems, characterisations of growing-state protocols without time bounds, and machine simulations available only in stronger variants of the model. We close part of this gap and thereby address the time-bounded expressive power of growing-state protocols, identified as an open problem in [CFG25]. We consider P-programs (Definition 1): w-RAM programs whose running time and number of registers are polynomial in w = Θ(log n), which halt on every admissible input and initialise each working register before its first read. Our main result gives an efficient, stable, and silent simulation of every such program, with polylogarithmic time both in expectation and whp (Theorem 1), and thus a lower bound on the computational power of efficient stable protocols. The simulation supports general word-oriented computations, including multiple numerical outputs, and thus contributes to the study of computation beyond agreement identified in [AR09]. Applications include functions with non-semilinear graphs, such as products of input counts when the result fits the prescribed output range. Section 5 discusses further applications and extensions: succinct protocols for quantifier-free Presburger formulas, following [CGHE24], and a possible extension to expected-polynomial-time Las Vegas computations. We retain the unary input and output representation standard for population protocols, while RAM instructions operate on binary words. Our main technical contribution is an MC+ implementation of the entire fast computation (Section 3), including unary–binary conversion and the maintenance and modification of binary registers. Majority comparisons against the population weights convert unary inputs into binary registers, each represented by w agents, one per bit. The protocol emulates each RAM instruction through O(w) atomic subroutines that read or write individual bits, then converts the binary outputs back to unary form. If an anomaly is detected, a novel rank-based backup simulates the program stably and silently in expected O(n2 w) time (Section 4). Together, the MC+ computation and backup guarantee correct silent stabilisation with probability 1, using polylogarithmically many states.

4

2

Model and Simulation Overview

Population protocols represent numerical inputs and outputs in unary: input Ai is represented by a set Xi of |Xi | = Ai agents, and output Bi by a set Yi of |Yi | = Bi agents. Outputs need not be Boolean; leader election, for example, produces a singleton output set. Values can be as large as the population size n, so their binary representations have logarithmic length. The word-RAM [CR73, FW90], with w = Θ(log n), therefore matches their scale and provides a standard model of general-purpose computation in which to establish efficient, stable, and silent population simulation. The w-RAM model. The basic parameter of the w-RAM model is its word length w. More specifically, (1) its instruction set is based on the Cook–Reckhow model [CR73] (Table 1), (2) each input and output value is a non-negative (w − 1)-bit integer, and (3) registers store signed w-bit words in two’s-complement (U2) encoding. Arithmetic is performed modulo 2w . The first six instructions listed in Table 1 are referred to as RAM instructions, whereas READ and PRINT are referred to as input/output instructions. Instruction LOAD(C, rd) ADD(rs1, rs2, rd) SUB(rs1, rs2, rd) COPY(i, rp, d, rd) COPY(d, rs, i, rp) JGE(r, Iz) READ(rd) PRINT(rs)

Description C → rd: load an integer constant C into register rd [rs1] + [rs2] → rd: load the sum of the values in rs1, rs2 into rd [rs1] − [rs2] → rd: load the difference of the values in rs1, rs2 into rd [[rp]] → rd: load the value of the register pointed to by rp into rd [rs] → [[rp]]: store the value of rs in the register pointed to by rp if [r] ≥ 0, jump to instruction Iz; otherwise continue read the next input value into register rd output the value of register rs

Table 1: Instructions of the Cook–Reckhow RAM model.∗ A w-RAM program is a finite sequence of instructions from Table 1. Its execution is controlled by an instruction pointer ip, which by default advances to the next instruction and may be modified explicitly by a conditional jump JGE. Input and output are handled by the corresponding input/output instructions. The execution terminates when ip reaches the end of the program. Although the number of registers in the standard word-RAM model is not usually fixed in advance, in this paper we restrict our attention to w-RAM programs whose memory consists of poly(w) registers, identified with their indices 0, 1, . . . , ρ − 1. † More precisely, the class of programs considered in this paper is captured by the following definition of P-programs. Definition 1 (P-programs). A w-RAM program is called a P-program if it satisfies the following properties: 1. the total number of instructions executed during its runtime is at most T = TR + TRAM + TP = poly(w), where TR and TP denote the numbers of executed READ and PRINT instructions, and TRAM is an upper bound on the number of executed RAM instructions; ∗

The square brackets [·] denote the value stored in a register. A program using sparse addresses can be transformed to this form by storing the addresses in use in a binary trie, which increases its running time by a factor polynomial in w. †

5

2. the program uses ρ = O(T ) = poly(w) registers, indexed from 0 to ρ − 1; 3. on every admissible tuple of TR input values, the program halts within these bounds, reads exactly TR values, and produces exactly TP non-negative outputs smaller than 2w−1 ; 4. on every execution, each working register is written before its first read, including a read used for indirect addressing, and every direct or indirect register access lies in {0, . . . , ρ − 1}. These requirements also apply to the partial input counts used during backup retries. The program therefore restarts independently of old working-register contents; its registers are disjoint from the arrays and auxiliary registers added by the simulation. We take TRAM ≥ 1, increasing this upper bound if necessary. This class encompasses a broad range of computations. Thus, the ability to simulate it shows that silently stabilising population protocols can efficiently solve a wide range of computational problems. Establishing this result is the main contribution of this paper, as stated in Theorem 1. Population size and data representation. Each input and output variable is represented in unary. For a given P-program, the simulation uses a distinct input state for each input variable and a distinct output state for each output variable, namely Sin = {in1 , . . . , inTR }, Sout = {out1 , . . . , outTP }, so that |Sin | + |Sout | = TR + TP = poly(w). Each input and output set has fewer than 2w−1 agents. In contrast, the w-RAM model uses binary representations of numbers, which we also found convenient for simulating w-RAM computations. Our simulation therefore converts the input values from unary to binary before emulating the P-program, and converts the final output values back to unary after the computation has been completed. Thus, the external input and output remain in unary form, while all intermediate computations use binary representations. The input values are stored in an input array of TR registers, and the results are collected in an output array of TP registers before being converted to unary. Together with O(1) auxiliary registers, the total number of registers in the simulation is therefore ρ′ = ρ + TR + TP + O(1) = poly(w). The total binary input length is O(TR w) and need not equal w. During the simulation, the population must accommodate the unary input and output values, the system of weights, which consists of 2w−1 − 1 agents (see Subsection 3.3), and the ρ′ w agents – each representing one bit of a register. In addition, a constant fraction of all agents should remain free and form the working set, which allows the epidemic-based computations to
run fast. For these reasons, the simulation uses a population of size nw = C (TR + TP + 1)2w + ρ′ w , where C > 1 is a fixed integer constant. The non-free roles are input, output, weight and register agents, the leader and, in the backup, a helper. A single simulation uses fewer than nw /C such agents. Fact 1. For n ≥ nw , at least (1 − 1/C)n agents are free whenever only one simulation’s auxiliary roles are present, subject to the prescribed register and output bounds. This covers successful MC+ executions and the final backup after lower-ranked auxiliary states have been reclaimed. Since TR , TP , and ρ′ are poly(w), the following relations hold. Fact 2. We have log nw = w + O(log w) = Θ(w) and, in particular, log nw < 2w for all sufficiently large w. For sufficiently large w, all ρ′ = poly(w) register addresses fit in non-negative w-bit words. Our main result is the following theorem. Theorem 1. Every P-program admits an efficient simulation by a silently stabilising probabilistic population protocol. For all sufficiently large w and population size nw , the simulation sta
bilises, both in expectation
and with high probability, in O w2 (TR w + TRAM + TP ) time, using O ρ′ w2 (TR w + TRAM + TP ) states. 6

Proof. By Theorem 3, there is an efficient MC+ simulation protocol that completes whp in O(w (TR w + TRAM + TP )) rounds, each lasting Θ(log n) = Θ(w)
time, plus one register initialisation round of O(ρ′ w) time, and uses O ρ′ w2 (TR w + TRAM + TP ) states. By Theorem 8, there is a silently stabilising backup simulation protocol with expected time O(n2 w) using O(ρ′ w2 ) states. The fast protocol has a fixed round budget and retains anomaly checks through terminal verification. Subsection 3.3 gives a polynomial bound D(n) on the expected remaining time, from any reachable configuration, to completion or detected failure followed by switching and backup. Thus, for the high-probability bound A = O(ρ′ w + w2 (TR w + TRAM + TP )), choosing the failure exponent η sufficiently large gives expected time at most A + n−η D(n) = O(A). By Theorem 2(ii), the one-way combination is therefore stable and silent, with the same time bound whp. Its disjoint fast and backup state sets give the stated state bound. Finally, ρ′ = O(T ) and T ≤ TR w + TRAM + TP , so register initialisation is absorbed in the stated time bound. The protocol requires the P-program, its word length w, and the parameters TR , TRAM , TP , and ρ. The analysis uses only w = Θ(log n), which holds for n = nw by Fact 2. It therefore applies without change to every population size n ≥ nw with log n = Θ(w), since additional agents are free and only increase the working set; the constants in the subprotocol durations depend on the constant hidden in log n = Θ(w). For significantly larger populations, the simulation remains efficient and stable provided that it is also given a constant-factor upper bound on log n for timing its subprotocols. In the remainder of this section, we present the components and techniques common to both variants of the simulation.

2.1

General Simulation Scheme

Each P-program simulation, whether the efficient MC+ simulation or the stable backup, follows the same high-level scheme, illustrated in Figure 1. Leader election

Register initialisation

Unary input to binary

Instruction emulation

Binary output to unary

Figure 1: High-level structure of the P-program simulation. 2.1.1

The Leader

Both simulations begin with leader election. The leader coordinates every subsequent stage: initialising the registers, converting unary inputs to binary in the input array, acting as the processor during instruction emulation, and converting the results in the output array back to unary. The simulated P-program has fixed length, with execution determined by its input. Its code, including constants and direct register addresses, is encoded in the transition function. The leader maintains an instruction pointer ip and coordinates the emulation of the current instruction. The fixed code requires only O(1) states for ip and its direct addresses (Example 1, page 7). After the last instruction, ip is set to END. The following example illustrates how an instruction of the program, determined by the leader’s ip, is realised by transition rules that additionally depend on auxiliary state components. Example 1. Suppose that register r is represented by a single agent storing its value, that instruction 7 sets this value to □, and that the update requires the leader and the register agent to share an

7

auxiliary component, say the colour red. Since r and □ are determined by ip, the leader does not store them; the transition function contains the rule (L; red; ip=7) + (r; red; v) → (L; red; ip=8) + (r; red; □), for every value v. Interactions in which the colours differ leave both agents unchanged.

2.1.2

Registers

Each of the ρ′ registers is represented by w distinct agents in states (R; r, i, b), where r ∈ {0, . . . , ρ′ −1} is the register address, i the bit index, and b its value. Both simulations use the same initialisation (Protocol 1, page 8): the leader assigns successive free agents to successive register bits, setting every bit to 0. Protocol 1 RegInit() Input: A unique leader, the free-agent bound of Fact 1, ρ′ , and w. Result: Initialised registers indexed by 0, 1, . . . , ρ′ − 1, each consisting of w bits. 1: function RegInit( ) 2: for r ← 0 to ρ′ − 1 do 3: for i ← 0 to w − 1 do 4: The leader assigns the i-th bit of register r to the first free agent it encounters: 5: L + φ → L + (R; r, i, 0). ▷ φ denotes a free agent The time and correctness guarantees are proved with Lemma 2 below. Lemma 2. Assuming a unique leader and the free-agent bound of Fact 1, Protocol 1 stably and silently initialises ρ′ registers of w bits each, in O(ρ′ w) time both in expectation and whp. Proof. Put M = ρ′ w and p = 1 − 1/C. Until allocation finishes, each interaction assigns the next bit with probability at least 2p/n. Its duration is therefore stochastically dominated by the time needed for M successes in Bernoulli trials with success probability 2p/n, giving expected time at most M/(2p) = O(M ). After dnM interactions, a Chernoff bound gives fewer than M successes with probability e−Ω(M ) = n−Ω(1) , for a sufficiently large constant d, since M ≥ w = Θ(log n). Every assignment removes its agent from the free set, so all register-bit agents are distinct. No allocation rule applies after the last assignment, giving stable and silent completion.

2.1.3

Input and Output Conversion

The i-th input variable, with value ki < 2w−1 , is given in unary by ki agents in state ini ; before emulating RAM instructions, the protocol converts it to binary and stores it in register riin of an input array occupying a fixed range of consecutive addresses, with an additional pointer register rpin . Every READ(rd) is replaced by COPY(i, rpin , d, rd), INC(rpin ) (INC increments a register, see Subsection 2.2), and analogously every PRINT(rs) by COPY(d, rs, i, rpout ), INC(rpout ), which writes to an output array r1out , . . . , rTout with pointer rpout ; the pointers are initialised by two LOAD P instructions as the arrays have fixed addresses. The resulting modified P-program still has fixed length, performs no input/output instructions and executes at most TRAM + 2(TR + TP ) + 2 RAM instructions; only after it has been emulated are the values in the output array converted from

8

binary to unary. Jump targets are adjusted to the expanded code. Within the modified program, only these trusted replacements access the reserved arrays. At each backup retry, the pointer loads are repeated, while the cumulative input array is preserved and the source program initialises its working registers. This preprocessing is essential for the backup. Conversions use a system of weights in the MC+ simulation and controlled rewriting rules in the backup; the full description follows below. The following paragraphs give the full description of the input and output conversion scheme used in both simulation variants. Before the actual simulation of the P-program, the protocol converts the input data from unary to binary. To store and access the converted input values, we use TR + 1 auxiliary registers: an input array r1in , r2in , . . . , rTinR and an additional register rpin containing a pointer to the next entry of the input array. The input array occupies a fixed range of consecutive addresses, with riin at its i-th position. The i-th integer input variable, with value ki < 2w−1 , is represented in unary by a subpopulation of ki agents in state ini . After the conversion, its binary representation is stored in register riin . Once all input data has been converted and stored in the input array, we replace every instruction READ(rd) of the P-program with the pair of instructions COPY(i, rpin , d, rd), INC(rpin ). The first copies the input-array entry pointed to by rpin into register rd, and the second advances the pointer. To make rpin initially point to the first entry of the input array, the modified program starts with LOAD(r1in , rpin ). The INC(r) instruction increments the value of register r by one; it is not an instruction of Table 1, but it is emulated in the same way as ADD, see Subsection 2.2. This preprocessing is essential for our backup simulation. Similarly, instead of performing binaryto-unary conversion on the fly during printing, we place the printed values in consecutive entries of the output array r1out , r2out , . . . , rTout , which also occupies a fixed range of consecutive addresses, P by replacing every instruction PRINT(rs) with COPY(d, rs, i, rpout ), INC(rpout ). Analogously, this requires TP + 1 auxiliary registers, including the pointer register rpout , which is initialised by LOAD(r1out , rpout ) at the start of the program. We thus obtain a RAM program, referred to as the modified P-program, that retrieves its data from the input array, processes it in binary, and stores the results in the output array. Its code is longer than that of the original program by one instruction per READ and PRINT instruction in the code, plus the two initial LOAD instructions, so it still has fixed length, and during its execution it performs no input/output instructions and at most TRAM + 2(TR + TP ) + 2 RAM instructions. Jump targets are updated to the corresponding expanded source instructions, beyond the initial pointer loads. Within the modified program, only the trusted replacements access the reserved arrays. On a backup retry, the cumulative input array is retained, the two pointer loads are repeated, and the source program initialises its working registers. Since every tentative input tuple is admissible, the program halts and overwrites all TP output entries. The computations of the modified program are emulated by a population protocol that operates between the creation of the input array and the conversion of the output array. Only after the entire modified program has been emulated are the values in the output array converted from binary to unary. This scheme is used in both the efficient MC+ simulation and the stable backup simulation. We use two mechanisms for conversion between unary and binary representations. The first is based on a system of weights and is employed in the efficient MC+ simulation. The second relies on controlled rewriting rules and is used in the stable and silent backup simulation.

9

2.1.4

State Organisation

Table 2, page 10, summarises the roles and state components described throughout the paper. We write (a|b) for either state a or state b. Only input agents have a permanent role, retaining their labels ini . All other agents are initially leaders; after election, all but one are free (φ), forming the working set. Free agents subsequently become register agents (R), output agents, weight agents (P , MC+ only), or helpers (H, backup only). Every agent also holds a clock component in MC+ or a rank in the backup. Role input (permanent role) leader (L) register (R) output free (φ) weight (P ) helper (H) every agent every agent

Components input state ini ip, register and bit index, O(1) memory (r, i, b): register index, bit index, bit value output state outi request/response components of GET/PUT weight index k of Pk counter of interactions with the leader clock component: round t, phase x rank

Used in both both both both MC+ MC+ backup MC+ backup

Table 2: Roles and main state components of agents. The input role is the only permanent one; the other roles are assigned to non-input agents during the computation.

2.2

RAM Instruction Emulation

A key feature of our construction is that the emulation of every RAM instruction reduces to two atomic subroutines, GET and PUT (see Table 3). The reductions are identical in the MC+ and backup simulations: both are coordinated by the leader and differ only in their implementations of these subroutines. Subroutine PUT(r, i, b) GET(r, i)

Description sets the i-th bit of register r to b returns the value of the i-th bit of register r Table 3: Atomic subroutines.

Atomic subroutines PUT and GET. In MC+, each atomic access completes correctly whp in one round; otherwise, an anomaly is signalled (Protocols 11 and 12). In the backup, the leader directly accesses the designated register-bit agent, guaranteeing correctness in O(n) expected time (Protocols 17 and 18). This modularisation leaves the higher-level instruction logic identical, with correctness following from that of the atomic accesses. Their detailed analyses appear in Subsections 3.4 and 4.4. The leader maintains an instruction pointer ip indicating the current instruction, and emulates the program step by step using the reductions below. Unless ip is explicitly modified by an instruction, the leader increments it by 1 after completing the instruction. We first present the most involved reduction, that of the copy instructions: for indirect addressing, the leader must retrieve a register address from a register and store it in its state, which contributes a factor O(ρ′ w) to the number of leader and working set agents states, whereas the remaining reductions, given below, require only O(w) additional leader states. 10

Indirect and direct copy COPY(·). To implement both Cook–Reckhow variants of the copy instruction, we first reduce them to two simpler subroutines: SET(r, rp) and the direct COPY(rs, rd). The former obtains the value stored in register rp by successive GET(rp, i) subroutines and stores it in the leader’s state as the register index r, while the latter performs a direct copy of the contents of register rs into register rd. The address bound is amax = ρ for source instructions and amax = ρ′ for trusted input/output wrappers, as determined by the fixed control context. SET checks all w bits and rejects an index outside {0, . . . , amax − 1}, including a negative word. An InvalidAddress outcome aborts the request: it signals an MC+ anomaly or suspends the current backup instance while its priority rank rules remain active. It cannot occur in a correct execution under Definition 1. The partial index is stored only below amax , so this check uses O(ρ′ ) index states. Protocol 2 SET(r, rp) Input: rp: register; r: leader’s index Result: Valid r = [rp], or InvalidAddress 1: function SET(r, rp) 2: r←0 3: for i ← 0 to w − 1 do 4: b ← GET(rp, i) 5: if b = 1 and r + 2i ≥ amax then 6: return InvalidAddress 7: r ← r + 2i b

Protocol 3 COPY(rs, rd) Input: rs, rd: registers Result: [rd] = [rs] 1: function COPY(rs, rd) 2: for i ← 0 to w − 1 do 3: b ← GET(rs, i) 4: PUT(rd, i, b)

Using these two building blocks, the instructions COPY(i, rp, d, rd) and COPY(d, rs, i, rp) (Protocols 4 and 5, page 11) are decomposed into two parts: first obtaining the indirect source or destination register index with SET(r, rp), and then performing a direct copy. Here we give the pseudocode of the reductions of COPY(i, rp, d, rd) and COPY(d, rs, i, rp). Protocol 4 COPY(i, rp, d, rd) Input: rp, rd - pointers to registers, i, d - indirect/direct flags Result: Register rd stores the contents of register r = [rp] 1: function COPY(i, rp, d, rd) 2: SET(r, rp) 3: COPY(r, rd)

Protocol 5 COPY(d, rs, i, rp) Input: rs, rp - pointers to registers, i, d - indirect/direct flags Result: Register r = [rp] stores the contents of register rs 1: function COPY(d, rs, i, rp) 2: SET(r, rp) 3: COPY(rs, r) Further instruction reductions. The following paragraphs give the remaining reductions of the RAM instructions to the atomic subroutines PUT and GET. The leader maintains an instruction pointer ip indicating the instruction currently being executed, and emulates the program step by step using the reductions below. Unless ip is explicitly modified by an instruction, the leader increments it by 1 after completing the instruction.

11

Conditional jump JGE(r, Iz). The conditional jump instruction is reduced to a single call to GET(r, w − 1), which retrieves the most significant bit of register r. Since values are represented in U2 encoding, this bit determines the sign of the stored value: if it is 0, the value is non-negative. In this case, the jump is taken and the leader updates the instruction pointer to the target instruction Iz; otherwise, it proceeds to the next instruction ip + 1. The Cook-Reckhow model [CR73] instead tests whether the register content is positive; each test is expressible by the other with O(1) instructions. Protocol 6 JGE(r, Iz) Input: r - pointer to a register, Iz - program instruction index Result: Jump to instruction Iz if the content of r is non-negative 1: function JGE(r, Iz) 2: b ← GET(r, w − 1) 3: if b = 0 then ip ← Iz Loading a constant into a register LOAD(C, rd). Let c0 , c1 , . . . , cw−1 be the complete w-bit U2 representation of a predefined constant C, encoded in the transition function, ordered from the least to the most significant bit. The reduction for the LOAD(C, rd) instruction assigns the value C to register rd bit by bit, where in each iteration i the agent representing the i-th bit of rd adopts value ci via PUT(rd, i, ci ). Constants independent of w need only a fixed number of bits in the program code and the transition function; for larger w, they are extended by copies of the sign bit. Protocol 7 LOAD(C, rd) Input: C = c0 . . . cw−1 - a constant in U2, rd - pointer to a register Result: Register rd contains the value C 1: function LOAD(C, rd) 2: for i ← 0 to w − 1 do 3: PUT(rd, i, ci ) Addition and subtraction ADD(rs1, rs2, rd) and SUB(rs1, rs2, rd). Both instructions are emulated bit by bit: at each position, the leader retrieves the two source bits using GET, computes the result bit and the new carry locally, and writes the result bit using PUT. The final carry is discarded, so the operations are performed modulo 2w ; in particular, signed overflow wraps around, as is standard for U2 arithmetic. Protocol 8 ADD(rs1, rs2, rd) Input: rs1, rs2, rd - pointers to registers Result: Register rd stores the w-bit sum of the values of registers rs1, rs2 1: function ADD(rs1, rs2, rd) 2: carry ← 0 3: for i ← 0 to w − 1 do 4: b1 ← GET(rs1, i) 5: b2 ← GET(rs2, i) 6: b ← (b1 + b2 + carry) mod 2, carry ← ⌊(b1 + b2 + carry)/2⌋ 7: PUT(rd, i, b) Subtraction uses the U2 identity a − b = a + ¬b + 1.

12

Protocol 9 SUB(rs1, rs2, rd) Input: rs1, rs2, rd - pointers to registers Result: Register rd stores the w-bit difference of the values of registers rs1, rs2 1: function SUB(rs1, rs2, rd) 2: carry ← 1 3: for i ← 0 to w − 1 do 4: b1 ← GET(rs1, i) 5: b2 ← GET(rs2, i) 6: b ← (b1 + (1 − b2) + carry) mod 2, carry ← ⌊(b1 + (1 − b2) + carry)/2⌋ 7: PUT(rd, i, b) The atomic subroutines and the RAM instructions are also used outside the emulation of the program itself: in the conversions and as macros in other subprotocols. We also use the instructions INC(r) and DEC(r), which increase and decrease the content of register r by 1. They are emulated as ADD and SUB with the second operand replaced by the constant 1, encoded in the transition function, so each requires 2w atomic subroutines. Table 4 and Fact 3 summarise the reductions. Instruction JGE(r, Iz) LOAD(C, rd) COPY(i, rp, d, rd), COPY(d, rs, i, rp) ADD(rs1, rs2, rd), SUB(rs1, rs2, rd) INC(r), DEC(r)

Reduction read the sign bit write the w bits of C SET, then direct copy bitwise, with carry bitwise, with carry

Atomic subroutines 1 w ≤ 3w 3w 2w

Table 4: Reduction of RAM instructions to atomic subroutines. Fact 3. Emulation of each RAM instruction (including INC and DEC) requires the execution of at most 3w atomic subroutines GET() and PUT().

3

Efficient MC+ Simulation

3.1

Overview

The efficient simulation is an MC+ protocol [GGJ+ 26]: whp it is correct and terminates in poly(w) time; otherwise, it signals a protocol or clock anomaly. Two results of [GGJ+ 26] reduce the proof of Theorem 1 to building such a protocol from polylogarithmically many MC+ stages, following the scheme of Figure 1 and Protocol 10, and combining it with a silent backup. Theorem 2. [(i) Theorem 3 and (ii) Theorem 2 in [GGJ+ 26]] (i) The sequential composition of polylogarithmically many MC+ protocols is an MC+ protocol. (ii) An efficient MC+ protocol and a polynomial-time stable protocol for the same problem can be combined into a protocol that is both efficient and stable; if the stable protocol is silent, so is the combined one. Our MC+ protocol modifies the clock of [GGJ+ 26] and ends with a terminal verification round, performing all pending anomaly checks before the clock stops. The remainder of this section shows that it retains the properties required by Theorem 2(ii): every malfunction is eventually signalled, the expected time to completion or detection is polynomial from every reachable configuration, and

13

a correct execution becomes silent. We prove the following theorem, and all other claims of this section, below. Theorem 3. For every P-program, there exists an efficient MC+ population protocol that, whp, correctly simulates the program in τ = O(w (TR w + TRAM + TP )) rounds of Θ(w) time each, plus one register initialisation round lasting O(ρ′ w) time. The protocol uses O(ρ′ wτ ) = O(ρ′ w2 (TR w + TRAM + TP )) states. Besides leader election, adopted from [GGJ+ 26], the MC+ simulation rests on four techniques. (1) Bit access in one round. By Subsection 2.2, every RAM instruction reduces to at most 3w calls of PUT and GET, so it suffices to make a single bit access fast and anomaly-detecting. In the MC+ variants PUTe (r, i, b) and GETe (r, i), the leader opens a round with a request that spreads through the working set by an epidemic; the register agent (R; r, i, ·), which holds the i-th bit of register r, applies the update or, for GETe , starts a second epidemic that carries the bit back to the leader. Since the working set is a constant fraction of the population (Fact 1), both complete whp within one round; a register agent that has not processed a PUTe request, or a leader that has not received the requested bit, signals an anomaly (Lemma 4). Together with the address checks, these subroutines ensure correct instruction emulation in the absence of an anomaly, using at most 3w rounds per instruction (Lemma 5). (2) A cheaper clock. In [GGJ+ 26], rounds advance by counting leader interactions, which multiplies the leader’s states by Θ(log n) per round. We count interactions only during MC+ leader election (Θ(w) rounds, O(w2 ) states; Theorem 6). Register initialisation, whose duration O(ρ′ w) may exceed Θ(log n), then occupies a single long round, after which the protocol switches to the improved clock based on the phase-clock mechanism of [AAE08a] with a constant number of phases. Each round then costs O(1) states and lasts Θ(w) time, and whp contains an interval of Ω(log n) time in which all agents share the same round number (Theorem 5), which is what every single-round subprotocol relies on. (3) Weights in one round. Conversions use the system of weights: disjoint sets of agents P0 , . . . , Pw−2 with |Pk | = 2k , whose unions represent every value below 2w−1 . Since w is known, we replace the sequential O(log n)-round construction of [GGJ+ 26] by a parallel single-round one: a delegating agent hands mass 2k of Pk to a fresh agent for k = w − 2, . . . , 1, and every mass is halved with free agents until each agent holds unit mass. The process may be represented as a binary tree of depth at most w with fewer than n leaves, so a Chernoff and union bound give completion whp in one round, with Θ(w2 ) states (Lemma 3). (4) Conversion by binary search. Extending the parity computation of [GGJ+ 26] from one bit to retrieving all w bits, U2Bconversione (i) determines |Xi | bit by bit from the most significant one: it adds Pℓ to an auxiliary subpopulation Z and compares |Z| with |Xi | by the MC+ majority protocol (Theorem 7), keeping Pℓ and writing bit 1 if |Z| ≤ |Xi |, and otherwise removing it and writing 0; this takes O(w2 ) rounds per input variable (Lemma 6). The invariant is 0 ≤ |Xi | − |Z| < 2ℓ+1 before bit ℓ, initially ℓ = w − 2 and Z = ∅. The comparison and choice reduce the residual to [0, 2ℓ ); after bit 0 it is zero. The untouched sign bit remains 0 from register initialisation, so the stored word equals |Xi |. Conversely, each weight acts as a stamp: for each bit ℓ of riout equal to 1, every agent of Pℓ first adopts an additional component outi and then passes it to a free agent, so all 2ℓ copies are stamped in parallel and 2ℓ output agents are created in one round, while Pℓ is preserved for later use (Lemmas 7 and 8). Summing over the stages gives τ rounds, dominated by conversions and program emulation. The state bound O(ρ′ wτ ) comes from agents that must record a register index and a bit index in every round: the register agents, and the leader and working set while emulating RAM instructions with indirect addressing. Our technical refinement reduces this bound by a factor Θ(min(ρ′ , w)). 14

Theorem 4. The MC+ simulation of Theorem 3 can be implemented in the same number of rounds and with O((ρ′ + w) τ ) states. The key idea is a fixed schedule. We pad every instruction emulation and every output conversion to exactly 3w rounds, and every iteration of the input conversion to a fixed length; we call these segments passes. The instruction tag remains fixed throughout its pass, including padding; the updated instruction pointer takes effect in the next pass. The bit index of every atomic subroutine call is then a function of the round, so the leader and the working set may store only a register index, i.e., O(ρ′ ) states per round. Register agents, whose identities (r, i, b) alone take Θ(ρ′ w) states, instead count coarse-grained rounds, one per pass of at least w rounds, and keep an O(1)-size status locating the current round relative to the at most three rounds of the pass in which their bit can be accessed. They update it from their partners’ exact rounds, checking pending obligations and skipped active rounds before each update and on termination, so failure detection is preserved. Since there are only O(τ /w) passes, register agents use O(ρ′ τ ) states. Combining Theorem 4 with the backup of Section 4 via Theorem 2(ii) improves the state bound of Theorem 1 accordingly.

3.2

Simulation Scheme

The following subsections give the full description and proofs of the MC+ simulation outlined in Subsection 3.1. The fast simulation is an MC+ protocol [GGJ+ 26] composed of MC+ subprotocols that implement successive operations of the simulated P-program. It follows the scheme presented in Protocol 10. First, the MC+ leader election protocol is executed, after which the elected leader initialises all required registers (Subsection 3.3). Next, the leader initiates the MC+ weight creation protocol, which constructs disjoint subsets of agents of sizes 20 , 21 , . . . , 2w−2 , called weights (Subsection 3.3). Together with the MC+ majority protocol (Subsection 3.3), these weights enable the efficient conversion of the input values from unary to binary, with the resulting values stored bit by bit in the input array registers (Subsection 3.5). The RAM instructions are then emulated according to the reductions described in Subsection 2.2, using the MC+ variants of the atomic subroutines GET and PUT (Subsection 3.4). Finally, the values stored in the output array are converted from binary to unary using the weights, yielding the output of the simulation and the program (Subsection 3.5). The MC+ simulation produces the correct output whp in poly(w) = poly log n time and uses poly(w) states, with both bounds depending on the running time and space usage of the simulated P-program. With negligible probability, an anomaly may occur; when it is detected, the protocol switches to the slower but stable backup simulation described in Section 4. The fast execution is bounded even on faulty histories. We pad the modified program’s execution to T ∗ = TRAM + 2(TR + TP ) + 2 instruction slots, using 3w rounds per slot and idle rounds after the program halts. A program that has not halted by the last slot signals an anomaly. Input-conversion branches and output conversions are also padded to fixed lengths, as detailed in the refined state analysis. Thus the round schedule has a prescribed finite endpoint determined by the parameters, and an instruction-slot index is determined by the round rather than stored separately. After the last output round, the leader initiates a terminal verification round. Every agent performs all pending end-of-round and skipped-round checks before adopting the terminal state. The terminal marker continues to propagate, but the clock no longer advances; outstanding anomaly witnesses and the rule detecting two leaders are retained. This adds only a constant number of rounds and ensures that stopping the computation cannot suppress an anomaly. 15

Protocol 10 MC+ Simulation Protocol Input: A modified P-program; T = TR + TRAM + TP , ρ′ , w; a leaderless population of n agents Result: Correct simulation of the given program whp, or an eventual Anomaly signal otherwise 1: function MC+ Simulation 2: LeaderElection 3: RegInit(ρ′ , w) 4: WeightCreation(w) 5: for i ← 1 to TR do 6: U2Bconversione (i) ▷ unary-to-binary conversion of i-th input 7: ip ← 0 8: for each of the T ∗ prescribed instruction slots do 9: if ip ̸= END then 10: Emulate the RAM instruction indicated by ip and update ip. 11: Pad the slot with idle rounds to a total of 3w rounds. 12: if ip ̸= END then signal Anomaly 13: for i ← 1 to TP do 14: B2Uconversione (i) ▷ binary-to-unary conversion of i-th output 15: Enter the terminal verification round and stop advancing the clock. In the remainder of this section, we develop the techniques needed to establish the following theorem on efficient MC+ simulation. The proof of the theorem is provided in Subsection 3.6. Theorem 3. For every P-program, there exists an efficient MC+ population protocol that, whp, correctly simulates the program in τ = O(w (TR w + TRAM + TP )) rounds of Θ(w) time each, plus one register initialisation round lasting O(ρ′ w) time. The protocol uses O(ρ′ wτ ) = O(ρ′ w2 (TR w + TRAM + TP )) states.

3.3

MC+ Protocols: Overview and Refinements

MC+ protocols were introduced in [GGJ+ 26]. They are fast Monte Carlo population protocols that execute correctly whp in poly(log n) time and additionally guarantee that any malfunction is eventually signalled by an anomaly. MC+ protocols facilitate the modular design of complex computations in population protocols, as compositions of MC+ protocols are themselves MC+ protocols. Each subprotocol uses a clocking mechanism to track a prescribed polylogarithmic number of consecutive computation rounds, after which it becomes silent, provided that no anomaly occurs. This allows subprotocols to be executed sequentially, with each building on the results of its predecessors. If all subprotocols execute correctly, their composition also produces the correct result. If a subprotocol malfunctions, an event of negligible probability, detection of the resulting anomaly triggers a switch to the stable backup. We distinguish two types of anomalies: 1. a protocol anomaly, arising from a failure of the subprotocol’s own computation; 2. a clock anomaly, detected when interacting agents have round numbers that differ by more than one, or when a post-election leader encounters a fine-clock follower with a later timestamp. Clock An essential component of an MC+ protocol is a clock that organises the computation into successive rounds. Each round lasts Θ(log n) = Θ(w) time whp. In the original MC+ construction [GGJ+ 26], rounds advance by counting leader interactions, which increases the number of leader states by a factor of Θ(log n).

16

We propose to employ a refined clock. In our construction, interaction counting is used to advance rounds only during leader election. Immediately afterwards, the registers are initialised in a single long round (see page 20). Once initialisation is complete, the protocol switches to a clock based on the phase-clock mechanism of [AAE08a]. By Theorem 1 of [AAE08a], this mechanism can provide intervals of length Θ(log n) whp, with an arbitrarily large constant lower bound on their duration. We implement the clock using a constant number m of phases. Each agent has a clock component of the form (L|F, t, x), where L and F denote a leader and a follower, respectively, t is the current round, and x ∈ {1, . . . , m} is the current phase. The clock transitions are as follows, where ⋆ denotes either L or F : (⋆, t, x) + (F, t, y) → (⋆, t, x) + (F, t, x),

if y < x,

(⋆, t + 1, x) + (F, t, y) → (⋆, t + 1, x) + (F, t + 1, x), (L, t, x) + (F, t, x) → (L, t, x + 1) + (F, t, x),

if x < m,

(L, t, m) + (F, t, m) → (L, t + 1, 1) + (F, t, m), (⋆, t′ , x) + (⋆, t, y) → clock Anomaly,

if |t′ − t| > 1.

After leader election, the following additional check has priority in both interaction orientations: if a leader meets a fine-clock follower whose timestamp (t′ , y) is lexicographically later than the leader’s (t, x), it signals a clock anomaly. In a correctly initialised unique-leader execution, the leader creates every new timestamp, so this check never fires. It uses only the existing clock fields and prevents an inherited clock discrepancy from leaving the unique leader unable to advance. Combining Theorem 1 of [AAE08a] with its epidemic propagation bound yields the following guarantee. Theorem 5. For any fixed constants a, c, η > 0, there exist constants m and D, depending only on a, c, η, such that the following holds for all sufficiently large n. Starting from the standard phase-clock initialisation with a unique leader, with probability at least 1 − n−η , each of the first na rounds lasts at most D log n time and contains an interval of at least c log n time during which all agents have the same round number. We also need a bound outside the high-probability event. With a unique leader, an ahead-ofleader follower triggers the additional check in expected time O(n). Otherwise, any phase advance is enabled after at most two specified leader–follower interactions: the first brings that follower to the leader’s phase, and the second advances the leader. Each such interaction has expected waiting time O(n). If an intervening discrepancy signals an anomaly, the fast execution stops earlier. Since the number of phases per round is constant and the round budget is finite, completing the clock or detecting an anomaly has a polynomial expected residual time, uniformly over reachable configurations. Every leader that starts register allocation retains its post-election leader flag until fallback. A subsequent interaction with any other leader or election candidate, including one still completing election, signals an anomaly. The expected time until such an anomaly is detected or no other candidate remains is O(n). Once no other candidate remains, only one allocation has created auxiliary roles, so Fact 1 applies and the remaining allocations take expected time O(ρ′ w) by Lemma 2. Thus register allocation also has a uniform polynomial expected residual bound. Terminal propagation executes pending checks before their evidence can be overwritten. Consequently, if A = O(ρ′ w + τ log n) is a high-probability bound for successful completion of the fast simulation and D(n) = nO(1) bounds the expected remaining detection, switching, and backup time from any reachable configuration, then E[stabilisation time] ≤ A + n−η D(n) = O(A), 17

by choosing the failure exponent η larger than the fixed degree in D. This is the expected-time accounting required by the MC+ combination theorem below; eventual detection alone would not suffice. The following theorems, formulated and proved in [GGJ+ 26], form the foundation of the MC+ simulation. Theorem 2(ii) establishes that an efficient MC+ protocol can be combined with a stable backup to obtain an efficient and stable population protocol. Theorem 2(i) establishes that MC+ protocols can be composed to create more complex protocols that are themselves MC+. Theorem 2. [(i) Theorem 3 and (ii) Theorem 2 in [GGJ+ 26]] (i) The sequential composition of polylogarithmically many MC+ protocols is an MC+ protocol. (ii) An efficient MC+ protocol and a polynomial-time stable protocol for the same problem can be combined into a protocol that is both efficient and stable; if the stable protocol is silent, so is the combined one. We next describe the MC+ protocols from [GGJ+ 26] that we adapt for the simulation. The leader election and majority protocols require only minor modifications, whereas our weight creation protocol is substantially simpler and completes in fewer rounds than the original construction. MC+ Leader Election The simulation begins with the MC+ leader election protocol of [GGJ+ 26], which is based on a scheme used in several prior works [AAE08a, GS21, BGK20]. It operates over Θ(log n) rounds and is designed so that all leaders cannot disappear, as this would cause the clock to stop. In our simulation, the number of rounds is set to a sufficiently large constant multiple of w. In successive rounds, the potential leaders perform coin tosses using randomness supplied by the scheduler. If at least one potential leader obtains heads in a round, those obtaining tails become followers. Each outcome is associated with its round number, ensuring that at least one leader persists. Although more efficient leader election protocols exist, adapting one to the MC+ variant would not improve the overall asymptotic complexity of our simulation. With negligible probability, more than one leader remains after the prescribed rounds. Since subsequent MC+ subprotocols assume a unique leader, this may lead to an incorrect computation. To detect this case, any subsequent interaction between two leaders signals an anomaly. Such an interaction occurs eventually with probability 1, and the expected time until it occurs is O(n). Theorem 6. There exists an MC+ leader election protocol that elects a unique leader whp in Θ(log n) = Θ(w) rounds and uses O(log2 n) = O(w2 ) states. Proof. Correctness and round complexity follow from Theorem 4 of [GGJ+ 26] and the relation w = Θ(log n). The state bound accounts for the clock that counts leader interactions. This clock requires Θ(log n) = Θ(w) states per round for the leader. MC+ Weight Creation We now describe the MC+ protocol for creating the system of weights: pairwise disjoint sets of agents P0 , P1 , . . . , Pw−2 , where |Pi | = 2i . Together, these sets contain 2w−1 − 1 agents, allowing unions of weights to represent every integer from 0 to 2w−1 − 1, that is, every non-negative w-bit value. The weights support both the conversion of unary input values to binary representations in registers and the final conversion of binary output values back to unary. The word length w, and hence the required number of weights, is known in advance. This allows us to propose a simpler and faster construction than the one in [GGJ+ 26]. Whereas that protocol creates weights sequentially over O(log n) rounds, ours creates all w − 1 weights in a single round. The protocol WeightCreation(w) is initiated by the leader. In its first interaction with a free agent, the leader delegates the creation of all weights by assigning that agent state p∗ (w − 2). The

18

subsequent weight creation process is governed by the following transitions: p∗ (k) + φ → p∗ (k − 1) + pk (k),

for k > 1,

∗

p (1) + φ → p0 (0) + p1 (1),

(1) (2)

pk (i) + φ → pk (i − 1) + pk (i − 1),

for i > 0.

(3)

We say that an agent in state pk (i) holds mass 2i belonging to weight Pk . The total mass of Pk is 2k , initially held by a single agent in state pk (k). This mass is repeatedly split until it is distributed among 2k agents, each holding unit mass. The agent in state p∗ (k) is responsible for initiating the creation of Pk , Pk−1 , . . . , P0 . When k > 1, an interaction with a free agent assigns the entire mass 2k of Pk to that agent, which adopts state pk (k), according to rule (1). At the same time the delegating agent adopts state p∗ (k − 1) and continues with the remaining weights. Rule (2) completes this delegation process by initiating P1 and creating P0 . Thus, the creation of weights is initiated while the previously assigned masses are being split. Within each weight Pk , splitting proceeds according to rule (3). An agent in state pk (i) with i > 0 divides its mass equally with a free agent, leaving both in state pk (i − 1). The process ends when all agents in Pk hold unit mass, that is, when they are in state pk (0). All w − 1 weights are created whp in one round. Labelling the created weights requires w = Θ(log n) states. With negligible probability, the protocol signals an anomaly if, upon entering the next round, the leader failed to delegate the creation of weights or some follower remains in state pk (i) or p∗ (i), for i > 0 and k ∈ {1, . . . , w − 2}. In the absence of an anomaly, the result of the protocol is the family of sets Pk for k = 0, . . . , w − 2, where Pk consists of agents in state pk (0). Lemma 3. The protocol WeightCreation(w) correctly creates weights P0 , P1 , . . . , Pw−2 whp in one round and signals an Anomaly otherwise. It uses Θ(w2 ) states. Proof. We follow the approach of [GGJ+ 26]. By the choice of population size, at least (1 − 1/C)n agents remain free throughout the construction. Consequently, conditional on a specified active agent being selected as initiator, the probability that its partner is free is at least 1 − 1/C. After the leader’s initial delegation, the construction can be represented by a binary tree rooted at p∗ (w − 2). A delegation step branches into the construction of the current weight and the delegation of the remaining weights; a splitting step branches into two equal masses belonging to P k w−1 − 1 leaves, corresponding to the final unit-mass the same weight. The tree has w−2 k=0 2 = 2 agents, and every root-to-leaf path has at most w − 1 edges. Including the leader’s initial delegation adds at most one transition to each path. Fix a path that is not yet complete. Its next transition occurs when the agent responsible for that transition has an interaction with a free agent. Conditional on the execution history, this happens in an interaction with probability at least (1 − 1/C)/n. Hence, over cn log n interactions, progress along the path is bounded below by a binomial process of mean (1 − 1/C)c log n, until the path is complete. Since w = Θ(log n), a Chernoff bound shows that the probability of completing fewer than the required w transitions is at most n−η−1 for a sufficiently large constant c. A union bound over the fewer than n root-to-leaf paths shows that all weights are created whp in O(log n) time. If the construction does not finish, an unfinished delegation or splitting state remains and triggers an anomaly. Finally, the states p∗ (k) and pk (i), with 0 ≤ i ≤ k < w, require Θ(w2 ) states. MC+ Majority Let A and B be two subpopulations of a population of n agents. The majority problem is to determine whether |A| > |B|, |A| < |B|, or |A| = |B|. The MC+ majority protocol [GGJ+ 26] employed in this work uses the standard operations of cancelling, in which two agents with opposite biases become unbiased, and splitting, in which a biased agent and an unbiased agent 19

become two agents with the same bias. These operations double the remaining bias over successive phases. The protocol runs for Θ(log n) rounds, producing the correct answer whp and signalling an anomaly otherwise. In our simulation, the number of rounds is set to a sufficiently large constant multiple of w. Apart from the clock, the protocol requires only O(1) additional states per agent. We believe that the best-known majority protocol [DEG+ 21], with O(log n) expected stabilisation time, could be adapted to the MC+ setting so that it operates in a constant number of rounds. Such an adaptation would improve the complexity of our construction by reducing the time required for input conversion by a logarithmic factor. We leave the development of such a protocol as an open problem, as determining whether such an adaptation is feasible, and constructing it if so, would introduce significant technical complications into the presentation of this work. Theorem 7. There exists an MC+ majority protocol that executes correctly whp in Θ(log n) = Θ(w) rounds and uses Θ(log n) = Θ(w) states. Proof. Correctness and round complexity follow from Theorem 6 of [GGJ+ 26] and the relation w = Θ(log n). The computation requires only O(1) additional states per round [GGJ+ 26]. At this stage, the clock uses O(1) states per round, so tracking the Θ(w) rounds requires Θ(w) states in total. Register Initialisation The leader participates in an average of two interactions per unit of time. By Lemma 2, initialising ρ′ = poly(log n) registers takes O(ρ′ w) time both in expectation and whp, and succeeds with probability 1. We therefore allocate a single long round immediately after leader election for this process. Unlike an ordinary round, its duration is determined by completion of RegInit and may exceed Θ(log n). During register initialisation, the improved-clock components keep their standard initial values; once allocation is complete, the leader increments the round number by 1 and activates this clock, leaving the allocated registers unchanged, and the simulation continues with rounds of logarithmic duration.

3.4

MC+ Emulation of RAM Instructions

In this subsection, we introduce efficient MC+ variants, PUTe and GETe , of the atomic subroutines PUT and GET. These subroutines allow every RAM instruction to be emulated by an MC+ protocol via reductions of Subsection 2.2. We assume that a leader has been elected and that all required registers have been initialised. The request and response states described below are additional state components; agents retain their register assignments and other persistent information. The PUTe (rd, i, b) subroutine (Protocol 11) completes successfully whp within one round. At the beginning of the round, the leader adopts a state component indicating that the i-th bit of register rd is to be set to b. Every free agent in this round subsequently adopts the same component via epidemic process. When a register agent enters the round, it adopts the state component (put). This component is cleared once the agent determines whether it holds the bit to be updated and, if so, performs the required change. If a register agent has not determined by the end of the round whether it is responsible for updating the bit, it signals an Anomaly.

20

Protocol 11 PUTe (rd, i, b) Input: rd - register pointer, i - bit index, b ∈ {0, 1} Result: The i-th bit of register rd is set to b 1: function PUTe (rd, i, b) 2: The leader adopts component (put, rd, i, b) at the start of round t. 3: upon entering round t a follower adopts component (put), 4: if both agents are in round t then 5: (φ; put) + (φ|L; put, rd, i, b) → (φ; put, rd, i, b) + (φ|L; put, rd, i, b), 6: (R; put, rd, i, b′ ) + (φ; put, rd, i, b) → (R; rd, i, b) + (φ; put, rd, i, b). 7: if both agents are in round t and (rd′ , i′ ) ̸= (rd, i) then 8: (R; put, rd′ , i′ , b′ ) + (φ; put, rd, i, b) → (R; rd′ , i′ , b′ ) + (φ; put, rd, i, b). 9: if a register agent still holds component (put) at the end of round t then 10: signal Anomaly The GETe (rs, i) subroutine (Protocol 12) also completes successfully whp within one round. At the beginning of the round, the leader adopts the component (get, rs, i, ?), requesting the value of the i-th bit of register rs, and propagates this request among the working set agents via an epidemic process. When a working set agent interacts with the agent storing the requested bit, it initiates a second epidemic process that propagates the bit value to the other agents, eventually to the leader, during the remainder of the round. The leader signals an Anomaly if it does not receive the requested bit by the end of the round. Protocol 12 GETe (rs, i) Input: rs - register pointer, i - bit index Result: The leader learns the i-th bit of register rs 1: function GETe (rs, i) 2: The leader adopts component (get, rs, i, ?) at the start of round t. 3: upon entering round t a follower adopts component (get). 4: if both agents are in round t then 5: (φ; get) + (φ|L; get, rs, i, z) → (φ; get, rs, i, z) + (φ|L; get, rs, i, z), 6: (R|φ; get, rs, i, b) + (φ|L; get, rs, i, ?) → (R|φ; get, rs, i, b) + (φ|L; get, rs, i, b). 7: if the leader still holds (get, rs, i, ?) at the end of round t then 8: signal Anomaly else return b Both MC+ subroutines may signal an anomaly with negligible probability. Together with the address validation in SET, their checks guarantee correct instruction emulation in the absence of an anomaly. Their behaviour is summarised by the following lemma. Lemma 4. The MC+ subprotocols PUTe and GETe complete correctly whp in one round; otherwise, an Anomaly is signalled. Proof. At the beginning of the round of the PUTe (rd, i, b) subroutine, the leader adopts the request component (put, rd, i, b). Each subsequent agent entering this round adopts the (put) component. The leader broadcasts the request (put, rd, i, b) to all free agents through an epidemic process. Since the free agents form a constant fraction of all agents, this epidemic reaches every one of them within O(log n) time whp. The register agents then verify within O(log n) time whp whether they hold the bit to be updated and, if so, set it to b. If a register agent fails to verify whether it is responsible

21

for the update by the end of the round, it signals an Anomaly. Thus, in the absence of such an anomaly or clock anomaly, the requested bit is set correctly. The GETe (rs, i) protocol begins with the leader adopting the request component (get, rs, i, ?) at the beginning of round t. Every follower entering round t subsequently adopts the (get) component. The leader broadcasts the request (get, rs, i, ?) to all free agents through an epidemic in time O(log n) whp. Consequently, the agent holding the i-th bit of the register rs also receives this request during round t whp by an interaction with a free agent. During the remainder of round t, the component (get, rs, i, b) spreads to all working set agents and the leader whp via a second epidemic process, also within time O(log n) whp. An Anomaly is signalled if the leader does not receive the requested bit value b by the end of round t. We conclude this subsection with a lemma showing that every RAM instruction can be efficiently emulated by an MC+ protocol. Lemma 5. For every RAM instruction, there exists an MC+ protocol that whp correctly emulates it in at most 3w rounds; otherwise, an Anomaly is signalled. The emulation requires O(ρ′ w) states per round for the leader and the agents in the working set. Proof. The reductions in Subsection 2.2 and Fact 3, together with Lemma 4 and Theorem 2(i), imply that each RAM instruction can be emulated by an MC+ protocol in at most 3w rounds. For an indirectly addressed register, the leader obtains its index using SET (Protocol 2). Since this index can identify any of the ρ′ registers, its representation together with the current bit index requires O(ρ′ w) states per round for the leader. The addresses of the remaining registers processed by the leader during this time appear explicitly in the program code and thus require only O(1) states. The agents in the working set also require O(ρ′ w) states per round to propagate requests.

3.5

MC+ Input and Output Conversion

As described in Subsection 2.1, the input values are converted from unary to binary and stored in the input array registers before the RAM instructions of the modified P-program are emulated. After the emulation, the values stored in the output array are converted back to unary to produce the protocol’s output. In this subsection we describe both conversions in the MC+ simulation. We assume that a leader has been elected, the registers have been initialised, and the system of weights has been created. Both conversions use this system of weights. Let Xi denote the subpopulation representing the i-th input variable, namely, the set of agents in state ini . Similarly, let Yi denote the subpopulation representing the i-th output variable, namely, the set of agents in state outi . We first describe input conversion (Protocol 13). The protocol builds on the mechanism used for parity computation in [GGJ+ 26], but recovers all bits of each input variable rather than only the least significant one, which determines parity. The input variables are processed one after another. To determine the binary representation of |Xi |, the protocol considers the weights in decreasing order, starting with Pw−2 . For each weight Pℓ , it adds that weight to an auxiliary subpopulation Z and uses the MC+ majority protocol to determine whether |Z| ≤ |Xi |. If the inequality holds, Pℓ remains in Z and the ℓ-th bit of |Xi | is set to 1. Otherwise, the weight is removed from Z and the bit is set to 0. Each bit is stored in the input array register riin using PUTe . Weights are added to and removed from Z using AddWeight and RemoveWeight, each of which completes whp within one round. The protocol AddWeight(ℓ) adds Pℓ to Z through a process initiated by the leader at the beginning of a new round. Each agent entering this round receives information indicating that this process is in progress. In particular, every agent in Pℓ 22

receives this information upon entering the round and joins Z. If an agent skips this round, a clock anomaly is signalled. The protocol RemoveWeight(ℓ) is analogous, except that agents in Pℓ leave Z, and Z ← ∅ is shorthand for a similar subprotocol that removes all weights from Z in one round. Thus, in the absence of a clock anomaly, these operations are performed correctly. Protocol 13 U2Bconversione (i) Input: i - input variable index Result: Input array register riin stores |Xi | in binary whp 1: function U2Bconversione (i) 2: Z←∅ 3: for ℓ ← w − 2 downto 0 do 4: AddWeight(ℓ) 5: Compare Xi and Z using Majority. 6: if |Xi | < |Z| then 7: RemoveWeight(ℓ) 8: PUTe (riin , ℓ, 0) 9: else 10: PUTe (riin , ℓ, 1)

▷ Add weight Pℓ to Z

▷ Remove weight Pℓ from Z

The conversion of a single input variable is summarised by the following lemma. Lemma 6. The protocol U2Bconversione (i) correctly converts the i-th input variable from unary to binary and stores its binary representation in riin whp within O(w log n) rounds, using O(1) additional states per round; otherwise, an Anomaly is signalled. Proof. Assume that all component operations execute correctly. The greedy invariant in the binary-search discussion of Section 3 proves that the value bits represent A = |Xi | < 2w−1 and the untouched sign bit is 0. Thus register riin stores the correct input value. There are w − 1 iterations, each using one majority comparison in O(log n) rounds and a constant number of single-round weight operations and bit writes. Including the initial clearing of Z gives O(w log n) rounds. Theorem 7, Lemma 4, and the weight-operation guarantees provide correctness whp and anomaly detection for each component. Theorem 2(i) gives the same guarantees for their sequential composition. The components’ additional state requirements remain O(1) per round. We now describe the conversion of the output array from binary to unary (Protocol 14). As with input conversion, the protocol processes the array sequentially, one entry at a time. To convert the value stored in the i-th output register riout , the protocol processes its bits one at a time. For bit ℓ, the leader first retrieves its value using GETe (riout , ℓ). If the bit is 1, the single-round protocol Out(ℓ, i) places 2ℓ additional agents in state outi . Protocol 14 B2Uconversione (i) Input: i – output variable index Result: A set Yi of agents in state outi encodes the i-th output value in unary 1: function B2Uconversione (i) 2: for ℓ ← 0 to w − 2 do 3: in round 2ℓ: b ← GETe (riout , ℓ) 4: if b = 1 then 5: in round 2ℓ + 1: Out(ℓ, i) 23

The protocol Out(ℓ, i) operates as follows (Protocol 15). It uses weight Pℓ of 2ℓ agents. Each agent in Pℓ adopts an additional component outi and transfers it to a free agent while retaining its weight label. This adds 2ℓ agents to the output subpopulation. After all bits of riout have been processed, the total number of agents in state outi equals the value stored in that register. Protocol 15 Out(ℓ, i) Input: ℓ – weight index; i – output variable index Result: 2ℓ additional agents enter state outi 1: function Out(ℓ, i) 2: upon entering round t: ▷ The protocol executes in one round 3: the leader adopts component (ℓ, i); 4: a free agent adopts component (ℓ, i); 5: an agent in Pℓ adopts component outi , giving (pℓ , outi ). 6: during round t: 7: (pℓ , outi ) + φ → pℓ + outi . ▷ φ denotes a free agent 8: upon entering round t + 1: 9: if an agent still has (pℓ , outi ) then signal Anomaly Lemma 7. The protocol Out(ℓ, i) correctly creates a subpopulation of 2ℓ agents in state outi whp in one round, otherwise an Anomaly is signalled. Proof. Let t be the round in which Out(ℓ, i) is executed. Each agent in Pℓ adopts an additional component outi upon entering round t. For the protocol to succeed, each such agent must interact with a free agent during this round and transfer outi to that agent. Throughout the protocol, at least (1 − C1 )n agents remain free and form the working set. Thus, for any agent in Pℓ with outi , the probability that a given interaction is initiated by this agent with a free agent as responder is 1− 1

at least nC . The phase clock ensures whp that all agents remain in round t for at least cn log n interactions. The probability that a particular agent retains outi while this common round lasts for at least cn log n interactions is at most 1 − C1 1− n

!cn log n

≤ e−(1− C )c log n ≤ n−(1− C )c . 1

1

A union bound over the agents in Pℓ gives a failure probability of at most |Pℓ | n−(1− C )c ≤ n−η , for any fixed η > 0, provided that c is sufficiently large. Failure therefore requires either a common round shorter than cn log n interactions or an unsuccessful transfer within its first cn log n interactions. Adding the phase clock’s failure probability to this bound yields the whp guarantee. 1

We conclude with a lemma on the binary-to-unary conversion of one output variable. Lemma 8. The protocol B2Uconversione (i) correctly converts the i-th output value stored in riout from binary to unary whp in 2w rounds, using O(1) additional states per round; otherwise, an Anomaly is signalled. ℓ w−1 . Initially, no agent belongs Proof. Write the admissible output value as B = w−2 ℓ=0 bℓ 2 < 2 to Yi . If the component operations execute correctly, then after processing bits 0, . . . , ℓ, the set Yi P contains exactly ℓj=0 bj 2j agents: the bit retrieval returns bℓ , and Out(ℓ, i) adds exactly 2ℓ agents

P

24

when this bit is 1, by Lemmas 4 and 7. The population bound supplies the required free agents throughout. Thus the final output count is B, including Yi = ∅ when B = 0. Each bit uses one retrieval round and at most one output round, giving at most 2(w − 1) < 2w rounds. The same lemmas and Theorem 2(i) give correctness whp and anomaly detection for the composition. Only the components’ O(1) additional states per round are needed.

3.6

MC+ Simulation Summary

We now combine the components developed in this section to prove Theorem 3, which establishes the existence of an efficient MC+ simulation for any given P-program. Proof of Theorem 3. We follow the scheme in Protocol 10. Each component is implemented by an MC+ protocol described above. Since the number of component invocations is polylogarithmic, their composition is also an MC+ protocol by Theorem 2(i). We first establish the round complexity. Leader election takes Θ(w) rounds whp by Theorem 6. Register initialisation occupies one long round of O(ρ′ w) time whp by Lemma 2. The system of w − 1 weights is then created whp in one round by Lemma 3. Next, each of the TR input values is converted from unary to binary and stored in the input array. By Lemma 6, each conversion takes O(w log n) = O(w2 ) rounds, giving O(TR w2 ) rounds in total. Emulating the modified P-program takes O(T w) rounds by Lemma 5. Finally, converting the TP output registers from binary to unary takes O(TP w) rounds by Lemma 8. Terminal verification adds a constant number of rounds. Thus, in addition to the long register-initialisation round, the total number of ordinary rounds is τ = O(w (TR w + TRAM + TP )) . We next establish the state complexity. Leader election uses O(w2 ) states by Theorem 6. After register initialisation, the phase-clock component uses only O(1) states per round by Theorem 5. Weight creation uses O(w2 ) states by Lemma 3. During subsequent computation, weight agents require O(wτ ) states to record their weight labels and the current round. Similarly, input agents require O(TR τ ) states and output agents require O(TP τ ) states. Register agents require O(ρ′ wτ ) states to record their register indices, bit indices, bit values, and the current round. The leader and the agents in the working set also require O(ρ′ wτ ) states. For all agents, it suffices to use only O(1) states per round for the remaining subprotocol-specific components. Since TR , TP ≤ ρ′ , the register-agent state bound dominates these contributions. Thus, the total number of states is   O(ρ′ wτ ) = O ρ′ w2 (TR w + TRAM + TP ) .

Refined state complexity of the MC+ simulation. With additional technical work, which exploits the fixed order in which register bits are accessed, the state bound of Theorem 3, and consequently that of Theorem 1, can be improved by a factor of Θ(min(ρ′ , w)). Theorem 4. The MC+ simulation of Theorem 3 can be implemented in the same number of rounds and with O((ρ′ + w) τ ) states. Proof. In the proof of Theorem 3, the state complexity O(ρ′ wτ ) comes from the leader, the working set agents, and the register agents. We first show, using three observations, that the leader and the working set need only O(ρ′ ) states per round. We then show that the register agents, whose identities alone require Θ(ρ′ w) states, need to count only O(τ /w) rounds.

25

Leader and working set agents. First, we fix the schedule of the simulation so that the bit index of every atomic subroutine call is determined by the round. By Lemma 5, emulating a RAM instruction requires at most 3w calls to atomic subroutines, each in separate round. If it requires fewer, we pad its emulation with idle rounds so that it occupies exactly 3w rounds. In U2Bconversione , the branch without RemoveWeight (line 9 of Protocol 13) is padded with one idle round, so that every iteration has the same number of rounds. The initial clearing of Z is included in the first iteration’s pass and, if necessary, padded to the same fixed pass length. Since leader election has a fixed number of rounds, and register initialisation and weight creation take one round each, the input conversion starts and ends at fixed rounds. Hence the indices of the input variable and of the bit are determined by the round number and the emulation of the RAM instructions also starts at a fixed round, depending only on w and TR . We also pad B2Uconversione , so that the round 2ℓ + 1 is idle if bit ℓ is 0, and the conversion of each output variable, which takes 2(w − 1) < 3w rounds, is padded to 3w rounds. We call each of these fixed-length segments a pass: an instruction slot or the conversion of one output variable, each of 3w rounds, or one iteration of an input conversion, of Θ(w) rounds. Execution is padded to all T ∗ instruction slots before output conversion begins. Every pass has at least w rounds and its boundaries are fixed in advance. The constant number of setup and terminal rounds use distinguished setup and terminal statuses. The bit index of each PUTe (rd, i, b) or GETe (rs, i) call is therefore determined by the position of the round within its pass and by the current instruction or conversion step, so the leader and the working set agents need no separate component for it. Second, register indices appearing explicitly in the instructions of the modified P-program require only O(1) states, since the program has fixed length. Third, for an indirectly addressed register, the leader obtains its index using SET (Protocol 2). Since this index may identify any of the ρ′ registers, its representation requires O(ρ′ ) states per round for the leader, and the agents in the working set also require O(ρ′ ) states per round to propagate requests involving this index. Similarly, during output conversion, the leader stores the index of the current output variable, which requires O(TP ) = O(ρ′ ) states. Hence the leader and the working set agents require only O(ρ′ τ ) states. Register agents. Register agents require a different argument: their identities (r, i, b) already account for Θ(ρ′ w) states, which cannot be reduced, so we instead reduce the number of round values they store. To this end, we exploit the fixed order in which the bits of each register are accessed. Instead of counting every round, each register agent in state (r, i, b) tracks coarse-grained rounds, which advance once per pass. It also stores the instruction emulated in the current pass, or a fixed tag for an idle or conversion pass, which requires only O(1) states, since the program has fixed length. The agent learns both from its interaction partners, whose states contain the current round and current instruction. The instruction tag remains fixed for the entire pass, including padding; an updated instruction pointer takes effect in the next pass. Within a pass, the rounds in which bit i of any register may be accessed are determined by i and the instruction, or, in a conversion, by i and the coarse-grained round. There are at most three of them, denoted t0 < t1 < t2 , and they may be consecutive (e.g. for ADD(r, r, r)). A register agent therefore also keeps a status from the set {early, active0 , between0 , active1 , between1 , active2 , late}. It indicates whether the current round of the pass precedes t0 , equals tj , lies strictly between tj and tj+1 , or follows the last of these rounds. In addition, as in PUTe , the agent adopts the component (put) when it enters an active round in which a PUTe is executed, and clears it once it has processed the request. Both components require O(1) states. Anomaly detection. These states suffice to preserve correctness and anomaly detection. Register agents do not relay the fine clock or participate in majority operations. Both protocols run on the remaining n − ρ′ w = (1 − o(1))n agents; all input and weight agents are in this set, so removing the register agents, which would contribute zero bias, does not alter a comparison. The induced 26

scheduler is uniform on this set, and the constant-factor change in interaction rate preserves the bounds. Outside its active rounds, no correct request concerns a register agent, so it ignores all requests. Let p denote the coarse-grained round of the agent, I the instruction of the current pass, and s its status; from i and I, the agent knows the positions t0 < t1 < t2 of its active rounds within the pass. When it meets a non-register agent in fine round t′ with instruction or pass tag I ′ , the transition function determines the corresponding coarse-grained round p′ and status s′ from t′ , I ′ , and i. This is possible because the pass boundaries are fixed. Coarse-grained rounds and statuses within a pass advance monotonically; an older observation is ignored, except for the anomaly tests below. Two different instruction tags for the same pass signal an anomaly. Before replacing (p, I, s) by a later (p′ , I ′ , s′ ), the agent checks all obligations associated with the old status and every active round that the update would skip. Thus an update never erases an unchecked witness. The exact round t′ is not stored. The agent signals an anomaly in the following cases: 1. Status skip: the update would skip one of its active rounds, that is, either p′ = p and the next active round of the agent in pass p precedes t′ , or p′ = p + 1 and the agent has an active round in pass p after its current status or in pass p′ before t′ . 2. Clock anomaly: the partner’s coarse-grained round differs from p by more than one, or the agent is active, the partner carries a fine round number, and that number differs by more than one from the active round determined by p, I, i, and s. 3. Protocol anomaly: the agent leaves an active status of a PUTe round while still holding the component (put). In active rounds in which GETe is executed, the agent adopts the component (get) as in Protocol 12, which allows it to answer the request; no additional check is attached to it, since the leader signals an anomaly if it does not receive the bit. Requests and responses are accepted only for the corresponding active round. On receipt of the terminal marker, the agent checks every remaining active-round obligation and any pending (put) component before entering its terminal status. An anomaly indication is permanent and takes priority over subsequent updates. Since every round contains an interval of Ω(log n) time in which all other agents share the same round number (Theorem 5), a register agent enters each of its active statuses whp, so none of these anomalies occurs in a correct execution whp. Since every pass has at least w rounds, there are O(τ /w) coarse-grained rounds. A register agent thus stores its register index, bit index, and bit value, its coarse-grained round, and O(1) further states for the instruction, the status, and the components (put) and (get). Hence the register agents use O(ρ′ w · τ /w) = O(ρ′ τ ) states instead of O(ρ′ wτ ). The remaining bounds from the proof of Theorem 3 are unchanged: leader election and weight creation use O(w2 ) states, weight agents use O(wτ ) states, and input and output agents use O((TR + TP )τ ) = O(ρ′ τ ) states. Hence the total number of states is O((ρ′ + w)τ ). The backup contributes O(ρ′ w2 ) states, which is absorbed because ρ′ = O(T ) and τ = Ω(wT ) for the padded schedule. Thus the same refinement applies to the combined stable and silent simulation.

4

Backup Simulation

4.1

Overview

We now present a novel stable and silent backup protocol simulating general P-programs, which provides the stable component required by Theorem 2(ii). An anomaly propagates a one-way switch into fresh backup states, preserving input labels. The backup then follows Figure 1 with the same

27

instruction reductions (Subsection 2.2), without a clock or further epidemics; full details and proofs follow in this section. Theorem 8. For every P-program, the backup simulation population protocol silently stabilises in expected time O(n2 w), and uses O(ρ′ w log n) = O(ρ′ w2 ) states. A stable protocol must cope with two problems that the MC+ simulation sidesteps by failing with negligible probability: the eventual leader never learns that it is unique, and it never learns that it has read all input agents. The construction addresses them with three main techniques. (1) Rank-based restarts. Leaders are eliminated in pairwise duels [AAD+ 06], which we augment with a rank carried by every agent; in a state (X, i), X ∈ {L, F } marks a leader or a non-input follower and i is its rank: (L, i) + (L|F, j) → (L, i) + (F, i) if i > j,

(L, i) + (L, i) → (L, i + 1) + (F, i + 1).

This augmentation is essential. Without it, simulations started by leaders that are later eliminated leave register, output and read-input data that the final leader cannot distinguish from its own, and since it never learns that it is unique, it cannot know when to start the definitive simulation. The rank of a leader is the Strahler number [Str52] of its tree of won duels, so it is at most 1 + ⌊log n⌋, and only the finally elected leader reaches the highest rank (Lemma 9). After each rank increase, the leader restarts the entire simulation under its new rank. Rank rules take priority throughout; a lower-ranked non-input follower can be reclaimed and, when needed, allocated in the same interaction. Hence the simulation of the last leader overwrites all others and alone determines the output, although this leader never learns that it is unique. Unlike a counter of won duels, which could reach n, the rank stays logarithmic, so ranks replace the round counter of the MC+ simulation at a cost of only a factor O(log n) = O(w) in the number of states. (2) Direct access. In PUTb and GETb (stable variants of the atomic subroutines), the leader simply waits until it meets the agent holding the requested register bit, which happens with probability 1 in O(n) expected time. Once the unique highest-ranked leader remains, the reductions of Subsection 2.2 emulate every RAM instruction correctly with probability 1 in O(nw) expected time (Fact 4); program emulation and output conversion then always succeed (Lemma 11). (3) Self-correcting input reading. Input agents keep their states ini permanently; the leader increments riin for every input agent of lower rank that it meets and marks it as read by assigning it its own rank. Termination of the input conversion stage is decided by a helper agent that counts its interactions with the leader up to dw: as the leader meets a given unread input agent and the helper with equal probability, it misses some input agent with probability at most n2−dw ≤ n−η (Lemma 10). This is where the preprocessing of Subsection 2.1 is essential. Since the input array is protected and the output array is preserved during printing, a missed input agent can be handled after program emulation and output conversion finish: the leader erases the completed unary output (Lemma 11) and re-enters input conversion. Only previously missed input agents remain unread, so their counts are added to the retained input array. The program is then emulated again on the corrected input array. After leader election, each fresh input-conversion attempt misses an input agent with conditional probability at most n−η , so the expected number of further retries is o(1). Any attempt already in progress has the same asymptotic expected cost. The emulation takes O(T nw) = O(n poly(w)) expected time, so the bound O(n2 w) is dominated by the conversions of the O((TR +TP )2w−1 ) = O(n) unary input and output units, each requiring an INC or DEC of O(nw) expected time.

28

4.2

State Organisation and Handover

The following subsections give the full description and proofs of the backup simulation outlined in Subsection 4.1. In this section, we present a stable and silent backup protocol for simulating a given P-program (Protocol 16). The program halts on every admissible input and initialises each working register before its first read in that execution, including on the partial input vectors encountered during recovery. Its time, memory, and input/output bounds hold uniformly for these executions. It provides the stable component required by the MC+ framework. The construction silently stabilises to the correct output with probability 1, in expected time O(n2 w), using O(ρ′ w log n) = O(ρ′ w2 ) states. As in the MC+ simulation, a leader coordinates the computation, as described in Subsection 2.1. However, in the backup, the leader accesses the register, input, and output agents directly. Other agents store data or assist with input conversion; they do not propagate requests by epidemics. Rules involving the leader apply in both interaction orientations. When an MC+ anomaly invokes this backup, a one-way backup-mode flag spreads by epidemic. On first receiving the flag, a non-input agent discards its MC+ state and enters the backup as a rank-1 leader, while an input agent retains its immutable input label and receives rank 0. An agent already in backup mode is never initialised again. The rank rules below remain active during this handover. All agents enter backup mode in expected time O(log n); the ensuing analysis includes any simulation work already in progress. Thus the handover needs no simultaneous reset and uses disjoint MC+ and backup state spaces. The backup does not count rounds. Instead, each agent carries a rank, which distinguishes successive simulations and allows obsolete data to be discarded. In protocol descriptions, agent A usually denotes a leader and agent B its interaction partner. The state of an agent A is a tuple of components, one of which is always the rank A.rank. We refer to the remaining components collectively as the substate A.substate. When a subprotocol has an explicit argument A, this denotes the leader executing it. The component rank takes values in {0, 1, . . . , h}, where h = 1 + ⌊log n⌋ = O(w), while substate specifies the role of the agent and its role-specific data, as listed in Table 5. Role leader

Value of substate (L, aux)

register helper input output free

(R, r, i, b) (H, j) ini outi φ

Description aux: finite control, ip, one register index, one bit index, input/output index register index, bit index, bit value counter of interactions with the leader index of the input variable index of the output variable no assigned role

Table 5: Values of the component substate.

4.3

Ranks, Leader Election and Backup Simulation Overview

The first stage of the backup simulation is leader election and rank computation. Election and rank-reclamation rules take priority in every control state, including during subroutine calls and after output conversion. We use a standard leader election protocol based on duels, augmented with a rank-computation mechanism that stores the rank of each agent in its component rank.

29

In this stage, the transition function concerns only the role and rank component. On initial entry into the backup, each non-input agent is a leader L of rank 1, and each input agent has rank 0. Whenever two leaders interact, one of them is eliminated: if their ranks differ, the leader with the lower rank becomes a follower F ; if the ranks are equal, one of them becomes a follower and the other increases its rank by 1. Only non-input agents reach follower state F . Consequently, only one leader reaches the highest rank that is at most 1 + ⌊log n⌋. A leader reclaims a lower-ranked non-input partner by resetting it to the free substate at its own rank. When the current operation allocates a free agent, a lower-ranked non-input follower may be reclaimed and assigned its new role in the same interaction; leader duels retain priority. An input agent retains its immutable input label and receives the leader’s rank only when accepted for input conversion. Every other simulation operation on a non-input agent requires matching ranks; higher-ranked partners are left unchanged. This process is described by the following transitions: (L, i) + (L|F, j) → (L, i) + (F, i) if i > j, (L, i) + (L, i) → (L, i + 1) + (F, i + 1). Here F denotes a non-input follower; on losing a duel, it is reset to the free substate. In an equal-rank duel, the winner discards its old control state and restarts register allocation at the increased rank. Interactions between two non-leaders make no changes. Once a unique leader of the highest rank remains, which happens with probability 1, it reclaims the remaining lower-ranked non-input agents through direct interactions. Lemma 9. The leader election and rank computation stage of the backup simulation elects a unique leader in expected time O(n). Only this leader reaches the highest rank in the population, which is at most 1 + ⌊log n⌋. Proof. The time complexity of leader election by pairwise duels has been studied in [AAD+ 06]. The rank of a leader corresponds to the Strahler number [Str52] of the tree of duels it has won, or equivalently to the register number [FRV79, ELS14]. In particular, a leader of rank r has defeated, directly or indirectly, at least 2r−1 initial leaders, so 2r−1 ≤ n. No other agent ever holds the leader role with the final highest rank: if two agents ever reached that rank as leaders, eliminating either would require an equal-rank duel creating a higher rank or a duel with an already higher-ranked leader. The maximum leader rank never decreases, contradicting its final value. These arguments also allow staggered entry during handover: each non-input agent contributes once as an initial rank-1 leader, and the O(n) expected election bound applies after the last such entry. After each rank increase, the leader restarts the entire simulation and labels it with its new rank, thereby invalidating all simulations of lower ranks. Hence, the simulation started by the last remaining leader is the only one with the highest rank; it overwrites all previous simulations, and its result becomes the final output of the backup protocol. This mechanism allows the finally elected leader to complete the definitive simulation without ever receiving confirmation that it is the only leader. When it first attains its final rank, that rank has never labelled another leader’s simulation. The register representation it constructs is therefore fresh and cannot be modified by lower-ranked leaders. The input array is cumulative and protected: the source program addresses only its original ρ registers, and only the trusted replacements of READ and PRINT access the reserved input and output arrays. Scratch registers are initialised before use. On a retry at the same rank, register agents and input counts are retained; the modified program restores its input/output pointers and initialises its working values. Address bounds are checked before an index is retained by the leader. 30

An invalid request suspends that simulation while leaving the priority rank rules active; it cannot occur in the final isolated instance under the program assumptions. Protocol 16 Simulationb . The final checking state persists; priority rank rules remain active throughout. Input: a modified P-program, a leader A Result: stable simulation if A is the unique leader 1: function Simulationb (A) 2: RegInit(ρ′ , w, A) 3: U2B: U2Bconversionb (A) 4: ip ← 0 5: while ip ̸= END do 6: A emulates the RAM instruction indicated by ip. 7: Update ip. 8: B2Uconversionb (A) 9: FINISHED: retain the output and wait for an input agent B with B.rank < A.rank. 10: EraseOutput(A); goto U2B: During its simulation, the leader uses only agents of its own rank; whenever it encounters followers of lower rank, it turns them into free agents. Thus, unless stated otherwise, all agents appearing in the protocols executed by a leader A are assumed to have rank A.rank. The leader starts the simulation by initialising the registers. It then reads the input using the unary-to-binary conversion, which succeeds whp. It then emulates the modified P-program and converts the output array from binary to unary, both of which always succeed. However, with negligible probability, some input agents are not read during the unary-to-binary conversion. To handle this case, after completing the simulation, the leader keeps checking for input agents of lower rank than its own. If there are none, these checks do not cause meaningful interactions and thus do not prevent the protocol from being silent. If such an agent is found, the entire output is erased and the simulation returns to the unary-to-binary conversion stage to read the remaining input agents. The working registers need not be reset externally before emulation is repeated, since the P-program initialises them before reading them. The input array is preserved and subsequent conversions count only input agents of lower rank. Since the modified P-program performs the same number TP of prints for any input, there is also no need to reset the output array: it is overwritten when the emulation is restarted.

4.4

Backup Emulation of RAM Instructions

We begin with the stable backup variants PUTb and GETb of the atomic subroutines PUT and GET. In the PUTb (rd, i, b) subroutine, the leader interacts with agents one after another until it encounters the agent holding the i-th bit of register rd, at which point it sets this bit to b.

31

Protocol 17 PUTb (rd, i, b) Input: rd - pointer to a register, i - bit index, b ∈ {0, 1}, a leader A Result: The i-th bit of register rd is set to b 1: function PUTb (rd, i, b, A) 2: repeat 3: The leader interacts with an agent B. 4: until B.rank = A.rank and B.substate = (R, rd, i, ⋆) 5: B.substate ← (R, rd, i, b) The GETb (rs, i) subroutine is analogous. The leader interacts with agents until it encounters the agent holding the i-th bit of register rs, at which point it learns the value of that bit. Protocol 18 GETb (rs, i) Input: rs - pointer to a register, i - bit index, a leader A Result: The leader learns the i-th bit of register rs 1: function GETb (rs, i, A) 2: repeat 3: The leader interacts with an agent B. 4: until B.rank = A.rank and B.substate = (R, rs, i, b) 5: return b Each of these subroutines completes once the leader interacts with the agent holding the specified bit. Such an interaction occurs with probability 1, in expected time O(n). The following fact states the completion time of the backup variants of the atomic subroutines and, consequently, the time required to emulate RAM instructions. Fact 4. When executed by the unique highest-ranked leader, the backup subroutines GETb and PUTb complete in expected time O(n). Consequently, every RAM instruction can be stably emulated by the unique leader in expected time O(nw).

4.5

Backup Input and Output Conversion

In this subsection, we describe input and output conversion in the stable backup variant. Since the input and output arrays occupy fixed ranges of consecutive addresses, with riin and riout at fixed positions, we assume that the leader can convert an index i, or a state ini or outi , to the address of riin or riout , and vice versa. This mapping can be encoded in the transition function, or emulated by a sequence of RAM instructions using a few additional registers. Backup unary-to-binary input conversion. Before the RAM instructions of the modified P-program are emulated, the input data is converted from unary to binary and stored in the input array, as in the MC+ variant. We now introduce the protocol U2Bconversionb (A) (Protocol 19), executed by the leader A, which performs this conversion. First, the leader designates a free agent B as a helper by setting B.substate ← (H, 0). The helper increments its counter each time it interacts with the leader. The conversion protocol terminates when the helper’s counter reaches the value dw, for a constant d > 0. At that point, the leader turns the helper back into a free agent so that every call of the protocol uses a fresh helper. After passing the label START:, the leader is in a waiting state, in which it reacts only to new input agents and the helper. When it encounters an input agent B with B.substate = ini and a lower rank, the leader executes line 7: it marks B as read by assigning it its own rank and 32

increments riin by one. Until this incrementation is completed, the leader ignores the helper and other input agents; only the required register accesses and the priority rank rules remain active. Once the incrementation is completed, the leader returns to the waiting state and continues to process input agents and count interactions with the helper. The helper’s counter bounds the number of L + H interactions and thus determines when the conversion ends. By choosing a sufficiently large constant d, the leader A encounters every input agent whp before the helper’s counter reaches dw. Protocol 19 U2Bconversionb (A) Input: A - a leader Result: the cumulative input counts include every input agent whp 1: function U2Bconversionb (A) 2: In the first interaction of A with a free agent B: 3: B.substate ← (H, 0) ▷ Helper designation. 4: START: 5: During subsequent interactions A + B: 6: if B.substate = ini and B.rank < A.rank then 7: B.rank ← A.rank, INC(riin ), goto START: 8: if B.substate = (H, j) and B.rank = A.rank then 9: if j + 1 < dw then B.substate ← (H, j + 1), goto START: 10: else B.substate ← φ; return The following lemma characterises the unary-to-binary input conversion protocol of the backup. Lemma 10. Protocol U2Bconversionb (A), when executed by the unique leader of the final rank, returns in expected time O((N + 1)nw) = O(n2 w), where N is the number of input agents not yet counted at the start of the call. The probability that any input agent remains uncounted at return is at most N 2−dw ≤ n2−dw . Proof. After leader election, a constant fraction of the population is either free at the leader’s rank or can be reclaimed from a lower rank on contact. Thus the leader designates a helper in expected time O(1). Fix an input agent B not yet counted and consider only interactions of the leader in the waiting state. Until B is counted, the probabilities of meeting B and the helper are equal. Pausing the scan during register increments does not change this symmetry. Hence the probability of meeting the helper dw times before meeting B is 2−dw . A union bound over the N uncounted input agents gives N 2−dw . This is at most n−η for any prescribed constant η > 0 when d is sufficiently large, since w = Θ(log n). The expected total time spent waiting for the dw helper meetings is O(nw). At most N inputregister increments are performed, each in expected time O(nw) by Fact 4. The helper counter is paused during these increments, giving total expected time O((N + 1)nw). At every boundary between completed increments, each input register equals the number of input agents of its label that have been assigned the leader’s rank. Thus partial conversion preserves correct cumulative counts. Backup binary-to-unary output conversion. The results of the modified P-program are stored in binary form in the output array. We now describe the binary-to-unary conversion protocol in the stable backup variant B2Uconversionb (A) (see Protocol 20), executed by the leader A.

33

The leader executes a loop from i = 1 to TP . Its goal in iteration i is to create a subpopulation of [riout ] agents in substate outi , which represents the i-th output value in unary. To this end, the leader copies [riout ] into a temporary register rc using the direct copy COPY(riout , rc). It repeatedly decrements rc and assigns the substate outi to a free agent whenever the resulting value is non-negative, stopping when [rc] = −1. Thus it prints exactly one agent per unit of the original output value, including no agents when that value is zero. In this way, the computation results are output in unary form, while the original binary values remain stored in the output array. Preserving these values allows the output to be undone if the simulation was carried out on incorrect data. This can occur only if the leader fails to encounter some input agent(s) during the unary-to-binary input conversion stage. After output conversion has completed, EraseOutput(A) follows the same scheme using the preserved binary values. Only after erasure finishes may the next execution overwrite the output array. The only difference is that the leader, instead of turning agents in substate φ into agents in substate outi , turns agents in substate outi into agents in substate φ. Protocol 20 B2Uconversionb (A) Input: A - a leader Result: all output stored in binary in output array registers stably converted to unary 1: function B2Uconversionb (A) 2: for i ← 1 to TP do 3: COPY(riout , rc) 4: goto CONVERT: 5: ASSIGN: 6: In the first interaction of A with a free agent B: 7: B.substate ← outi 8: CONVERT: 9: DEC(rc), JGE(rc, ASSIGN:) The behaviour of the output-creating and output-erasing protocols is characterised by the following lemma. Lemma 11. Protocol B2Uconversionb (A), when executed by the unique highest-ranked leader, stably converts all output values stored in the output array from binary to unary representation in expected time O(TP 2w nw) = O(n2 w). Moreover, if necessary, the unary output representation can be stably erased by protocol EraseOutput(A) in the same expected time. Proof. By Fact 4, each RAM instruction used in B2Uconversionb (A) executes in expected time O(nw). After leader election, a constant fraction of the population is free or reclaimable on contact, even while the definitive output is being allocated. Thus, the leader A can stably assign any output state to a previously free agent in expected time O(1) (lines 6–7 of Protocol 20). The binary-to-unary conversion proceeds one output variable at a time. To convert the i-th output value, the leader emulates one instruction COPY, followed by at most 2w−1 pairs of DEC and JGE instructions and exactly [riout ] assignments of an output state to a free agent. Since 0 ≤ [riout ] < 2w−1 , the signed counter runs down to −1 without overflow. Each such iteration takes expected time O(nw). Hence, converting a single output variable takes expected time O(2w · nw). Consequently, all TP output variables are stably converted from binary to unary in total expected time O(TP 2w nw) = O(n2 w). The analysis of protocol EraseOutput(A) is analogous to the one above. The only difference is that releasing an output agent takes expected time up to O(n). However, this does not affect the overall expected time bound. 34

4.6

Backup Summary

We conclude the construction of the backup simulation protocol by establishing the following theorem on its correctness and complexity. Theorem 8. For every P-program, the backup simulation population protocol silently stabilises in expected time O(n2 w), and uses O(ρ′ w log n) = O(ρ′ w2 ) states. Proof. After the O(log n) expected handover, Lemma 9 gives a unique leader within further expected time O(n). Only this leader ever attains its final rank K, so its rank-K registers are uncontaminated. By the coupon collector bound, direct interactions reclaim all lower-ranked non-input agents in expected time O(n log n). Reclamation overlaps simulation; no separate synchronisation is needed. At rank K, the protected input array records correct cumulative counts for agents assigned that rank and survives retries. Every tentative input is admissible: the program halts, initialises its working registers, and writes exactly TP outputs. Output conversion completes with probability 1, preserving the binary record needed for erasure. If input was missed, the leader eventually encounters a missed agent in FINISHED, erases the completed output, and resumes conversion with a fresh helper. Otherwise, the output is correct and no retry occurs. Register allocation costs expected time O(ρ′ w) once at the final rank: a constant fraction of agents is free or reclaimable on contact, and performing reclamation and allocation in one interaction allows Lemma 2 to apply. Lemma 10, Fact 4, and Lemma 11 give expected costs O(n2 w) for input conversion, O(T nw) for each tentative execution, and O(n2 w) each for output creation and erasure. Finding a missed input in FINISHED costs expected time O(n). Since T = poly(w) and n ≥ C2w , these costs, including detection and erasure after failure, are bounded conditionally on every valid attempt-start history by B = O(n2 w). The same bound covers a legitimate subprotocol already in progress when leader election finishes. Charge O(B) for this residual execution, then consider attempts starting with a fresh helper. For each fresh attempt, Lemma 10 bounds the conditional probability of missed input by δ ≤ n2−dw ≤ n−η , for sufficiently large d. Thus a k-th fresh attempt is needed with probability at most δ k−1 . Summing the conditional cost bounds at attempt starts gives expected remaining time at most X k≥1

δ k−1 B =

B = O(n2 w). 1−δ

Independence is unnecessary, and infinitely many retries have probability zero. After complete input has been simulated, obsolete non-input states are reclaimed, the helper is released, and the leader’s checking rules make no changes. The protocol therefore silently stabilises correctly with probability 1. Including election, reclamation, allocation, and the initial residual execution preserves the expected bound O(n2 w). There are O(log n) = O(w) ranks. Per rank, register agents use O(ρ′ w) states for a register index, bit index, and bit value; input/output agents use O(TR + TP ); the helper uses O(w); and free agents use O(1). The leader stores ip and finite control in O(1) states for the fixed program, plus one variable register index, one bit index, and constantly many bits. During conversion, the input/output index determines the register address. Whole-word temporaries occupy auxiliary registers already included in ρ′ . Thus the leader uses O(ρ′ w) states per rank, and the disjoint role-specific state spaces total O(ρ′ w log n) states. 35

Remark. Correctness of the backup does not require advance knowledge of TRAM . It is enough that each admissible execution halts and initialises its working registers, while the memory and input/output bounds are known so that the required registers and agents can be allocated. The stated complexity bounds continue to use the polynomial resource assumptions defining P-programs.

5

Conclusions

We have shown that every P-program satisfying the stated halting and register-initialisation assumptions admits an efficient, stable, and silent population protocol (Theorem 1). Under suitable binary encodings and population-capacity bounds, this supports computations in P and FP, including multiple outputs; longer results can be split into admissible words. The total binary input length is O(TR w) and need not equal w. In particular, multiplication of input counts admits an efficient stable protocol with unary inputs and outputs whenever the product lies in the admissible range. This gives a lower bound towards the time-bounded characterisation sought in [CFG25]. Las Vegas computations. The framework suggests an extension to ZPP. An instruction LoadRandom(rd) could sample a word bit by bit from the leader’s initiator/responder roles at fresh interactions. If a zero-error algorithm has expected running time at most p(w), each fresh trial truncated after 2p(w) steps succeeds with probability at least 1/2; cw trials fail with probability at most 2−cw = n−Ω(1) . Formalising random-bit generation, restarts, and a stable backup remains necessary. Exhausting all trials would trigger fallback; this is distinct from an MC+ simulation anomaly. Succinct Presburger evaluation. Czerner et al. [CGHE24] proposed as a research direction succinct protocols for quantifier-free Presburger formulas, with poly(m) states for a formula of size m, that converge in poly log n time. We propose an analogous direction for leaderless protocols that are additionally required to be stable. With poly(m) states independent of n, such protocols cannot be fast [BDS17], and already majority, a formula of constant size, requires Ω(log n) states for time O(n1−c ) under the assumptions of [AAG18]. We therefore call a fast leaderless stable protocol succinct if it uses poly(m) · poly log n states. Under this notion, our result gives succinct protocols that moreover stabilise silently: every such formula is evaluated by a P-program with poly(m) instructions and registers, so for all sufficiently large n, Theorem 1 yields a protocol with poly(m) · poly log n states and poly log n stabilisation time. Reducing the polylogarithmic factor, ideally to poly(m) · O(log n) states, which would match the lower bound for majority, remains open. Open problems. First, Theorem 4 improves the state bound; adapting faster majority [DEG+ 21], leader election, clocks, or conversions to MC+ could sharpen the bounds further. A structural goal is a state bound depending on memory and input/output requirements without a multiplicative dependence on running time, while preserving failure detection. Second, under the assumptions of Section 1.1, a gap remains between poly(w)-time source computations and reverse simulation in poly(w) space and expected 2O(w) time. For predicates, the cited uniformity and constructibility assumptions also yield an NSPACE(polylog n) upper bound [CFG25]. Narrowing this gap, characterising the power exactly, and determining whether dropping silence increases it remain open. Another goal is to remove advance knowledge of w while preserving arithmetic semantics and resource guarantees; stable size estimation [BKR19] may help. Interaction graphs beyond the complete graph provide another direction. External, distributed, and spatial data. Relevant precedents include selective protocols for median computation using comparisons of arbitrarily large hidden keys [GGJ+ 24], and spatial population protocols for localisation using distance or vector queries [GKL+ 25]. A useful goal is to integrate such interfaces with our simulation through operations for reading records, comparing keys, and

36

acquiring geometric information that preserve anonymity and support efficient stable computation. Their costs must be analysed alongside internal arithmetic. Selection on distributed records and computation from statistical or geometric summaries provide concrete benchmarks. These extensions should account for precision, output representation, and data consistency, and support recovery followed by silence once the data stop changing. AI methodology. OpenAI’s ChatGPT and Anthropic’s Claude assisted with language polishing, LaTeX editing, bibliographic reconciliation, and consistency checking. ChatGPT also helped refine the presentation of the simulation and recovery arguments in Sections 2–4, and Claude helped revise the introduction and related work, check cited claims against their sources, and review the manuscript. The authors verified the correctness and originality of all content, including references.

37

References [AG15]

Dan Alistarh and Rati Gelashvili. Polylogarithmic-time leader election in population protocols. In Automata, Languages, and Programming (ICALP 2015), Part II, volume 9135 of Lecture Notes in Computer Science, pages 479–491. Springer, 2015. doi: 10.100 7/978-3-662-47666-6_38.

[AGV15]

Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and exact majority in population protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, pages 47–56. ACM, 2015. ISBN 978-1-4503-3617-8. doi: 10.1145/2767386.2767429.

[AAE+ 17]

Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2560–2579. SIAM, 2017. doi: 10.1137/1.9781611974782.169.

[AAG18]

Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 2221–2239. SIAM, 2018. doi: 10.1137/1.9781 611975031.144.

[AGR22]

Dan Alistarh, Rati Gelashvili, and Joel Rybicki. Fast graphical population protocols. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021), volume 217 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1– 14:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi: 10.4230/LIPIcs.O PODIS.2021.14.

[ARV22]

Dan Alistarh, Joel Rybicki, and Sasha Voitovych. Near-optimal leader election in population protocols on graphs. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022), pages 246–256. ACM, 2022. doi: 10 .1145/3519270.3538435.

[AAD+ 06]

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235–253, 2006. doi: 10.1007/s00446-005-0138-3.

[AAE06]

Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC 2006), pages 292–299. ACM, 2006. doi: 10.1145/11 46381.1146425.

[AAER07]

Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279–304, 2007. doi: 10.1 007/s00446-007-0040-2.

[AAE08b]

Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21(2):87–102, 2008. doi: 10.1007/s00446-008-0059-z. URL https://cs.yale.edu/homes/aspnes/paper s/approximate-majority-abstract.html.

38

[AAE08a]

Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):183–199, 2008. doi: 10.1007/s0 0446-008-0067-z.

[Asp21]

James Aspnes. Clocked population protocols. Journal of Computer and System Sciences, 121:34–48, 2021. doi: 10.1016/j.jcss.2021.05.001.

[Asp25]

James Aspnes. Stochastic well-structured transition systems, 2025. URL https: //arxiv.org/abs/2512.20939. arXiv:2512.20939.

[AR09]

James Aspnes and Eric Ruppert. An introduction to population protocols. In Benoît Garbinato, Hugo Miranda, and Luís Rodrigues, editors, Middleware for Network Eccentric and Mobile Applications, pages 97–120. Springer, 2009. doi: 10.1007/978-3-5 40-89707-1_5. URL https://www.cs.yale.edu/homes/aspnes/papers/introduc tion-to-population-protocols-abstract.html.

[BDS17]

Amanda Belleville, David Doty, and David Soloveichik. Hardness of computing and approximating predicates and functions with leaderless population protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 141:1– 141:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi: 10.4230/LIPIcs .ICALP.2017.141.

[BNKKP20] Stav Ben-Nun, Tsvi Kopelowitz, Matan Kraus, and Ely Porat. An O(log3/2 n) parallel time population protocol for majority with O(log n) states. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC 2020, pages 191–199. ACM, 2020. doi: 10.1145/3382734.3405747. [BKKO18]

Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. Simple and efficient leader election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018), volume 61 of Open Access Series in Informatics (OASIcs), pages 9:1–9:11. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi: 10.4230/OASIcs.SOSA.2018.9.

[BKR19]

Petra Berenbrink, Dominik Kaaser, and Tomasz Radzik. On counting the population size. In P. Robinson and F. Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 43–52. ACM, 2019. doi: 10.1145/3293611.3331631.

[BGK20]

Petra Berenbrink, George Giakkoupis, and Peter Kling. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), pages 119–129. ACM, 2020. doi: 10.1145/3357713.3384312.

[BHK+ 20]

Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck, and Hung Tran. Simulating population protocols in sub-constant time per interaction. In 28th Annual European Symposium on Algorithms (ESA 2020), volume 173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi: 10.4230/LIPIcs.ESA.2020.16.

[BEF+ 21]

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. Time-space trade-offs in population protocols for the majority 39

problem. Distributed Computing, 34(2):91–111, 2021. ISSN 1432-0452. doi: 10.1007/s0 0446-020-00385-0. [BCER17]

Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O(log2 n) states and O(log2 n) convergence time. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing, PODC 2017, pages 451–453. ACM, 2017. doi: 10.1145/3087 801.3087858.

[BEJ19]

Michael Blondin, Javier Esparza, and Stefan Jaax. Expressive power of broadcast consensus protocols. In 30th International Conference on Concurrency Theory (CONCUR 2019), volume 140 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi: 10.4230/LIPIcs.CONCUR.2019.31.

[BEG+ 20]

Michael Blondin, Javier Esparza, Blaise Genest, Martin Helfrich, and Stefan Jaax. Succinct population protocols for Presburger arithmetic. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi: 10.4230/LIPIcs.STACS.2020.40.

[BEJM21]

Michael Blondin, Javier Esparza, Stefan Jaax, and Philipp J. Meyer. Towards efficient verification of population protocols. Formal Methods in System Design, 57(3):305–342, 2021. doi: 10.1007/s10703-021-00367-3.

[BCR18]

Olivier Bournez, Johanne Cohen, and Mikaël Rabie. Homonym population protocols. Theory of Computing Systems, 62(5):1318–1346, 2018. doi: 10.1007/s00224-017-9833-2.

[CMN+ 11]

Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, and Paul G. Spirakis. Passively mobile communicating machines that use restricted space. Theoretical Computer Science, 412(46):6469–6483, 2011. doi: 10.1016/j.tcs.2011.07.001.

[CDS14]

Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 13(4):517–534, 2014. doi: 10.100 7/s11047-013-9393-6.

[CR73]

Stephen A. Cook and Robert A. Reckhow. Time bounded random access machines. Journal of Computer and System Sciences, 7(4):354–375, 1973. doi: 10.1016/S0022-000 0(73)80029-7.

[CJ21]

Philipp Czerner and Stefan Jaax. Running time analysis of broadcast consensus protocols. In Foundations of Software Science and Computation Structures (FoSSaCS 2021), volume 12650 of Lecture Notes in Computer Science, pages 164–183. Springer, 2021. doi: 10.1007/978-3-030-71995-1_9.

[CGHE24]

Philipp Czerner, Roland Guttenberg, Martin Helfrich, and Javier Esparza. Fast and succinct population protocols for Presburger arithmetic. Journal of Computer and System Sciences, 140:103481, 2024. doi: 10.1016/j.jcss.2023.103481.

[CFG25]

Philipp Czerner, Vincent Fischer, and Roland Guttenberg. The expressive power of uniform population protocols with logarithmic space. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025), volume 330 of Leibniz International 40

Proceedings in Informatics (LIPIcs), pages 1:1–1:18. Schloss Dagstuhl – LeibnizZentrum für Informatik, 2025. doi: 10.4230/LIPIcs.SAND.2025.1. [DE19]

David Doty and Mahsa Eftekhari. Efficient size estimation and impossibility of termination in uniform dense population protocols. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 34–42. ACM, 2019. doi: 10.1145/3293611.3331627.

[DE21]

David Doty and Mahsa Eftekhari. A survey of size counting in population protocols. Theoretical Computer Science, 894:91–102, 2021. doi: 10.1016/j.tcs.2021.08.038.

[DS15]

David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. In Distributed Computing (DISC 2015), volume 9363 of Lecture Notes in Computer Science, pages 602–616. Springer, 2015. doi: 10.1007/978-3-662-486 53-5_40. URL https://doi.org/10.1007/978-3-662-48653-5_40.

[DEG+ 21]

David Doty, Mahsa Eftekhari, Leszek Gąsieniec, Eric E. Severson, Przemysław Uznański, and Grzegorz Stachowiak. A time and space optimal stable population protocol solving exact majority. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1044–1055. IEEE, 2021. doi: 10.1109/FOCS52979.20 21.00104.

[ELS14]

Javier Esparza, Michael Luttenberger, and Maximilian Schlund. A brief history of Strahler numbers. In Language and Automata Theory and Applications (LATA 2014), volume 8370 of Lecture Notes in Computer Science, pages 1–13. Springer, 2014. doi: 10.1007/978-3-319-04921-2_1.

[FRV79]

Philippe Flajolet, Jean-Claude Raoult, and Jean Vuillemin. The number of registers required for evaluating arithmetic expressions. Theoretical Computer Science, 9(1): 99–125, 1979. doi: 10.1016/0304-3975(79)90009-4.

[FW90]

Michael L. Fredman and Dan E. Willard. BLASTING through the information theoretic barrier with FUSION TREES. In H. Ortiz, editor, Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (STOC 1990), pages 1–7. ACM, 1990. doi: 10.1145/100216.100217.

[GGJ+ 24]

Adam Gańczorz, Leszek Gąsieniec, Tomasz Jurdziński, Jakub Kowalski, and Grzegorz Stachowiak. Selective population protocols. In Stabilization, Safety, and Security of Distributed Systems (SSS 2024), volume 14931 of Lecture Notes in Computer Science, pages 225–239. Springer, 2024. doi: 10.1007/978-3-031-74498-3_16.

[GS18]

Leszek Gąsieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 2653–2667. SIAM, 2018. doi: 10.1137/1.9781611975031.169.

[GS21]

Leszek Gąsieniec and Grzegorz Stachowiak. Enhanced phase clocks, population protocols, and fast space optimal leader election. Journal of the ACM, 68(1):2:1–2:21, 2021. doi: 10.1145/3424659.

[GSU19]

Leszek Gąsieniec, Grzegorz Stachowiak, and Przemysław Uznański. Almost logarithmictime space optimal leader election in population protocols. In Proceedings of the 31st 41

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), pages 93–102. ACM, 2019. doi: 10.1145/3323165.3323178. [GSS23]

Leszek Gąsieniec, Paul G. Spirakis, and Grzegorz Stachowiak. New clocks, optimal line formation and self-replication population protocols. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), volume 254 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPIcs.STACS.2023.33.

[GKL+ 25]

Leszek Gąsieniec, Łukasz Kuszner, Ehsan Latif, Ramviyas Parasuraman, Paul Spirakis, and Grzegorz Stachowiak. Anonymous self-stabilising localisation via spatial population protocols. In Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai, editors, 36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.ISAAC.2025.35.

[GGJ+ 26]

Leszek Gąsieniec, Tytus Grodzicki, Tomasz Jurdziński, Jakub Kowalski, and Grzegorz Stachowiak. Efficient stable population protocols for parity and beyond. In 40th International Symposium on Distributed Computing (DISC 2026), volume 397 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. ISBN 978-3-95977-454-3. doi: 10.4 230/LIPIcs.DISC.2026.17.

[GR09]

Rachid Guerraoui and Eric Ruppert. Names trump malice: Tiny mobile agents can tolerate Byzantine failures. In Automata, Languages and Programming (ICALP 2009), Part II, volume 5556 of Lecture Notes in Computer Science, pages 484–495. Springer, 2009. doi: 10.1007/978-3-642-02930-1_40. URL https://doi.org/10.1007/978-3-6 42-02930-1_40.

[HP26]

Lukas Hintze and Manuel Penschuck. No time to interact: Simulating population protocols at scale. In Philip Bille, Seth Pettie, and Sabine Storandt, editors, 34th Annual European Symposium on Algorithms (ESA 2026), volume 388 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. doi: 10.4230/LIPIcs.ESA.2026.19.

[KU18]

Adrian Kosowski and Przemysław Uznański. Brief announcement: Population protocols are fast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 475–477. ACM, 2018. URL https://arxiv.org/ab s/1802.06872. Full version: arXiv:1802.06872.

[MS15]

Othon Michail and Paul G. Spirakis. Terminating population protocols via some minimal global knowledge assumptions. Journal of Parallel and Distributed Computing, 81–82:1–10, 2015. doi: 10.1016/j.jpdc.2015.02.005. URL https://livrepository.li verpool.ac.uk/3003386/.

[MAA+ 15]

Yves Mocquard, Emmanuelle Anceaume, James Aspnes, Yann Busnel, and Bruno Sericola. Counting with population protocols. In 2015 IEEE 14th International Symposium on Network Computing and Applications, pages 35–42. IEEE, 2015. doi: 10 .1109/NCA.2015.35. URL https://www.cs.yale.edu/homes/aspnes/papers/nca2 015-proceedings.pdf.

42

[MAS16]

Yves Mocquard, Emmanuelle Anceaume, and Bruno Sericola. Optimal proportion computation with population protocols. In 2016 IEEE 15th International Symposium on Network Computing and Applications, pages 216–223. IEEE, 2016. doi: 10.1109/NC A.2016.7778621.

[RSSV26]

Joel Rybicki, Jakob Solnerzik, Olivier Stietel, and Robin Vacus. Space-efficient population protocols for exact majority on general graphs. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 574–612. SIAM, 2026. doi: 10.1137/1.9781611978971.24.

[SCWB08]

David Soloveichik, Matthew Cook, Erik Winfree, and Jehoshua Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4):615–633, 2008. doi: 10.1007/s11047-008-9067-y.

[Str52]

Arthur N. Strahler. Hypsometric (area-altitude) analysis of erosional topography. Geological Society of America Bulletin, 63(11):1117–1142, 11 1952. doi: 10.1130/0016-7 606(1952)63[1117:HAAOET]2.0.CO;2.

[SOI+ 20]

Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Time-optimal leader election in population protocols. IEEE Transactions on Parallel and Distributed Systems, 31(11):2620–2632, 2020. doi: 10.1109/TPDS.2020. 2991771.

43

Related documents

• Cache Engineering for Agents#1412634
• OTRO: Oblivious Tokenization Path with Square-Root ORAM#1247420
• Securing LLM-Agent Long-Term Memory Against Poisoning: Non-Malleable, Origin-Bound Authority with Machine-Checked Guarantees#303152
• LongMINT: Evaluating Memory under Multi-Target Interference in Long-Horizon Agent Systems#200536
• Semantic-TVM: Structure-Preserving Trustworthy Virtual Memory for Memory-Augmented and Tool-Using Agents#1084910