betaFeedback

WorksComputer Science

Efficient Stable Word-RAM Simulation by Population Protocols

Abstract

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

Introduction

The population protocol model [7] 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 nn. 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 11, and silent if no agent changes state after stabilisation. An event occurs with high probability (whp) if its probability is at least 1−n−η1-n^{-\eta} for any prescribed constant η>0\eta>0, with the protocol constants chosen accordingly. Its complement has negligible probability. All logarithms are to base 22. Our simulation is stable and silent, with polylogarithmic stabilisation time both in expectation and whp.

We write a transition as A+B→A′+B′A+B\mathbin{\to}A^\prime+B^\prime, meaning that an interaction between an initiator in state AA and a responder in state BB changes their states to A′A^\prime and B′B^\prime, respectively. Some of our protocols use compound states: an agent state is a tuple of components from sets S1,…,SkS_1,\ldots,S_k, giving the full state space S1×⋯×SkS_1\times\cdots\times S_k.

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 [7], the state space and transition function are independent of nn. Under uniformly random interactions, these protocols can simulate whp counter machines with a constant number of O(n)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 [7]. The stably computable predicates are exactly the semilinear predicates, equivalently those definable in Presburger arithmetic [8, 9]. In the closely related model of chemical reaction networks, the stably computable functions are exactly those with semilinear graphs [28].

These characterisations do not imply efficient stabilisation. With a constant number of states, stable leader election [35] and broad classes of predicates and functions under leaderless initialisation [15] require Ω(n)\Omega(n) expected time. For monotone protocol families, leader election and majority require Ω(n/polylog⁡n)\Omega(n/\operatorname{polylog} n) expected time with at most 12log⁡log⁡n\frac{1}{2}\log\log n states [3]. Under the additional output-dominance assumption, majority in expected time O(n1−c)O(n^{1-c}), for any fixed c>0c>0, requires Ω(log⁡n)\Omega(\log n) states [4]. 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 nn. The first efficient leader-election protocol was given in [1], and the number of states was reduced in [22] and then to the optimal O(log⁡log⁡n)O(\log\log n) in [41], with O(log⁡2n)O(\log^2 n) time whp. Further work [17 GSU19, 55] culminated in [19], with Θ(log⁡log⁡n)\Theta(\log\log n) states and optimal O(log⁡n)O(\log n) expected time.

For exact majority, early fast protocols [2, 22] were followed by an O(log⁡n)O(\log n)-state, O(log⁡2n)O(\log^{2} n)-time protocol based on a new leaderless phase clock [4]. Further improvements [BEF+21, BNKKP20] culminated in the stable protocol of [36], using O(log⁡n)O(\log n) states and optimal O(log⁡n)O(\log n) expected time. With a sufficiently large initial majority margin, approximate majority can be solved in O(log⁡n)O(\log n) time whp using only three states [10]. Efficient stable protocols for parity and congruence were obtained only recently [45].

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 [5]; near-optimal stable leader election on general graphs [6]; and space-efficient exact majority on general graphs [52]. Our simulation assumes a complete graph; extending it to these interaction graphs remains open.

Many of these protocols use the one-way epidemic process [11], whose agents are either susceptible (0) or infected (1), with transition (x,y)→(x,max⁡{x,y})(x,y) \to(x,\max\{x,y\}).

Lemma 1 (Lemma 2 in [11]). Starting from a single infected agent, the epidemic reaches all agents in Θ(log⁡n)\Theta(\log n) time whp.

This dissemination primitive underlies phase clocks and many fast leader-election and majority protocols; see [44] for a kk-contact generalisation.

Another key ingredient of these protocols is synchronisation. Phase clocks coordinate successive stages of computation, typically allowing Θ(log⁡n)\Theta(\log n) time for epidemic dissemination. Given a leader or a suitably sized junta, constant-state clocks [11 GS21] can be nested to measure any fixed polylogarithmic duration. Leaderless constructions use Θ(log⁡n)\Theta(\log n) states, including fixed-resolution clocks [36] and clocks based on the power-of-two-choices process [4]. A different leader-based construction measures Θ(nlog⁡n)\Theta(n\log n) time whp using a constant number of states [43].

We combine MC+ leader election and majority [45], 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 [50, 51]. Uniform population-size estimation has also been studied [33], including stable protocols that compute either ⌊log⁡n⌋\lfloor\log n\rfloor or ⌈log⁡n⌉\lceil\log n\rceil in O(log⁡2n)O(\log^{2} n) time whp [18]; see also [34] for a survey of counting. Our simulation assumes known w=Θ(log⁡n)w=\Theta(\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 [11]. 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(log⁡2n)O(\log^{2} 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 [53].

The framework of [48] 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ε)O(n^{\varepsilon}) convergence time for any fixed ε>0\varepsilon>0, with a constant number of states depending on ε\varepsilon, or retain polylogarithmic convergence time using O(log⁡log⁡n)O(\log\log n) states. These guarantees concern convergence; the always-correct constructions are not silent as 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 mm as defined in [31], succinct protocols [24] reduce exponential state complexity to poly⁡(m)\operatorname{poly}(m), at the cost of exponential expected time, as observed in [31]. Using population computers as an intermediate formalism, the construction of [31] achieves O(m)O(m) states and O(m7n)O(m^{7}n) expected time for n=Ω(m)n = \Omega(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)⋅polylog⁡n\operatorname{poly}(m) \cdot\operatorname{polylog} n states, which our framework achieves with silent stabilisation (§ 5).

Expressive power with growing state spaces. Uniform protocols with o(log⁡n)o(\log n) states still decide only semilinear predicates [9, 27], whereas protocols with f(n)∈Ω(n)f(n) \in\Omega(n) states capture NSPACE⁡(nlog⁡f(n))\operatorname{NSPACE}(n \log f(n)) under unary encoding [27]. For the intermediate range, under the constructibility and uniformity assumptions of [CFG25], for f(n)∈Ω(log⁡n)∩O(n1−ε)f(n) \in\Omega(\log n) \cap O(n^{1-\varepsilon}) and fixed ε>0\varepsilon> 0, uniform and weakly uniform protocols with Θ(f(n))\Theta(f(n)) states decide exactly the predicates whose unary encodings lie in NSPACE⁡(f(n)log⁡n)\operatorname{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)\operatorname{NSPACE}(\operatorname{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)\operatorname{poly}(w) time. A randomised ww-RAM stores one O(w)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)w = \Theta(\log n), the expected number of interactions is npolylog⁡nn\operatorname{polylog} n. They can be simulated by a Las Vegas algorithm using poly⁡(w)\operatorname{poly}(w) space and expected 2O(w)2^{O(w)} time. Batched simulations [20, 47] reduce the amortised cost per interaction, but do not by themselves yield a general poly⁡(w)\operatorname{poly}(w)-time simulation. With binary counts as RAM inputs, our poly⁡(w)\operatorname{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 [46] give agents unique identifiers and allow them to remember a constant number of identifiers, capturing symmetric predicates in NSPACE⁡(nlog⁡n)\operatorname{NSPACE}(n\log n). Homonym protocols [26] allow shared identifiers; with the model’s identifier operations, polylogarithmically many distinct identifiers suffice to simulate Turing machines using polylogarithmic space. PALOMA [27] gives agents logarithmic local memory and captures the same class as community protocols.

Broadcast consensus protocols capture unary predicates in NL [23]. The simulation of [30] emulates a randomised logarithmic-space Turing machine of expected running time TT in expected O(nlog⁡n⋅T)O(n\log n \cdot T) interactions. Clocked population protocols [12] provide an idealised signal that sufficient time for convergence has elapsed; absence detectors [49] test whether a specified state is absent; and selective population protocols [40] strengthen partner selection. Our simulation retains anonymous agents and uniformly random pairwise interactions, without these additional capabilities.

Complexity-theoretic perspective. Stochastic well-structured transition systems [13] 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 [25] 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 [45] 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)\Theta(\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)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 PP-programs (Definition 1): ww-RAM programs whose running time and number of registers are polynomial in w=Θ(log⁡n)w = \Theta(\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 [14].

Applications include functions with non-semilinear graphs, such as products of input counts when the result fits the prescribed output range. § 5 discusses further applications and extensions: succinct protocols for quantifier-free Presburger formulas, following [31], 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 (§ 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 ww agents, one per bit. The protocol emulates each RAM instruction through O(w)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(n2w)O(n^{2}w) time (§ 4). Together, the MC+ computation and backup guarantee correct silent stabilisation with probability 1, using polylogarithmically many states.

Model and Simulation Overview

Population protocols represent numerical inputs and outputs in unary: input AiA_i is represented by a set XiX_i of ∣Xi∣=Ai|X_i| = A_i agents, and output BiB_i by a set YiY_i of ∣Yi∣=Bi|Y_i| = B_i agents. Outputs need not be Boolean; leader election, for example, produces a singleton output set. Values can be as large as the population size nn, so their binary representations have logarithmic length. The word-RAM [29, 39], with w=Θ(log⁡n)w = \Theta(\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 ww-RAM model. The basic parameter of the ww-RAM model is its word length ww. More specifically, (1) its instruction set is based on the Cook–Reckhow model [29] (Table 1), (2) each input and output value is a non-negative (w−1)(w - 1)-bit integer, and (3) registers store signed ww-bit words in two’s-complement (U2) encoding. Arithmetic is performed modulo 2w2^w. 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.

InstructionDescription
LOAD(C,rdC, rd)C→rdC \to rd: load an integer constant CC into register rdrd
ADD(rs1,rs2,rdrs_1, rs_2, rd)[rs1]+[rs2]→rd[rs_1] + [rs_2] \to rd: load the sum of the values in rs1,rs2rs_1, rs_2 into rdrd
SUB(rs1,rs2,rdrs_1, rs_2, rd)[rs1]−[rs2]→rd[rs_1] - [rs_2] \to rd: load the difference of the values in rs1,rs2rs_1, rs_2 into rdrd
COPY(i,rp,d,rdi, rp, d, rd)[[rp]]→rd[[rp]] \to rd: load the value of the register pointed to by rprp into rdrd
COPY(d,rs,i,rpd, rs, i, rp)[rs]→[[rp]][rs] \to[[rp]]: store the value of rsrs in the register pointed to by rprp
JGE(r,Izr, I_z)if [r]≥0[r] \ge0, jump to instruction IzI_z; otherwise continue
READ(rdrd)read the next input value into register rdrd
PRINT(rsrs)output the value of register rsrs

Table 1. Instructions of the Cook–Reckhow RAM model.1

A ww-RAM program is a finite sequence of instructions from Table 1. Its execution is controlled by an instruction pointer ipip, 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 ipip 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 ww-RAM programs whose memory consists of poly⁡(w)\operatorname{poly}(w) registers, identified with their indices 0,1,…,ρ−10,1,\ldots,\rho- 1.2 More precisely, the class of programs considered in this paper is captured by the following definition of P\mathcal{P}-programs.

Definition 1 (P\mathcal{P}-programs). A ww-RAM program is called a P\mathcal{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),T = T_{\mathrm{R}} + T_{\mathrm{RAM}} + T_{\mathrm{P}} = \operatorname{poly}(w),

where TRT_{\mathrm{R}} and TPT_{\mathrm{P}} denote the numbers of executed READ and PRINT instructions, and TRAMT_{\mathrm{RAM}} is an upper bound on the number of executed RAM instructions;

  1. the program uses ρ=O(T)=poly⁡(w)\rho= O(T) = \operatorname{poly}(w) registers, indexed from 0 to ρ−1\rho- 1;

  1. on every admissible tuple of TRT_R input values, the program halts within these bounds, reads exactly TRT_R values, and produces exactly TPT_P non-negative outputs smaller than 2w−12^{w-1};

  1. 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}\{0,\ldots,\rho- 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≥1T_{\mathrm{RAM}} \ge1, 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\mathcal{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}S_{\mathrm{in}} = \{\mathit{in}_1,\ldots,\mathit{in}_{T_R}\}, Sout={out1,…,outTP}S_{\mathrm{out}} = \{\mathit{out}_1,\ldots,\mathit{out}_{T_P}\}, so that ∣Sin∣+∣Sout∣=TR+TP=poly⁡(w)\lvert S_{\mathrm{in}}\rvert+ \lvert S_{\mathrm{out}}\rvert= T_R + T_P = \operatorname{poly}(w). Each input and output set has fewer than 2w−12^{w-1} agents. In contrast, the ww-RAM model uses binary representations of numbers, which we also found convenient for simulating ww-RAM computations. Our simulation therefore converts the input values from unary to binary before emulating the P\mathcal{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 TRT_R registers, and the results are collected in an output array of TPT_P registers before being converted to unary. Together with O(1)O(1) auxiliary registers, the total number of registers in the simulation is therefore ρ′=ρ+TR+TP+O(1)=poly⁡(w)\rho' = \rho+ T_R + T_P + O(1) = \operatorname{poly}(w). The total binary input length is O(TRw)O(T_Rw) and need not equal ww.

During the simulation, the population must accommodate the unary input and output values, the system of weights, which consists of 2w−1−12^{w-1} - 1 agents (see Subsection 3.3), and the ρ′w\rho'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)n_w = C((T_R + T_P + 1)2^w + \rho'w), where C>1C > 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/Cn_w/C such agents.

Fact 1. For n≥nwn \ge n_w, at least (1−1/C)n(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 TRT_R, TPT_P, and ρ′\rho' are poly⁡(w)\operatorname{poly}(w), the following relations hold.

Fact 2. We have log⁡nw=w+O(log⁡w)=Θ(w)\log n_w = w + O(\log w) = \Theta(w) and, in particular, log⁡nw<2w\log n_w < 2w for all sufficiently large ww.

For sufficiently large ww, all ρ′=poly⁡(w)\rho' = \operatorname{poly}(w) register addresses fit in non-negative ww-bit words. Our main result is the following theorem.

Theorem 1. Every P\mathcal{P}-program admits an efficient simulation by a silently stabilising probabilistic population protocol. For all sufficiently large ww and population size nwn_w, the simulation stabilises, both in expectation and with high probability, in O(w2(TRw+TRAM+TP))O(w^2(T_Rw + T_{\mathrm{RAM}} + T_P)) time, using O(ρ′w2(TRw+TRAM+TP))O(\rho'w^2(T_Rw + T_{\mathrm{RAM}} + T_P)) states.

Proof. By Theorem 3, there is an efficient MC+ simulation protocol that completes whp in O(w(TRw+TRAM+TP))O(w(T_{R}w+T_{\mathrm{RAM}}+T_{P})) rounds, each lasting Θ(log⁡n)=Θ(w)\Theta(\log n)=\Theta(w) time, plus one register initialisation round of O(ρ′w)O(\rho' w) time, and uses O(ρ′w2(TRw+TRAM+TP))O(\rho' w^{2}(T_{R}w+T_{\mathrm{RAM}}+T_{P})) states. By Theorem 8, there is a silently stabilising backup simulation protocol with expected time O(n2w)O(n^{2w}) using O(ρ′w2)O(\rho' w^{2}) 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)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(TRw+TRAM+TP))A=O(\rho' w+w^{2}(T_{R}w+T_{\mathrm{RAM}}+T_{P})), choosing the failure exponent η\eta sufficiently large gives expected time at most A+n−ηD(n)=O(A)A+n^{-\eta}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)\rho'=O(T) and T≤TRw+TRAM+TPT\leq T_{R}w+T_{\mathrm{RAM}}+T_{P}, so register initialisation is absorbed in the stated time bound.

The protocol requires the P\mathcal{P}-program, its word length ww, and the parameters TRT_{R}, TRAMT_{\mathrm{RAM}}, TPT_{P}, and ρ\rho. The analysis uses only w=Θ(log⁡n)w=\Theta(\log n), which holds for n=nwn=n_{w} by Fact 2. It therefore applies without change to every population size n≥nwn\geq n_{w} with log⁡n=Θ(w)\log n=\Theta(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)\log n=\Theta(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\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.

General Simulation Scheme

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

High-level structure of the P-program simulation

Figure 1. High-level structure of the P\mathcal{P}-program simulation.

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\mathcal{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 ipip and coordinates the emulation of the current instruction. The fixed code requires only O(1)O(1) states for ipip and its direct addresses (Example 1, page 7). After the last instruction, ipip is set to END.

The following example illustrates how an instruction of the program, determined by the leader’s ipip, is realised by transition rules that additionally depend on auxiliary state components.

Example 1. Suppose that register rr 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 auxiliary component, say the colour red. Since rr and □\square are determined by ipip, 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; □)(L;\,\mathrm{red};\,ip=7) + (r;\,\mathrm{red};\,v) \to(L;\,\mathrm{red};\,ip=8) + (r;\,\mathrm{red};\,\square)

for every value vv. Interactions in which the colours differ leave both agents unchanged.

Registers

Each of the ρ′\rho' registers is represented by ww distinct agents in states (R;r,i,b)(R;r,i,b), where r∈{0,…,ρ′−1}r \in\{0,\ldots,\rho'-1\} is the register address, ii the bit index, and bb 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, ρ′\rho', and ww.

Result: Initialised registers indexed by 0,1,…,ρ′−10,1,\ldots,\rho'-1, each consisting of ww bits.

  1. function RegInit()

  2. for r←0r \gets0 to ρ′−1\rho'-1 do

  3. for i←0i \gets0 to w−1w-1 do

  4. The leader assigns the ii-th bit of register rr to the first free agent it encounters:

  5. L+φ→L+(R;r,i,0)L+\varphi\to L+(R;r,i,0). ▹\triangleright φ\varphi 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 ρ′\rho' registers of ww bits each, in O(ρ′w)O(\rho'w) time both in expectation and whp.

Proof. Put M=ρ′wM=\rho'w and p=1−1/Cp=1-1/C. Until allocation finishes, each interaction assigns the next bit with probability at least 2p/n2p/n. Its duration is therefore stochastically dominated by the time needed for MM successes in Bernoulli trials with success probability 2p/n2p/n, giving expected time at most M/(2p)=O(M)M/(2p)=O(M). After dnMdnM interactions, a Chernoff bound gives fewer than MM successes with probability e−Ω(M)=n−Ω(1)e^{-\Omega(M)}=n^{-\Omega(1)}, for a sufficiently large constant dd, since M≥w=Θ(log⁡n)M\ge w=\Theta(\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. □\square

Input and Output Conversion

The ii-th input variable, with value ki<2w−1k_i<2^{w-1}, is given in unary by kik_i agents in state iniin_i; before emulating RAM instructions, the protocol converts it to binary and stores it in register riinr_i^{in} of an input array occupying a fixed range of consecutive addresses, with an additional pointer register rpinrp_{in}. Every READ(rd)(rd) is replaced by COPY(i,rpin,d,rd)(i,rp_{in},d,rd), INC(rpin)(rp_{in}) (INC increments a register, see Subsection 2.2), and analogously every PRINT(rs)(rs) by COPY(d,rs,i,rpout)(d,rs,i,rp_{out}), INC(rpout)(rp_{out}), which writes to an output array r1out,…,rTPoutr_1^{out},\ldots,r_{\mathit{TP}}^{out} with pointer rpoutrp_{out}; the pointers are initialised by two LOAD instructions as the arrays have fixed addresses. The resulting modified PP-program still has fixed length, performs no input/output instructions and executes at most TRAM+2(TR+TP)+2T_{RAM}+2(T_R+T_P)+2 RAM instructions; only after it has been emulated are the values in the output array converted from 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\mathcal{P}-program, the protocol converts the input data from unary to binary. To store and access the converted input values, we use TR+1T_R + 1 auxiliary registers: an input array r1in,r2in,…,rTRinr^{in}_1, r^{in}_2, \ldots, r^{in}_{T_R} and an additional register rpinr_{pin} containing a pointer to the next entry of the input array. The input array occupies a fixed range of consecutive addresses, with riinr^{in}_i at its ii-th position. The ii-th integer input variable, with value ki<2w−1k_i < 2^{w-1}, is represented in unary by a subpopulation of kik_i agents in state iniin_i. After the conversion, its binary representation is stored in register riinr^{in}_i.

Once all input data has been converted and stored in the input array, we replace every instruction READ⁡(rd)\operatorname{READ}(r_d) of the P\mathcal{P}-program with the pair of instructions COPY⁡(i,rpin,d,rd)\operatorname{COPY}(i,r_{pin},d,r_d), INC⁡(rpin)\operatorname{INC}(r_{pin}). The first copies the input-array entry pointed to by rpinr_{pin} into register rdr_d, and the second advances the pointer. To make rpinr_{pin} initially point to the first entry of the input array, the modified program starts with LOAD⁡(r1in,rpin)\operatorname{LOAD}(r^{in}_1,r_{pin}). The INC⁡(r)\operatorname{INC}(r) instruction increments the value of register rr by one; it is not an instruction of Table 1, but it is emulated in the same way as ADD⁡\operatorname{ADD}, see Subsection 2.2. This preprocessing is essential for our backup simulation. Similarly, instead of performing binary-to-unary conversion on the fly during printing, we place the printed values in consecutive entries of the output array r1out,r2out,…,rTPoutr^{out}_1,r^{out}_2,\ldots,r^{out}_{T_P}, which also occupies a fixed range of consecutive addresses, by replacing every instruction PRINT⁡(rs)\operatorname{PRINT}(r_s) with COPY⁡(d,rs,i,rpout)\operatorname{COPY}(d,r_s,i,r_{pout}), INC⁡(rpout)\operatorname{INC}(r_{pout}). Analogously, this requires TP+1T_P + 1 auxiliary registers, including the pointer register rpoutr_{pout}, which is initialised by LOAD⁡(r1out,rpout)\operatorname{LOAD}(r^{out}_1,r_{pout}) at the start of the program.

We thus obtain a RAM program, referred to as the modified P\mathcal{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)+2T_{\mathrm{RAM}} + 2(T_R + T_P) + 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 TPT_P 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.

State Organisation

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

RoleComponentsUsed in
input (permanent role)input state iniin_iboth
leader (L)(L)ipip, register and bit index, O(1)O(1) memoryboth
register (R)(R)(r,i,b)(r,i,b): register index, bit index, bit valueboth
outputoutput state outiout_iboth
free (φ)(\varphi)request/response components of GET/PUTMC+
weight (P)(P)weight index kk of PkP_kMC+
helper (H)(H)counter of interactions with the leaderbackup
every agentclock component: round tt, phase xxMC+
every agentrankbackup

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.

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.

SubroutineDescription
PUT(r,i,b)(r,i,b)sets the ii-th bit of register rr to bb
GET(r,i)(r,i)returns the value of the ii-th bit of register rr

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)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 ipip indicating the current instruction, and emulates the program step by step using the reductions below. Unless ipip 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)O(\rho' w) to the number of leader and working set agents states, whereas the remaining reductions, given below, require only O(w)O(w) additional leader states.

Indirect and direct copy COPY⁡(⋅)\operatorname{COPY}(\cdot). To implement both Cook–Reckhow variants of the copy instruction, we first reduce them to two simpler subroutines: SET⁡(r,rp)\operatorname{SET}(r,rp) and the direct COPY⁡(rs,rd)\operatorname{COPY}(rs,rd). The former obtains the value stored in register rprp by successive GET⁡(rp,i)\operatorname{GET}(rp,i) subroutines and stores it in the leader’s state as the register index rr, while the latter performs a direct copy of the contents of register rsrs into register rdrd. The address bound is amax⁡=ρa_{\max}=\rho for source instructions and amax⁡=ρ′a_{\max}=\rho' for trusted input/output wrappers, as determined by the fixed control context. SET checks all ww bits and rejects an index outside {0,…,amax⁡−1}\{0,\ldots,a_{\max}-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⁡a_{\max}, so this check uses O(ρ′)O(\rho') index states.

Protocol 2 SET⁡(r,rp)\operatorname{SET}(r,rp)

Input: rprp: register; rr: leader’s index

Result: Valid r=[rp]r=[rp], or INVALIDADDRESS

  1. function SET⁡(r,rp)\operatorname{SET}(r,rp)

  2. r←0r\leftarrow0

  3. for i←0i\leftarrow0 to w−1w-1 do

  4. b←GET⁡(rp,i)b\leftarrow\operatorname{GET}(rp,i)

  5. if b=1b=1 and r+2i≥amax⁡r+2^i\ge a_{\max} then

  6. return INVALIDADDRESS

  7. r←r+2ibr\leftarrow r+2^i b

Protocol 3 COPY⁡(rs,rd)\operatorname{COPY}(rs,rd)

Input: rs,rdrs,rd: registers

Result: [rd]=[rs][rd]=[rs]

  1. function COPY⁡(rs,rd)\operatorname{COPY}(rs,rd)

  2. for i←0i\leftarrow0 to w−1w-1 do

  3. b←GET⁡(rs,i)b\leftarrow\operatorname{GET}(rs,i)

  4. PUT⁡(rd,i,b)\operatorname{PUT}(rd,i,b)

Using these two building blocks, the instructions COPY⁡(i,rp,d,rd)\operatorname{COPY}(i,rp,d,rd) and COPY⁡(d,rs,i,rp)\operatorname{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)\operatorname{SET}(r,rp), and then performing a direct copy.

Here we give the pseudocode of the reductions of COPY⁡(i,rp,d,rd)\operatorname{COPY}(i,rp,d,rd) and COPY⁡(d,rs,i,rp)\operatorname{COPY}(d,rs,i,rp).

Protocol 4 COPY⁡(i,rp,d,rd)\operatorname{COPY}(i,rp,d,rd)

Input: rp,rdrp,rd - pointers to registers, i,di,d - indirect/direct flags

Result: Register rdrd stores the contents of register r=[rp]r=[rp]

  1. function COPY⁡(i,rp,d,rd)\operatorname{COPY}(i,rp,d,rd)

  2. SET⁡(r,rp)\operatorname{SET}(r,rp)

  3. COPY⁡(r,rd)\operatorname{COPY}(r,rd)

Protocol 5 COPY⁡(d,rs,i,rp)\operatorname{COPY}(d,rs,i,rp)

Input: rs,rprs,rp - pointers to registers, i,di,d - indirect/direct flags

Result: Register r=[rp]r=[rp] stores the contents of register rsrs

  1. function COPY⁡(d,rs,i,rp)\operatorname{COPY}(d,rs,i,rp)

  2. SET⁡(r,rp)\operatorname{SET}(r,rp)

  3. COPY⁡(rs,r)\operatorname{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 ipip indicating the instruction currently being executed, and emulates the program step by step using the reductions below. Unless ipip is explicitly modified by an instruction, the leader increments it by 1 after completing the instruction.

Conditional jump JGE(r,Iz)\mathrm{JGE}(r, I_z). The conditional jump instruction is reduced to a single call to GET(r,w−1)\mathrm{GET}(r, w-1), which retrieves the most significant bit of register rr. 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 IzI_z; otherwise, it proceeds to the next instruction ip+1ip+1. The Cook-Reckhow model [29] instead tests whether the register content is positive; each test is expressible by the other with O(1)O(1) instructions.

Protocol 6 JGE(r,Iz)\mathrm{JGE}(r, I_z)

Input: rr - pointer to a register, IzI_z - program instruction index Result: Jump to instruction IzI_z if the content of rr is non-negative

  1. function JGE(r,Iz)\mathrm{JGE}(r, I_z)

  2. b←GET(r,w−1)b \leftarrow\mathrm{GET}(r, w-1)

  3. if b=0b=0 then ip←Izip \leftarrow I_z

Loading a constant into a register LOAD(C,rd)\mathrm{LOAD}(C, r_d). Let c0,c1,…,cw−1c_0, c_1, \ldots, c_{w-1} be the complete ww-bit U2 representation of a predefined constant CC, encoded in the transition function, ordered from the least to the most significant bit. The reduction for the LOAD(C,rd)\mathrm{LOAD}(C, r_d) instruction assigns the value CC to register rdr_d bit by bit, where in each iteration ii the agent representing the ii-th bit of rdr_d adopts value cic_i via PUT(rd,i,ci)\mathrm{PUT}(r_d, i, c_i). Constants independent of ww need only a fixed number of bits in the program code and the transition function; for larger ww, they are extended by copies of the sign bit.

Protocol 7 LOAD(C,rd)\mathrm{LOAD}(C, r_d)

Input: C=c0…cw−1C=c_0\ldots c_{w-1} - a constant in U2, rdr_d - pointer to a register Result: Register rdr_d contains the value CC

  1. function LOAD(C,rd)\mathrm{LOAD}(C, r_d)

  2. for i←0i \leftarrow0 to w−1w-1 do

  3. PUT(rd,i,ci)\mathrm{PUT}(r_d, i, c_i)

Addition and subtraction ADD(rs1,rs2,rd)\mathrm{ADD}(r_{s1}, r_{s2}, r_d) and SUB(rs1,rs2,rd)\mathrm{SUB}(r_{s1}, r_{s2}, r_d). Both instructions are emulated bit by bit: at each position, the leader retrieves the two source bits using GET\mathrm{GET}, computes the result bit and the new carry locally, and writes the result bit using PUT\mathrm{PUT}. The final carry is discarded, so the operations are performed modulo 2w2^w; in particular, signed overflow wraps around, as is standard for U2 arithmetic.

Protocol 8 ADD(rs1,rs2,rd)\mathrm{ADD}(r_{s1}, r_{s2}, r_d)

Input: rs1,rs2,rdr_{s1}, r_{s2}, r_d - pointers to registers Result: Register rdr_d stores the ww-bit sum of the values of registers rs1,rs2r_{s1}, r_{s2}

  1. function ADD(rs1,rs2,rd)\mathrm{ADD}(r_{s1}, r_{s2}, r_d)

  2. carry←0\mathrm{carry} \leftarrow0

  3. for i←0i \leftarrow0 to w−1w-1 do

  4. b1←GET(rs1,i)b_1 \leftarrow\mathrm{GET}(r_{s1}, i)

  5. b2←GET(rs2,i)b_2 \leftarrow\mathrm{GET}(r_{s2}, i)

  6. b←(b1+b2+carry) mod 2,carry←⌊(b1+b2+carry)/2⌋b \leftarrow(b_1+b_2+\mathrm{carry}) \bmod2,\quad\mathrm{carry} \leftarrow\left\lfloor(b_1+b_2+\mathrm{carry})/2 \right\rfloor

  7. PUT(rd,i,b)\mathrm{PUT}(r_d, i, b)

Subtraction uses the U2 identity a−b=a+¬b+1a-b=a+\lnot b+1.

Protocol 9 SUB(rs1,rs2,rdrs1,rs2,rd)

Input: rs1,rs2,rdrs1,rs2,rd - pointers to registers Result: Register rdrd stores the ww-bit difference of the values of registers rs1,rs2rs1,rs2

  1. function SUB(rs1,rs2,rdrs1,rs2,rd)

  2. carry ←1\leftarrow1

  3. for i←0i \leftarrow0 to w−1w-1 do

  4. b1←GET⁡(rs1,i)b1 \leftarrow\operatorname{GET}(rs1,i)

  5. b2←GET⁡(rs2,i)b2 \leftarrow\operatorname{GET}(rs2,i)

  6. b←(b1+(1−b2)+carry) mod 2,carry←⌊(b1+(1−b2)+carry)/2⌋b \leftarrow(b1+(1-b2)+carry)\bmod2,\quad carry \leftarrow\lfloor(b1+(1-b2)+carry)/2\rfloor

  7. PUT⁡(rd,i,b)\operatorname{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)\operatorname{INC}(r) and DEC⁡(r)\operatorname{DEC}(r), which increase and decrease the content of register rr 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 2w2w atomic subroutines. Table 4 and Fact 3 summarise the reductions.

InstructionReductionAtomic subroutines
JGE(r,Izr,I_z)read the sign bit1
LOAD(C,rdC,rd)write the ww bits of CCww
COPY(i,rp,d,rdi,r_p,d,r_d), COPY(d,rs,i,rpd,r_s,i,r_p)SET, then direct copy≤3w\le3w
ADD(rs1,rs2,rdrs1,rs2,rd), SUB(rs1,rs2,rdrs1,rs2,rd)bitwise, with carry3w3w
INC(rr), DEC(rr)bitwise, with carry2w2w

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 3w3w atomic subroutines GET() and PUT().

Efficient MC+ Simulation

Overview

The efficient simulation is an MC+ protocol [45]: whp it is correct and terminates in poly⁡(w)\operatorname{poly}(w) time; otherwise, it signals a protocol or clock anomaly. Two results of [45] 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 [45] 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 a correct execution becomes silent. We prove the following theorem, and all other claims of this section, below.

Theorem 3. For every PP-program, there exists an efficient MC+ population protocol that, whp, correctly simulates the program in τ=O(w(TRw+TRAM+TP))\tau= O(w (T_{\mathrm{R}}w + T_{\mathrm{RAM}} + T_{\mathrm{P}})) rounds of Θ(w)\Theta(w) time each, plus one register initialisation round lasting O(ρ′w)O(\rho' w) time. The protocol uses O(ρ′wτ)=O(ρ′w2(TRw+TRAM+TP))O(\rho' w\tau) = O(\rho' w^2 (T_{\mathrm{R}}w + T_{\mathrm{RAM}} + T_{\mathrm{P}})) states.

Besides leader election, adopted from [45], the MC+ simulation rests on four techniques.

(1) Bit access in one round. By Subsection 2.2, every RAM instruction reduces to at most 3w3w calls of PUT and GET, so it suffices to make a single bit access fast and anomaly-detecting. In the MC+ variants PUT⁡E(r,i,b)\operatorname{PUT}^{\mathrm{E}}(r,i,b) and GET⁡E(r,i)\operatorname{GET}^{\mathrm{E}}(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,⋅)(R;r,i,\cdot), which holds the ii-th bit of register rr, applies the update or, for GET⁡E\operatorname{GET}^{\mathrm{E}}, 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 PUT⁡E\operatorname{PUT}^{\mathrm{E}} 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 3w3w rounds per instruction (Lemma 5).

(2) A cheaper clock. In [45], rounds advance by counting leader interactions, which multiplies the leader’s states by Θ(log⁡n)\Theta(\log n) per round. We count interactions only during MC+ leader election (Θ(w)\Theta(w) rounds, O(w2)O(w^2) states; Theorem 6). Register initialisation, whose duration O(ρ′w)O(\rho' w) may exceed Θ(log⁡n)\Theta(\log n), then occupies a single long round, after which the protocol switches to the improved clock based on the phase-clock mechanism of [11] with a constant number of phases. Each round then costs O(1)O(1) states and lasts Θ(w)\Theta(w) time, and whp contains an interval of Ω(log⁡n)\Omega(\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−2P_0,\ldots,P_{w-2} with ∣Pk∣=2k|P_k| = 2^k, whose unions represent every value below 2w−12^{w-1}. Since ww is known, we replace the sequential O(log⁡n)O(\log n)-round construction of [45] by a parallel single-round one: a delegating agent hands mass 2k2^k of PkP_k to a fresh agent for k=w−2,…,1k = w-2,\ldots,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 ww with fewer than nn leaves, so a Chernoff and union bound give completion whp in one round, with Θ(w2)\Theta(w^2) states (Lemma 3).

(4) Conversion by binary search. Extending the parity computation of [45] from one bit to retrieving all ww bits, U2Bconversion⁡E(i)\operatorname{U2Bconversion}^{\mathrm{E}}(i) determines ∣Xi∣|X_i| bit by bit from the most significant one: it adds PℓP_\ell to an auxiliary subpopulation ZZ and compares ∣Z∣|Z| with ∣Xi∣|X_i| by the MC+ majority protocol (Theorem 7), keeping PℓP_\ell and writing bit 1 if ∣Z∣≤∣Xi∣|Z| \le|X_i|, and otherwise removing it and writing 0; this takes O(w2)O(w^2) rounds per input variable (Lemma 6). The invariant is 0≤∣Xi∣−∣Z∣<2ℓ+10 \le|X_i| - |Z| < 2^{\ell+1} before bit ℓ\ell, initially ℓ=w−2\ell= w-2 and Z=∅Z = \varnothing. The comparison and choice reduce the residual to [0,2ℓ)[0,2^\ell); after bit 0 it is zero. The untouched sign bit remains 0 from register initialisation, so the stored word equals ∣Xi∣|X_i|. Conversely, each weight acts as a stamp: for each bit ℓ\ell of rioutr_i^{\mathrm{out}} equal to 1, every agent of PℓP_\ell adopts an additional component outi\mathrm{out}_i and then passes it to a free agent, so all 2ℓ2^\ell copies are stamped in parallel and 2ℓ2^\ell output agents are created in one round, while PℓP_\ell is preserved for later use (Lemmas 7 and 8).

Summing over the stages gives τ\tau rounds, dominated by conversions and program emulation. The state bound O(ρ′wτ)O(\rho' w\tau) 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))\Theta(\min(\rho',w)).

Theorem 4. The MC+ simulation of Theorem 3 can be implemented in the same number of rounds and with O((ρ′+w)τ)O((\rho' + w)\tau) states.

The key idea is a fixed schedule. We pad every instruction emulation and every output conversion to exactly 3w3w 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(ρ′)O(\rho') states per round. Register agents, whose identities (r,i,b)(r,i,b) alone take Θ(ρ′w)\Theta(\rho'w) states, instead count coarse-grained rounds, one per pass of at least ww rounds, and keep an O(1)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)O(\tau/w) passes, register agents use O(ρ′τ)O(\rho'\tau) states. Combining Theorem 4 with the backup of § 4 via Theorem 2(ii) improves the state bound of Theorem 1 accordingly.

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 [45] composed of MC+ subprotocols that implement successive operations of the simulated P\mathcal{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−22^0,2^1,\ldots,2^{w-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\operatorname{poly}(w)=\operatorname{poly}\log n time and uses poly⁡(w)\operatorname{poly}(w) states, with both bounds depending on the running time and space usage of the simulated P\mathcal{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 § 4.

The fast execution is bounded even on faulty histories. We pad the modified program’s execution to

T∗=TRAM+2(TR+TP)+2T^* = T_{\mathrm{RAM}} + 2(T_R + T_P) + 2

instruction slots, using 3w3w 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.

Protocol 10 MC+ Simulation Protocol

Input: A modified P\mathcal{P}-program; T=TR+TRAM+TPT = T_R + T_{\mathrm{RAM}} + T_P, ρ′\rho', ww; a leaderless population of nn agents

Result: Correct simulation of the given program whp, or an eventual Anomaly signal otherwise

  1. function MC+ Simulation

  2. LeaderElection

  3. RegInit(ρ′,w)(\rho', w)

  4. WeightCreation(w)(w)

  5. for i←1i \leftarrow1 to TRT_R do

  6. U2BConversione(i)^{e}(i) ▷ unary-to-binary conversion of ii-th input

  7. ip←0ip \leftarrow0

  8. for each of the T∗T^{*} prescribed instruction slots do

  9. if ip≠ENDip \ne\mathrm{END} then

  10. Emulate the RAM instruction indicated by ipip and update ipip.

  11. Pad the slot with idle rounds to a total of 3w3w rounds.

  12. if ip≠ENDip \ne\mathrm{END} then signal Anomaly

  13. for i←1i \leftarrow1 to TPT_P do

  14. B2UConversione(i)^{e}(i) ▷ binary-to-unary conversion of ii-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\mathcal{P}-program, there exists an efficient MC+ population protocol that, whp, correctly simulates the program in τ=O(w(TRw+TRAM+TP))\tau= O(w (T_Rw + T_{\mathrm{RAM}} + T_P)) rounds of Θ(w)\Theta(w) time each, plus one register initialisation round lasting O(ρ′w)O(\rho' w) time. The protocol uses O(ρ′wτ)=O(ρ′w2(TRw+TRAM+TP))O(\rho' w\tau) = O(\rho' w^2 (T_Rw + T_{\mathrm{RAM}} + T_P)) states.

MC+ Protocols: Overview and Refinements

MC+ protocols were introduced in [45]. They are fast Monte Carlo population protocols that execute correctly whp in poly⁡(log⁡n)\operatorname{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)\Theta(\log n) = \Theta(w) time whp. In the original MC+ construction [45], rounds advance by counting leader interactions, which increases the number of leader states by a factor of Θ(log⁡n)\Theta(\log n).

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 [11]. By Theorem 1 of [11], this mechanism can provide intervals of length Θ(log⁡n)\Theta(\log n) whp, with an arbitrarily large constant lower bound on their duration. We implement the clock using a constant number mm of phases. Each agent has a clock component of the form (L∣F,t,x)(L|F,t,x), where LL and FF denote a leader and a follower, respectively, tt is the current round, and x∈{1,…,m}x \in\{1,\ldots,m\} is the current phase.

The clock transitions are as follows, where ⋆\star denotes either LL or FF:

(⋆,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.\begin{aligned} (\star,t,x) + (F,t,y) &\to(\star,t,x) + (F,t,x), && \text{if } y < x,\\ (\star,t+1,x) + (F,t,y) &\to(\star,t+1,x) + (F,t+1,x),\\ (L,t,x) + (F,t,x) &\to(L,t,x+1) + (F,t,x), && \text{if } x < m,\\ (L,t,m) + (F,t,m) &\to(L,t+1,1) + (F,t,m),\\ (\star,t',x) + (\star,t,y) &\to\text{clock Anomaly}, && \text{if } |t' - t| > 1. \end{aligned}

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)(t',y) is lexicographically later than the leader’s (t,x)(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 [11] with its epidemic propagation bound yields the following guarantee.

Theorem 5. For any fixed constants a,c,η>0a,c,\eta> 0, there exist constants mm and DD, depending only on a,c,ηa,c,\eta, such that the following holds for all sufficiently large nn. Starting from the standard phase-clock initialisation with a unique leader, with probability at least 1−n−η1-n^{-\eta}, each of the first nan^a rounds lasts at most Dlog⁡nD\log n time and contains an interval of at least clog⁡nc\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-of-leader follower triggers the additional check in expected time O(n)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)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)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)O(\rho' 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)A = O(\rho' w + \tau\log n) is a high-probability bound for successful completion of the fast simulation and D(n)=nO(1)D(n) = n^{O(1)} bounds the expected remaining detection, switching, and backup time from any reachable configuration, then

E[stabilisation time]≤A+n−ηD(n)=O(A),\mathbb{E}[\text{stabilisation time}] \le A + n^{-\eta}D(n) = O(A),

by choosing the failure exponent η\eta larger than the fixed degree in DD. 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 [45], 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 [45]]

(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 [45] 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 [45], which is based on a scheme used in several prior works [11 GS21, 19]. It operates over Θ(log⁡n)\Theta(\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 ww. 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)O(n).

Theorem 6. There exists an MC+ leader election protocol that elects a unique leader whp in Θ(log⁡n)=Θ(w)\Theta(\log n)=\Theta(w) rounds and uses O(log⁡2n)=O(w2)O(\log^2 n)=O(w^2) states.

Proof. Correctness and round complexity follow from Theorem 4 of [45] and the relation w=Θ(log⁡n)w=\Theta(\log n). The state bound accounts for the clock that counts leader interactions. This clock requires Θ(log⁡n)=Θ(w)\Theta(\log n)=\Theta(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−2P_0,P_1,\ldots,P_{w-2}, where ∣Pi∣=2i|P_i|=2^i. Together, these sets contain 2w−1−12^{w-1}-1 agents, allowing unions of weights to represent every integer from 0 to 2w−1−12^{w-1}-1, that is, every non-negative ww-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 ww, 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 [45]. Whereas that protocol creates weights sequentially over O(log⁡n)O(\log n) rounds, ours creates all w−1w-1 weights in a single round.

The protocol WeightCreation(w)\mathsf{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)p^*(w-2). The subsequent weight creation process is governed by the following transitions:

p∗(k)+φ→p∗(k−1)+pk(k),for k>1,(1)p^{*}(k) + \varphi\to p^{*}(k-1) + p_k(k), \qquad\text{for } k > 1, \tag*{(1)}
p∗(1)+φ→p0(0)+p1(1),(2)p^{*}(1) + \varphi\to p_0(0) + p_1(1), \tag*{(2)}
pk(i)+φ→pk(i−1)+pk(i−1),for i>0.(3)p_k(i) + \varphi\to p_k(i-1) + p_k(i-1), \qquad\text{for } i > 0. \tag*{(3)}

We say that an agent in state pk(i)p_k(i) holds mass 2i2^i belonging to weight PkP_k. The total mass of PkP_k is 2k2^k, initially held by a single agent in state pk(k)p_k(k). This mass is repeatedly split until it is distributed among 2k2^k agents, each holding unit mass.

The agent in state p∗(k)p^{*}(k) is responsible for initiating the creation of Pk,Pk−1,…,P0P_k,P_{k-1},\ldots,P_0. When k>1k > 1, an interaction with a free agent assigns the entire mass 2k2^k of PkP_k to that agent, which adopts state pk(k)p_k(k), according to rule (1). At the same time the delegating agent adopts state p∗(k−1)p^{*}(k-1) and continues with the remaining weights. Rule (2) completes this delegation process by initiating P1P_1 and creating P0P_0. Thus, the creation of weights is initiated while the previously assigned masses are being split. Within each weight PkP_k, splitting proceeds according to rule (3). An agent in state pk(i)p_k(i) with i>0i > 0 divides its mass equally with a free agent, leaving both in state pk(i−1)p_k(i-1). The process ends when all agents in PkP_k hold unit mass, that is, when they are in state pk(0)p_k(0).

All w−1w-1 weights are created whp in one round. Labelling the created weights requires w=Θ(log⁡n)w = \Theta(\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)p_k(i) or p∗(i)p^{*}(i), for i>0i > 0 and k∈{1,…,w−2}k \in\{1,\ldots,w-2\}. In the absence of an anomaly, the result of the protocol is the family of sets PkP_k for k=0,…,w−2k = 0,\ldots,w-2, where PkP_k consists of agents in state pk(0)p_k(0).

Lemma 3. The protocol WeightCreation(ww) correctly creates weights P0,P1,…,Pw−2P_0,P_1,\ldots,P_{w-2} whp in one round and signals an Anomaly otherwise. It uses Θ(w2)\Theta(w^2) states.

Proof. We follow the approach of [45]. By the choice of population size, at least (1−1/C)n(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/C1-1/C.

After the leader’s initial delegation, the construction can be represented by a binary tree rooted at p∗(w−2)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 the same weight. The tree has ∑k=0w−22k=2w−1−1\sum_{k=0}^{w-2}2^k = 2^{w-1}-1 leaves, corresponding to the final unit-mass agents, and every root-to-leaf path has at most w−1w-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(1-1/C)/n. Hence, over cnlog⁡ncn\log n interactions, progress along the path is bounded below by a binomial process of mean (1−1/C)clog⁡n(1-1/C)c\log n, until the path is complete. Since w=Θ(log⁡n)w = \Theta(\log n), a Chernoff bound shows that the probability of completing fewer than the required ww transitions is at most n−η−1n^{-\eta-1} for a sufficiently large constant cc. A union bound over the fewer than nn root-to-leaf paths shows that all weights are created whp in O(log⁡n)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)p^{*}(k) and pk(i)p_k(i), with $0 \le i \le k < w$, require Θ(w2)\Theta(w^2) states.

MC+ Majority Let AA and BB be two subpopulations of a population of nn agents. The majority problem is to determine whether ∣A∣>∣B∣|A| > |B|, ∣A∣<∣B∣|A| < |B|, or ∣A∣=∣B∣|A| = |B|. The MC+ majority protocol [45] 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 become two agents with the same bias. These operations double the remaining bias over successive phases. The protocol runs for Θ(log⁡n)\Theta(\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 ww. Apart from the clock, the protocol requires only O(1)O(1) additional states per agent.

We believe that the best-known majority protocol [36], with O(log⁡n)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)\Theta(\log n) = \Theta(w) rounds and uses Θ(log⁡n)=Θ(w)\Theta(\log n) = \Theta(w) states.

Proof. Correctness and round complexity follow from Theorem 6 of [45] and the relation w=Θ(log⁡n)w = \Theta(\log n). The computation requires only O(1)O(1) additional states per round [45]. At this stage, the clock uses O(1)O(1) states per round, so tracking the Θ(w)\Theta(w) rounds requires Θ(w)\Theta(w) states in total. □\square

Register Initialisation The leader participates in an average of two interactions per unit of time. By Lemma 2, initialising ρ′=poly⁡(log⁡n)\rho' = \operatorname{poly}(\log n) registers takes O(ρ′w)O(\rho'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)\Theta(\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.

MC+ Emulation of RAM Instructions

In this subsection, we introduce efficient MC+ variants, PUTe\mathrm{PUT}^{\mathrm e} and GETe\mathrm{GET}^{\mathrm e}, 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)\mathrm{PUT}^{\mathrm e}(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 ii-th bit of register rdrd is to be set to bb. 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. Protocol 11 PUTE(rd,i,b)^{\mathrm{E}}(rd, i, b)

Input: rdrd - register pointer, ii - bit index, b∈{0,1}b \in\{0,1\}

Result: The ii-th bit of register rdrd is set to bb

  1. function PUTE(rd,i,b)^{\mathrm{E}}(rd, i, b)

  2. The leader adopts component (put,rd,i,b)(put, rd, i, b) at the start of round tt.

  3. upon entering round tt a follower adopts component (put)(put),

  4. if both agents are in round tt then

  5. (φ;put)+(φ∣L;put,rd,i,b)→(φ;put,rd,i,b)+(φ∣L;put,rd,i,b),(\varphi; put) + (\varphi|L; put, rd, i, b) \to(\varphi; put, rd, i, b) + (\varphi|L; put, rd, i, b),

  6. (R;put,rd,i,b′)+(φ;put,rd,i,b)→(R;rd,i,b)+(φ;put,rd,i,b).(R; put, rd, i, b') + (\varphi; put, rd, i, b) \to(R; rd, i, b) + (\varphi; put, rd, i, b).

  7. if both agents are in round tt and (rd′,i′)≠(rd,i)(rd', i') \ne(rd, i) then

  8. (R;put,rd′,i′,b′)+(φ;put,rd,i,b)→(R;rd′,i′,b′)+(φ;put,rd,i,b).(R; put, rd', i', b') + (\varphi; put, rd, i, b) \to(R; rd', i', b') + (\varphi; put, rd, i, b).

  9. if a register agent still holds component (put)(put) at the end of round tt then

  10. signal ANOMALY

The GETE(rs,i)^{\mathrm{E}}(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,?)(get, rs, i, ?), requesting the value of the ii-th bit of register rsrs, 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)^{\mathrm{E}}(rs, i)

Input: rsrs - register pointer, ii - bit index

Result: The leader learns the ii-th bit of register rsrs

  1. function GETE(rs,i)^{\mathrm{E}}(rs, i)

  2. The leader adopts component (get,rs,i,?)(get, rs, i, ?) at the start of round tt.

  3. upon entering round tt a follower adopts component (get)(get).

  4. if both agents are in round tt then

  5. (φ;get)+(φ∣L;get,rs,i,z)→(φ;get,rs,i,z)+(φ∣L;get,rs,i,z),(\varphi; get) + (\varphi|L; get, rs, i, z) \to(\varphi; get, rs, i, z) + (\varphi|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).(R|\varphi; get, rs, i, b) + (\varphi|L; get, rs, i, ?) \to(R|\varphi; get, rs, i, b) + (\varphi|L; get, rs, i, b).

  7. if the leader still holds (get,rs,i,?)(get, rs, i, ?) at the end of round tt then

  8. signal ANOMALY else return bb

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^{\mathrm{E}} and GETE^{\mathrm{E}} complete correctly whp in one round; otherwise, an ANOMALY is signalled.

Proof. At the beginning of the round of the PUTE(rd,i,b)^{\mathrm{E}}(rd, i, b) subroutine, the leader adopts the request component (put,rd,i,b)(put, rd, i, b). Each subsequent agent entering this round adopts the (put)(put) component. The leader broadcasts the request (put,rd,i,b)(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)O(\log n) time whp. The register agents then verify within O(log⁡n)O(\log n) time whp whether they hold the bit to be updated and, if so, set it to bb. If a register agent fails to verify whether it is responsible 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)^{\mathrm{E}}(rs,i) protocol begins with the leader adopting the request component (get,rs,i,?)(get,rs,i,?) at the beginning of round tt. Every follower entering round tt subsequently adopts the (get)(get) component. The leader broadcasts the request (get,rs,i,?)(get,rs,i,?) to all free agents through an epidemic in time O(log⁡n)O(\log n) whp. Consequently, the agent holding the ii-th bit of the register rsrs also receives this request during round tt whp by an interaction with a free agent. During the remainder of round tt, the component (get,rs,i,b)(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)O(\log n) whp. An ANOMALY is signalled if the leader does not receive the requested bit value bb by the end of round tt.

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 3w3w rounds; otherwise, an ANOMALY is signalled. The emulation requires O(ρ′w)O(\rho' 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 3w3w rounds. For an indirectly addressed register, the leader obtains its index using SET (Protocol 2). Since this index can identify any of the ρ′\rho' registers, its representation together with the current bit index requires O(ρ′w)O(\rho' 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)O(1) states. The agents in the working set also require O(ρ′w)O(\rho' w) states per round to propagate requests.

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 PP-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 XiX_i denote the subpopulation representing the ii-th input variable, namely, the set of agents in state iniin_i. Similarly, let YiY_i denote the subpopulation representing the ii-th output variable, namely, the set of agents in state outiout_i.

We first describe input conversion (Protocol 13). The protocol builds on the mechanism used for parity computation in [45], 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∣|X_i|, the protocol considers the weights in decreasing order, starting with Pw−2P_{w-2}. For each weight PℓP_\ell, it adds that weight to an auxiliary subpopulation ZZ and uses the MC+ majority protocol to determine whether ∣Z∣≤∣Xi∣|Z| \leq|X_i|. If the inequality holds, PℓP_\ell remains in ZZ and the ℓ\ell-th bit of ∣Xi∣|X_i| is set to 1. Otherwise, the weight is removed from ZZ and the bit is set to 0. Each bit is stored in the input array register riinr_i^{in} using PUTE^{\mathrm{E}}.

Weights are added to and removed from ZZ using ADDWEIGHT and REMOVEWEIGHT, each of which completes whp within one round. The protocol ADDWEIGHT(ℓ)(\ell) adds PℓP_\ell to ZZ 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ℓP_\ell receives this information upon entering the round and joins ZZ. If an agent skips this round, a clock anomaly is signalled. The protocol RemoveWeight(ℓ\ell) is analogous, except that agents in PℓP_{\ell} leave ZZ, and Z←∅Z \leftarrow\emptyset is shorthand for a similar subprotocol that removes all weights from ZZ in one round. Thus, in the absence of a clock anomaly, these operations are performed correctly.

Protocol 13 U2BconversionE(i)^{\mathrm{E}}(i)

Input: ii - input variable index

Result: Input array register riinr_i^{\mathrm{in}} stores ∣Xi∣\lvert X_i\rvert in binary whp

  1. function U2BconversionE(i)^{\mathrm{E}}(i)

  2. Z←∅Z \leftarrow\emptyset

  3. for ℓ←w−2\ell\leftarrow w-2 downto 00 do

  4. AddWeight(ℓ\ell) ▷ Add weight PℓP_{\ell} to ZZ

  5. Compare XiX_i and ZZ using Majority.

  6. if ∣Xi∣<∣Z∣\lvert X_i\rvert< \lvert Z\rvert then

  7. RemoveWeight(ℓ\ell) ▷ Remove weight PℓP_{\ell} from ZZ

  8. PUTE(riin,ℓ,0)^{\mathrm{E}}(r_i^{\mathrm{in}},\ell,0)

  9. else

  10. PUTE(riin,ℓ,1)^{\mathrm{E}}(r_i^{\mathrm{in}},\ell,1)

The conversion of a single input variable is summarised by the following lemma.

Lemma 6. The protocol U2BconversionE(i)^{\mathrm{E}}(i) correctly converts the ii-th input variable from unary to binary and stores its binary representation in riinr_i^{\mathrm{in}} whp within O(wlog⁡n)O(w\log n) rounds, using O(1)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 § 3 proves that the value bits represent A=∣Xi∣<2w−1A=\lvert X_i\rvert<2^{w-1} and the untouched sign bit is 0. Thus register riinr_i^{\mathrm{in}} stores the correct input value.

There are w−1w-1 iterations, each using one majority comparison in O(log⁡n)O(\log n) rounds and a constant number of single-round weight operations and bit writes. Including the initial clearing of ZZ gives O(wlog⁡n)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)O(1) per round. □\square

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 ii-th output register rioutr_i^{\mathrm{out}}, the protocol processes its bits one at a time. For bit ℓ\ell, the leader first retrieves its value using GETE(riout,ℓ)^{\mathrm{E}}(r_i^{\mathrm{out}},\ell). If the bit is 1, the single-round protocol Out(ℓ,i\ell,i) places 2ℓ2^{\ell} additional agents in state outiout_i.

Protocol 14 B2UconversionE(i)^{\mathrm{E}}(i)

Input: ii – output variable index

Result: A set YiY_i of agents in state outiout_i encodes the ii-th output value in unary

  1. function B2UconversionE(i)^{\mathrm{E}}(i)

  2. for ℓ←0\ell\leftarrow0 to w−2w-2 do

  3. in round 2ℓ2\ell: b←b \leftarrow GETE(riout,ℓ)^{\mathrm{E}}(r_i^{\mathrm{out}},\ell)

  4. if b=1b=1 then

  5. in round 2ℓ+12\ell+1: Out(ℓ,i\ell,i)

The protocol Out⁡(ℓ,i)\operatorname{Out}(\ell,i) operates as follows (Protocol 15). It uses weight PℓP_\ell of 2ℓ2^\ell agents. Each agent in PℓP_\ell adopts an additional component outiout_i and transfers it to a free agent while retaining its weight label. This adds 2ℓ2^\ell agents to the output subpopulation. After all bits of rioutr_i^{out} have been processed, the total number of agents in state outiout_i equals the value stored in that register.

Protocol 15 Out⁡(ℓ,i)\operatorname{Out}(\ell,i)

Input: ℓ\ell – weight index; ii – output variable index

Result: 2ℓ2^\ell additional agents enter state outiout_i

  1. function Out⁡(ℓ,i)\operatorname{Out}(\ell,i)

  2. upon entering round tt: ▷ The protocol executes in one round

  3. the leader adopts component (ℓ,i)(\ell,i);

  4. a free agent adopts component (ℓ,i)(\ell,i);

  5. an agent in PℓP_\ell adopts component outiout_i, giving (pℓ,outi)(p_\ell,out_i).

  6. during round tt:

  7. (pℓ,outi)+φ→pℓ+outi(p_\ell,out_i)+\varphi\to p_\ell+out_i. ▷ φ\varphi denotes a free agent

  8. upon entering round t+1t+1:

  9. if an agent still has (pℓ,outi)(p_\ell,out_i) then signal Anomaly

Lemma 7. The protocol Out⁡(ℓ,i)\operatorname{Out}(\ell,i) correctly creates a subpopulation of 2ℓ2^\ell agents in state outiout_i whp in one round, otherwise an Anomaly is signalled.

Proof. Let tt be the round in which Out⁡(ℓ,i)\operatorname{Out}(\ell,i) is executed. Each agent in PℓP_\ell adopts an additional component outiout_i upon entering round tt. For the protocol to succeed, each such agent must interact with a free agent during this round and transfer outiout_i to that agent. Throughout the protocol, at least (1−1c)n(1-\frac{1}{c})n agents remain free and form the working set. Thus, for any agent in PℓP_\ell with outiout_i, the probability that a given interaction is initiated by this agent with a free agent as responder is at least 1−1cn\frac{1-\frac{1}{c}}{n}. The phase clock ensures whp that all agents remain in round tt for at least cnlog⁡ncn\log n interactions. The probability that a particular agent retains outiout_i while this common round lasts for at least cnlog⁡ncn\log n interactions is at most

(1−1−1cn)cnlog⁡n≤e−(1−1c)clog⁡n≤n−(1−1c)c.\left(1-\frac{1-\frac{1}{c}}{n}\right)^{cn\log n}\le e^{-(1-\frac{1}{c})c\log n}\le n^{-(1-\frac{1}{c})c}.

A union bound over the agents in PℓP_\ell gives a failure probability of at most ∣Pℓ∣n−(1−1c)c≤n−η|P_\ell|n^{-(1-\frac{1}{c})c}\le n^{-\eta}, for any fixed η>0\eta>0, provided that cc is sufficiently large. Failure therefore requires either a common round shorter than cnlog⁡ncn\log n interactions or an unsuccessful transfer within its first cnlog⁡ncn\log n interactions. Adding the phase clock’s failure probability to this bound yields the whp guarantee.

We conclude with a lemma on the binary-to-unary conversion of one output variable.

Lemma 8. The protocol B2Uconversion⁡e(i)\operatorname{B2Uconversion}^{e}(i) correctly converts the ii-th output value stored in rioutr_i^{out} from binary to unary whp in 2w2w rounds, using O(1)O(1) additional states per round; otherwise, an Anomaly is signalled.

Proof. Write the admissible output value as B=∑ℓ=0w−2bℓ2ℓ<2w−1B=\sum_{\ell=0}^{w-2}b_\ell2^\ell<2^{w-1}. Initially, no agent belongs to YiY_i. If the component operations execute correctly, then after processing bits 0,…,ℓ0,\ldots,\ell, the set YiY_i contains exactly ∑j=0ℓbj2j\sum_{j=0}^{\ell}b_j2^j agents: the bit retrieval returns bℓb_\ell, and Out⁡(ℓ,i)\operatorname{Out}(\ell,i) adds exactly 2ℓ2^\ell agents 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 BB, including Yi=∅Y_i = \emptyset when B=0B = 0.

Each bit uses one retrieval round and at most one output round, giving at most 2(w−1)<2w2(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)O(1) additional states per round are needed. □

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\mathcal{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)\Theta(w) rounds whp by Theorem 6. Register initialisation occupies one long round of O(ρ′w)O(\rho' w) time whp by Lemma 2. The system of w−1w-1 weights is then created whp in one round by Lemma 3. Next, each of the TRT_R input values is converted from unary to binary and stored in the input array. By Lemma 6, each conversion takes O(wlog⁡n)=O(w2)O(w \log n) = O(w^2) rounds, giving O(TRw2)O(T_R w^2) rounds in total. Emulating the modified P\mathcal{P}-program takes O(Tw)O(Tw) rounds by Lemma 5. Finally, converting the TPT_P output registers from binary to unary takes O(TPw)O(T_Pw) 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(TRw+TRAM+TP)).\tau= O\left(w\left(T_Rw + T_{RAM} + T_P\right)\right).

We next establish the state complexity. Leader election uses O(w2)O(w^2) states by Theorem 6. After register initialisation, the phase-clock component uses only O(1)O(1) states per round by Theorem 5. Weight creation uses O(w2)O(w^2) states by Lemma 3. During subsequent computation, weight agents require O(wτ)O(w\tau) states to record their weight labels and the current round. Similarly, input agents require O(TRτ)O(T_R\tau) states and output agents require O(TPτ)O(T_P\tau) states. Register agents require O(ρ′wτ)O(\rho' w\tau) 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τ)O(\rho' w\tau) states. For all agents, it suffices to use only O(1)O(1) states per round for the remaining subprotocol-specific components.

Since TR,TP≤ρ′T_R, T_P \le\rho', the register-agent state bound dominates these contributions. Thus, the total number of states is

O(ρ′wτ)=O(ρ′w2(TRw+TRAM+TP)).O(\rho' w\tau) = O\left(\rho' w^2\left(T_Rw + T_{RAM} + T_P\right)\right).

□

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))\Theta(\min(\rho', w)).

Theorem 4. The MC+ simulation of Theorem 3 can be implemented in the same number of rounds and with O((ρ′+w)τ)O((\rho' + w)\tau) states.

Proof. In the proof of Theorem 3, the state complexity O(ρ′wτ)O(\rho' w\tau) 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(ρ′)O(\rho') states per round. We then show that the register agents, whose identities alone require Θ(ρ′w)\Theta(\rho'w) states, need to count only O(τ/w)O(\tau/w) rounds.

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 3w3w calls to atomic subroutines, each in separate round. If it requires fewer, we pad its emulation with idle rounds so that it occupies exactly 3w3w rounds. In U2BCONVERSIONᴱ, 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 ZZ 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 ww and TRT_R. We also pad B2UCONVERSIONᴱ, so that the round 2ℓ+12\ell+ 1 is idle if bit ℓ\ell is 0, and the conversion of each output variable, which takes 2(w−1)<3w2(w - 1) < 3w rounds, is padded to 3w3w rounds. We call each of these fixed-length segments a pass: an instruction slot or the conversion of one output variable, each of 3w3w rounds, or one iteration of an input conversion, of Θ(w)\Theta(w) rounds. Execution is padded to all T∗T^* instruction slots before output conversion begins. Every pass has at least ww 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 PUTᴱ(rd,i,brd,i,b) or GETᴱ(rs,irs,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 PP-program require only O(1)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 ρ′\rho' registers, its representation requires O(ρ′)O(\rho') states per round for the leader, and the agents in the working set also require O(ρ′)O(\rho') 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(ρ′)O(T_P) = O(\rho') states. Hence the leader and the working set agents require only O(ρ′τ)O(\rho'\tau) states.

Register agents. Register agents require a different argument: their identities (r,i,b)(r,i,b) already account for Θ(ρ′w)\Theta(\rho'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)(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)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 ii of any register may be accessed are determined by ii and the instruction, or, in a conversion, by ii and the coarse-grained round. There are at most three of them, denoted t0<t1<t2t_0 < t_1 < t_2, and they may be consecutive (e.g. for ADD(r,r,rr,r,r)). A register agent therefore also keeps a status from the set {early0,active0,between0,active1,between1,active2,late}\{\textit{early}_0,\textit{active}_0,\textit{between}_0,\textit{active}_1,\textit{between}_1,\textit{active}_2,\textit{late}\}. It indicates whether the current round of the pass precedes t0t_0, equals tjt_j, lies strictly between tjt_j and tj+1t_{j+1}, or follows the last of these rounds. In addition, as in PUTᴱ, the agent adopts the component put when it enters an active round in which a PUTᴱ is executed, and clears it once it has processed the request. Both components require O(1)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))nn - \rho'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 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 pp denote the coarse-grained round of the agent, II the instruction of the current pass, and ss its status; from ii and II, the agent knows the positions t0<t1<t2t_0 < t_1 < t_2 of its active rounds within the pass. When it meets a non-register agent in fine round t′t' with instruction or pass tag I′I', the transition function determines the corresponding coarse-grained round p′p' and status s′s' from tt, I′I', and ii. 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)(p,I,s) by a later (p′,I′,s′)(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′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′=pp'=p and the next active round of the agent in pass pp precedes t′t', or p′=p+1p'=p+1 and the agent has an active round in pass pp after its current status or in pass p′p' before t′t'.

  1. Clock anomaly: the partner’s coarse-grained round differs from pp 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 pp, II, ii, and ss.

  1. Protocol anomaly: the agent leaves an active status of a PUTE\mathrm{PUT}^{\mathrm{E}} round while still holding the component (put)(put).

In active rounds in which GETE\mathrm{GET}^{\mathrm{E}} is executed, the agent adopts the component (get)(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)(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)\Omega(\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 ww rounds, there are O(τ/w)O(\tau/w) coarse-grained rounds. A register agent thus stores its register index, bit index, and bit value, its coarse-grained round, and O(1)O(1) further states for the instruction, the status, and the components (put)(put) and (get)(get). Hence the register agents use O(ρ′⋅τ/w)=O(ρ′τ)O(\rho' \cdot\tau/w)=O(\rho'\tau) states instead of O(ρ′τ)O(\rho'\tau). The remaining bounds from the proof of Theorem 3 are unchanged: leader election and weight creation use O(w2)O(w^2) states, weight agents use O(wτ)O(w\tau) states, and input and output agents use O((TR+TP)τ)=O(ρ′τ)O((T_R+T_P)\tau)=O(\rho'\tau) states. Hence the total number of states is O((ρ′+w)τ)O((\rho'+w)\tau). The backup contributes O(ρ′w2)O(\rho'w^2) states, which is absorbed because ρ′=O(T)\rho'=O(T) and τ=Ω(wT)\tau=\Omega(wT) for the padded schedule. Thus the same refinement applies to the combined stable and silent simulation.

Backup Simulation

Overview

We now present a novel stable and silent backup protocol simulating general P\mathcal{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 instruction reductions (Subsection 2.2), without a clock or further epidemics; full details and proofs follow in this section.

Theorem 8. For every P\mathcal{P}-program, the backup simulation population protocol silently stabilises in expected time O(n2w)O(n^{2}w), and uses O(ρ′wlog⁡n)=O(ρ′w2)O(\rho'^{w}\log n)=O(\rho'^{w^{2}}) 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 [7], which we augment with a rank carried by every agent; in a state (X,i)(X,i), X∈{L,F}X\in\{L,F\} marks a leader or a non-input follower and ii 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).(L,i)+(L\mathbin{|}F,j)\to(L,i)+(F,i)\quad\text{if }i>j,\qquad(L,i)+(L,i)\to(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 [54] of its tree of won duels, so it is at most 1+⌊log⁡n⌋1+\lfloor\log n\rfloor, 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 nn, 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)O(\log n)=O(w) in the number of states.

(2) Direct access. In PUTB\mathrm{PUT}^{\mathrm B} and GETB\mathrm{GET}^{\mathrm B} (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)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)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 viv_i permanently; the leader increments riinr_i^{\mathrm{in}} 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 dwdw; 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−ηn2^{-dw}\le n^{-\eta} (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−ηn^{-\eta}, so the expected number of further retries is o(1)o(1). Any attempt already in progress has the same asymptotic expected cost. The emulation takes O(Tnw)=O(npoly⁡(w))O(Tnw)=O(n\operatorname{poly}(w)) expected time, so the bound O(n2w)O(n^{2}w) is dominated by the conversions of the O((TR+TP)2w−1)=O(n)O((T_R+T_P)2^{w-1})=O(n) unary input and output units, each requiring an INC or DEC of O(nw)O(nw) expected time.

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\mathcal{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(n2w)O(n^{2}w), using O(ρ′wlog⁡n)=O(ρ′w2)O(\rho' w \log n) = O(\rho' w^{2}) 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)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 AA usually denotes a leader and agent BB its interaction partner. The state of an agent AA is a tuple of components, one of which is always the rank A.rankA.\mathit{rank}. We refer to the remaining components collectively as the substate A.substateA.\mathit{substate}. When a subprotocol has an explicit argument AA, this denotes the leader executing it. The component rank takes values in {0,1,…,h}\{0,1,\ldots,h\}, where h=1+⌊log⁡n⌋=O(w)h = 1 + \lfloor\log n\rfloor= O(w), while substate specifies the role of the agent and its role-specific data, as listed in Table 5.

RoleValue of substateDescription
leader(L,aux)(L, aux)auxaux: finite control, ipip, one register index, one bit index, input/output index
register(R,r,i,b)(R,r,i,b)register index, bit index, bit value
helper(H,j)(H,j)counter of interactions with the leader
inputiniin_iindex of the input variable
outputoutiout_iindex of the output variable
freeφ\varphino assigned role

Table 5. Values of the component substate.

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.

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 LL 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 FF; 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 FF. Consequently, only one leader reaches the highest rank that is at most 1+⌊log⁡n⌋1 + \lfloor\log n\rfloor. 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 \mid F, j) \to(L, i) + (F, i) \quad\text{if } i > j,
(L,i)+(L,i)→(L,i+1)+(F,i+1).(L, i) + (L, i) \to(L, i + 1) + (F, i + 1).

Here FF 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)O(n). Only this leader reaches the highest rank in the population, which is at most 1+⌊log⁡n⌋1 + \lfloor\log n\rfloor.

Proof. The time complexity of leader election by pairwise duels has been studied in [7]. The rank of a leader corresponds to the Strahler number [54] of the tree of duels it has won, or equivalently to the register number [38, 37]. In particular, a leader of rank rr has defeated, directly or indirectly, at least 2r−12^{r-1} initial leaders, so 2r−1≤n2^{r-1} \le 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)O(n) expected election bound applies after the last such entry. □\square

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 ρ\rho 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.

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 Simulationᵇ. The final checking state persists; priority rank rules remain active throughout.

Input: a modified P\mathcal{P}-program, a leader AA

Result: stable simulation if AA is the unique leader

  1. function Simulationᵇ(AA)

  2. RegInit(ρ′,w,A\rho', w, A)

  3. U2B: U2Bconversionᵇ(AA)

  4. ip←0ip \leftarrow0

  5. while ip≠ENDip \ne\mathrm{END} do

  6. AA emulates the RAM instruction indicated by ipip.

  7. Update ipip.

  8. B2Uconversionᵇ(AA)

  9. FINISHED: retain the output and wait for an input agent BB with B.rank<A.rankB.rank < A.rank.

  10. EraseOutput(AA); 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 AA are assumed to have rank A.rankA.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\mathcal{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\mathcal{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\mathcal{P}-program performs the same number TPT_P of prints for any input, there is also no need to reset the output array: it is overwritten when the emulation is restarted.

Backup Emulation of RAM Instructions

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

Protocol 17 PUTB(rd,i,b)^{\mathrm{B}}(rd, i, b)

Input: rdrd - pointer to a register, ii - bit index, b∈{0,1}b \in\{0,1\}, a leader AA

Result: The ii-th bit of register rdrd is set to bb

  1. function PUTB(rd,i,b,A)^{\mathrm{B}}(rd, i, b, A)

  2. repeat

  3. The leader interacts with an agent BB.

  4. until B.rank=A.rankB.rank = A.rank and B.substate=(R,rd,i,⋆)B.substate = (R, rd, i, \star)

  5. B.substate←(R,rd,i,b)B.substate \leftarrow(R, rd, i, b)

The GETB(rs,i)^{\mathrm{B}}(rs, i) subroutine is analogous. The leader interacts with agents until it encounters the agent holding the ii-th bit of register rsrs, at which point it learns the value of that bit.

Protocol 18 GETB(rs,i)^{\mathrm{B}}(rs, i)

Input: rsrs - pointer to a register, ii - bit index, a leader AA

Result: The leader learns the ii-th bit of register rsrs

  1. function GETB(rs,i,A)^{\mathrm{B}}(rs, i, A)

  2. repeat

  3. The leader interacts with an agent BB.

  4. until B.rank=A.rankB.rank = A.rank and B.substate=(R,rs,i,b)B.substate = (R, rs, i, b)

  5. return bb

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)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^{\mathrm{B}} and PUTB^{\mathrm{B}} complete in expected time O(n)O(n). Consequently, every RAM instruction can be stably emulated by the unique leader in expected time O(nw)O(nw).

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 riinr_i^{in} and rioutr_i^{out} at fixed positions, we assume that the leader can convert an index ii, or a state iniin_i or outiout_i, to the address of riinr_i^{in} or rioutr_i^{out}, 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 PP-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)\mathrm{CONVERSION}^{\mathrm{B}}(A) (Protocol 19), executed by the leader AA, which performs this conversion.

First, the leader designates a free agent BB as a helper by setting B.substate←(H,0)B.substate \leftarrow(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 dwdw, for a constant d>0d > 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 BB with B.substate=iniB.substate = in_i and a lower rank, the leader executes line 7: it marks BB as read by assigning it its own rank and increments riinr_i^{in} 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+HL+H interactions and thus determines when the conversion ends. By choosing a sufficiently large constant dd, the leader AA encounters every input agent whp before the helper’s counter reaches dwdw.

Protocol 19 U2Bconversionᵇ(AA)

Input: AA - a leader

Result: the cumulative input counts include every input agent whp

  1. function U2Bconversionᵇ(AA)

  2. In the first interaction of AA with a free agent BB:

  3. B.substate←(H,0)B.\mathit{substate} \leftarrow(H,0) ▷ Helper designation.

  4. START:

  5. During subsequent interactions A+BA+B:

  6. if B.substate=iniB.\mathit{substate}=in_i and B.rank<A.rankB.\mathit{rank}<A.\mathit{rank} then

  7. B.rank←A.rankB.\mathit{rank} \leftarrow A.\mathit{rank}, INC⁡(riin)\operatorname{INC}(r_i^{in}), goto START;

  8. if B.substate=(H,j)B.\mathit{substate}=(H,j) and B.rank=A.rankB.\mathit{rank}=A.\mathit{rank} then

  9. if j+1<dwj+1<dw then B.substate←(H,j+1)B.\mathit{substate} \leftarrow(H,j+1), goto START;

  10. else B.substate←φB.\mathit{substate} \leftarrow\varphi; return

The following lemma characterises the unary-to-binary input conversion protocol of the backup.

Lemma 10. Protocol U2Bconversionᵇ(AA), when executed by the unique leader of the final rank, returns in expected time O((N+1)nw)=O(n2w)O((N+1)nw)=O(n^2w), where NN 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 N2−dw≤n2−dwN2^{-dw}\le 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)O(1).

Fix an input agent BB not yet counted and consider only interactions of the leader in the waiting state. Until BB is counted, the probabilities of meeting BB and the helper are equal. Pausing the scan during register increments does not change this symmetry. Hence the probability of meeting the helper dwdw times before meeting BB is 2−dw2^{-dw}. A union bound over the NN uncounted input agents gives N2−dwN2^{-dw}. This is at most n−ηn^{-\eta} for any prescribed constant η>0\eta>0 when dd is sufficiently large, since w=Θ(log⁡n)w=\Theta(\log n).

The expected total time spent waiting for the dwdw helper meetings is O(nw)O(nw). At most NN input-register increments are performed, each in expected time O(nw)O(nw) by Fact 4. The helper counter is paused during these increments, giving total expected time O((N+1)nw)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\mathcal{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 B2Uconversionᵇ(AA) (see Protocol 20), executed by the leader AA.

The leader executes a loop from i=1i = 1 to TPT_P. Its goal in iteration ii is to create a subpopulation of [riout][r_i^{out}] agents in substate outiout_i, which represents the ii-th output value in unary. To this end, the leader copies [riout][r_i^{out}] into a temporary register rcrc using the direct copy COPY(riout,rcr_i^{out}, rc). It repeatedly decrements rcrc and assigns the substate outiout_i to a free agent whenever the resulting value is non-negative, stopping when [rc]=−1[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(AA) 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 φ\varphi into agents in substate outiout_i, turns agents in substate outiout_i into agents in substate φ\varphi.

Protocol 20 B2Uconversionᵇ(AA)

Input: AA - a leader

Result: all output stored in binary in output array registers stably converted to unary

  1. function B2Uconversionᵇ(AA)

  2. for i←1i \leftarrow1 to TPT_P do

  3. COPY(riout,rcr_i^{out}, rc)

  4. goto CONVERT:

  5. ASSIGN:

  6. In the first interaction of AA with a free agent BB:

  7. B.substate←outiB.substate \leftarrow out_i

  8. CONVERT:

  9. DEC(rcrc), JGE(rcrc, ASSIGN:)

The behaviour of the output-creating and output-erasing protocols is characterised by the following lemma.

Lemma 11. Protocol B2Uconversionᵇ(AA), 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(TP2wnw)=O(n2w)O(T_P 2^w nw) = O(n^2w). Moreover, if necessary, the unary output representation can be stably erased by protocol EraseOutput(AA) in the same expected time.

Proof. By Fact 4, each RAM instruction used in B2Uconversionᵇ(AA) executes in expected time O(nw)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 AA can stably assign any output state to a previously free agent in expected time O(1)O(1) (lines 6–7 of Protocol 20). The binary-to-unary conversion proceeds one output variable at a time. To convert the ii-th output value, the leader emulates one instruction COPY, followed by at most 2w−12^{w-1} pairs of DEC and JGE instructions and exactly [riout][r_i^{out}] assignments of an output state to a free agent. Since 0≤[riout]<2w−10 \le[r_i^{out}] < 2^{w-1}, the signed counter runs down to −1-1 without overflow. Each such iteration takes expected time O(nw)O(nw). Hence, converting a single output variable takes expected time O(2w⋅nw)O(2^w \cdot nw). Consequently, all TPT_P output variables are stably converted from binary to unary in total expected time O(TP2wnw)=O(n2w)O(T_P 2^w nw) = O(n^2w).

The analysis of protocol EraseOutput(AA) is analogous to the one above. The only difference is that releasing an output agent takes expected time up to O(n)O(n). However, this does not affect the overall expected time bound.

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\mathcal{P}-program, the backup simulation population protocol silently stabilises in expected time O(n2w)O(n^{2}w), and uses O(ρ′wlog⁡n)=O(ρ′w2)O(\rho' w \log n)=O(\rho' w^{2}) states.

Proof. After the O(log⁡n)O(\log n) expected handover, Lemma 9 gives a unique leader within further expected time O(n)O(n). Only this leader ever attains its final rank KK, so its rank-KK registers are uncontaminated. By the coupon collector bound, direct interactions reclaim all lower-ranked non-input agents in expected time O(nlog⁡n)O(n\log n). Reclamation overlaps simulation; no separate synchronisation is needed.

At rank KK, 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 TPT_P outputs. Output conversion completes with probability 11, 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)O(\rho'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(n2w)O(n^{2}w) for input conversion, O(Tnw)O(Tnw) for each tentative execution, and O(n2w)O(n^{2}w) each for output creation and erasure. Finding a missed input in FINISHED costs expected time O(n)O(n). Since T=poly⁡(w)T=\operatorname{poly}(w) and n≥C2wn\ge C2^{w}, these costs, including detection and erasure after failure, are bounded conditionally on every valid attempt-start history by

B=O(n2w).B=O(n^{2}w).

The same bound covers a legitimate subprotocol already in progress when leader election finishes. Charge O(B)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−η,\delta\le n2^{-dw}\le n^{-\eta},

for sufficiently large dd. Thus a kk-th fresh attempt is needed with probability at most δk−1\delta^{k-1}. Summing the conditional cost bounds at attempt starts gives expected remaining time at most

∑k≥1δk−1B=B1−δ=O(n2w).\sum_{k\ge1}\delta^{k-1}B=\frac{B}{1-\delta}=O(n^{2}w).

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 11. Including election, reclamation, allocation, and the initial residual execution preserves the expected bound O(n2w)O(n^{2}w).

There are O(log⁡n)=O(w)O(\log n)=O(w) ranks. Per rank, register agents use O(ρ′w)O(\rho'w) states for a register index, bit index, and bit value; input/output agents use O(TR+TP)O(T_R+T_P); the helper uses O(w)O(w); and free agents use O(1)O(1). The leader stores ipip and finite control in O(1)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 ρ′\rho'. Thus the leader uses O(ρ′w)O(\rho'w) states per rank, and the disjoint role-specific state spaces total O(ρ′wlog⁡n)O(\rho'w\log n) states.

Remark. Correctness of the backup does not require advance knowledge of TRAMT_{\mathrm{RAM}}. 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\mathcal{P}-programs.

Conclusions

We have shown that every P\mathcal{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(TRw)O(T_Rw) and need not equal ww. 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(rdr_d) 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)p(w), each fresh trial truncated after 2p(w)2p(w) steps succeeds with probability at least 1/21/2; cwcw trials fail with probability at most 2−cw=n−Ω(1)2^{-cw}=n^{-\Omega(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. [31] proposed as a research direction succinct protocols for quantifier-free Presburger formulas, with poly⁡(m)\operatorname{poly}(m) states for a formula of size mm, that converge in poly⁡log⁡n\operatorname{poly}\log n time. We propose an analogous direction for leaderless protocols that are additionally required to be stable. With poly⁡(m)\operatorname{poly}(m) states independent of nn, such protocols cannot be fast [15], and already majority, a formula of constant size, requires Ω(log⁡n)\Omega(\log n) states for time O(n1−c)O(n^{1-c}) under the assumptions of [4]. We therefore call a fast leaderless stable protocol succinct if it uses poly⁡(m)⋅poly⁡log⁡n\operatorname{poly}(m)\cdot\operatorname{poly}\log n states. Under this notion, our result gives succinct protocols that moreover stabilise silently: every such formula is evaluated by a P\mathcal{P}-program with poly⁡(m)\operatorname{poly}(m) instructions and registers, so for all sufficiently large nn, Theorem 1 yields a protocol with poly⁡(m)⋅poly⁡log⁡n\operatorname{poly}(m)\cdot\operatorname{poly}\log n states and poly⁡log⁡n\operatorname{poly}\log n stabilisation time. Reducing the polylogarithmic factor, ideally to poly⁡(m)⋅O(log⁡n)\operatorname{poly}(m)\cdot 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 [36], 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 § 1.1, a gap remains between poly⁡(w)\operatorname{poly}(w)-time source computations and reverse simulation in poly⁡(w)\operatorname{poly}(w) space and expected 2O(w)2^{O(w)} time. For predicates, the cited uniformity and constructibility assumptions also yield an NSPACE(polylog⁡n)(\operatorname{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 ww while preserving arithmetic semantics and resource guarantees; stable size estimation [18] 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 [40], and spatial population protocols for localisation using distance or vector queries [44]. A useful goal is to integrate such interfaces with our simulation through operations for reading records, comparing keys, and 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 § 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.

References

  1. [1]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.1007/978-3-662-47666-6_38.
  2. [2]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.
  3. [3]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.
  4. [4]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.9781611975031.144.
  5. [5]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.OPODIS.2021.14.
  6. [6]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.
  7. [7]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.
  8. [8]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/1146381.1146425.
  9. [9]Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279–304, 2007. doi: 10.1007/s00446-007-0040-2.
  10. [10]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/papers/approximate-majority-abstract.html.
  11. [11]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/s00446-008-0067-z.
  12. [12]James Aspnes. Clocked population protocols. Journal of Computer and System Sciences, 121:34–48, 2021. doi: 10.1016/j.jcss.2021.05.001.DOI
  13. [13]James Aspnes. Stochastic well-structured transition systems, 2025. URL https://arxiv.org/abs/2512.20939. arXiv:2512.20939.
  14. [14]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-540-89707-1_5. URL https://www.cs.yale.edu/homes/aspnes/papers/introduction-to-population-protocols-abstract.html.DOI
  15. [15]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.DOI
  16. [17]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.DOI
  17. [18]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.DOI
  18. [19]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.DOI
  19. [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.
  20. [22]Andreas Bilke, Colin Cooper, Robert Elsässer, and Tomasz Radzik. Brief announcement: Population protocols for leader election and exact majority with O(log² n) states and O(log² 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/3087801.3087858.DOI
  21. [23]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.DOI
  22. [24]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.DOI
  23. [25]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.DOI
  24. [26]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.
  25. [27]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.DOI
  26. [28]Ho-Lin Chen, David Doty, and David Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 13(4):517–534, 2014. doi: 10.1007/s11047-013-9393-6.DOI
  27. [29]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-0000(73)80029-7.DOI
  28. [30]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.DOI
  29. [31]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.DOI
  30. [33]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.DOI
  31. [34]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.DOI
  32. [35]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-48653-5_40. URL https://doi.org/10.1007/978-3-662-48653-5_40.
  33. [36]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.2021.00104.DOI
  34. [37]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.DOI
  35. [38]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.DOI
  36. [39]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.DOI
  37. [40]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.
  38. [41]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.DOI
  39. [43]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.DOI
  40. [44]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.DOI
  41. [45]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.4230/LIPIcs.DISC.2026.17.arxiv.org/abs/2512.20163
  42. [46]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-642-02930-1_40.
  43. [47]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.DOI
  44. [48]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/abs/1802.06872. Full version: arXiv:1802.06872.
  45. [49]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.liverpool.ac.uk/3003386/.DOI
  46. [50]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/nca2015-proceedings.pdf.DOI
  47. [51]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/NCA.2016.7778621.DOI
  48. [52]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.DOI
  49. [53]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.DOI
  50. [54]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-7606(1952)63[1117:HAAOET]2.0.CO;2.DOI
  51. [55]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.DOI

Paper details

vlnc:W_twhaveub
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents