Distributed Population Protocols: Naturally! David de Frutos Escrig Dpto. Sistemas Informáticos y Computación, Facultad de Ciencias Matemáticas Universidad Complutense de Madrid, Madrid, Spain defrutos@sip.ucm.es Abstract. Classical population protocols manage a fix size population of agents that are created by the input population: one agent exactly per unit of the input. As a consequence, complex protocols that have to perform several independent tasks find here a clear bottleneck that drastically reduces the parallelism in the execution of those tasks. To solve this problem, I propose to manage distributed population protocols, that simply generalize the classical ones by generating a (fix, finite) set of agents per each unit of the input. A surprising fact is that these protocols are not really new, if instead of considering only the classical protocols with an input alphabet we consider the alternative simpler one that states as input mechanism a given subset of the set of states. Distributed population protocols are not only interesting because they allow more parallel and faster executions, but specially because the distribution of both code and data will allow much simpler protocols, inspired by the distribution of both places and transitions in Petri nets. 1 Introduction Population protocols were introduced by Angluin et al. [4, 5] as a new proposal for distributed computation by very limited agents, whose computational power is based on the interactions between them. These agents are supposed to be moving in an uncontrolled way in a common arena, so that from time to time they meet one another. In their meetings they communicate each other their state, after which they can change it according to the received information. The initial formalization is extremely simple, reflecting all the ingredients in the description above, and producing a formalism very easy to use. But at the same time, their creators foresaw that the main idea could be used in more liberal ways, and so they also introduced a general framework allowing many generalizations. Indeed, several of them have been considered interesting by several groups of researchers during the last years, and many definitions of new classes of population protocols have appeared, and their computational power and characteristics have been studied in detail. You can find in [18] a nice very compact informative essay. Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). 214 D. de Frutos Escrig Probably, the first (intended) limitation of the original model was the con- servation of the number of agents working in the protocol. This is justified by a possible hardware implementation of those agents as nanocomputers. Definitely, this restriction, together with the fix limitation of memory of each agent, is the main reason of the quite limited computational power of the classical popula- tion protocols. Their creators characterized it as that of semilinear predicates, or equivalently those definable in Presburger arithmetic [6, 8]. The input compo- nent at the definition establishes a (finite) input alphabet, and the multisets on it are the concrete inputs. Besides, each unit of this input creates one agent (in a certain initial state) and thus the number of agents all along the execution of the protocol coincides with the size of the input. Another main characteristic of the classical population protocols is that the protocol itself (its code) is uniform and does not know in advance the set of agents that is working on it. This code is just a list of transitions in which one agent can participate when meeting with another; the same list for all the agents. Finally, the agents are assumed to be (and they are indeed, by definition) only differentiable by their state, so that there are no unique identifiers for them from scratch. But fairness of the executions is the crucial assumption in order to get their computational power. Fairness filters out the executions that are considered to be feasible, and then the protocols can be designed in a way that all the fair executions from the same input lead all the agents working at it to the same output, that is the output computed for that input. Another justification of fairness arrives when we consider the uniform prob- abilistic selection of the pair of agents that communicate at each step of an execution. It is well known that in bounded non-deterministic models, where the probabilities of the next step to be executed are fixed, fairness is equivalent to probability 1 computation, so that we can neglect the consideration of unfair executions since its full set has probability 0 . The introduction of probabilities also allows the computation of the expected time for stabilization of a protocol, which provides a natural measure of the efficiency of population protocols. By ruling out the imposed restrictions much more powerful classes of pro- tocols have been introduced. Doty et al. have developed a large collection of papers where the dynamic creation of agents makes possible the delay of cer- tain transitions, simply because a few pairs of agents can participate in them. Under these assumptions fairness and probability 1 are not equivalent anymore, and this makes the probabilistic model much more powerful, even exceeding the power of Turing machines (of course in a non-implementable way) [13]. And by extending the memory of agents, which will be related with the size of the input, Alistarh et al. [1] have provided protocols that compute more predicates, study- ing a trade-off between used memory and needed time for stabilization, similar to the existing one in classical computation. Finally, by removing the (total) sym- metry, we can get either faster protocols or again a bigger computation power. Protocols with leaders [7, 15] and agents with unique identification [17] work in those directions. More about recent extensions of the basic model can be found in [2]. Distributed Population Protocols: Naturally! 215 In this paper I present a new methodology for the design of protocols in the basic class, that advocates for (even) more distributed protocols. It is obtained by removing the one to one correspondence between the units of the input and the agents participating in the computation of the protocol. Instead, the input function will introduce at the initial configuration a certain collection of agents at some preset states. After that they evolve following the rules in the classical definition. I want to stress the fact that I am not introducing another extension of the basic model, but just a new methodology to define protocols that remain at that basic model. What I am claiming is that the use of (mainly only) classical protocols is constraining the designs of people developing basic protocols, so that they are forced to use quite complicated techniques to construct their protocols (see for instance [9]). In particular, I will show that the use of my distributed population protocols have led me to obtain protocols where reverse transitions, which reverse the effect of others, are totally removed, or their role is quite limited. These reverse transitions seemed unavoidable to maintain the state space of the protocols small, but we will see that the distribution of tasks will facilitate alternative (and very natural) solutions that do not need (or reduce a lot) their use. Reverse transitions will always delay the stabilization of the protocols, and in most of the cases they will do it in an absolutely unacceptable (overexponential) way. Thus their removal is a clear improvement. The rest of the paper is organized as follows. In the next section the ba- sic notation is presented and the definitions of (classical) population protocols recalled, explaining how I ‘derived’ the one for distributed protocols, starting from them. In Section 3, I give the formal definition of distributed population protocol, and the protocol P∧ for the computation of φ = φ1 ∧ φ2 is introduced as a representative example. Next, in Section 4, I present a different application of distributed protocols, based in the 2-base representation of numbers, instead of using the unary representation, as usually done when developing population protocols. This representation is also used in Section 5, where I present a suc- cinct protocol for the computation of threshold predicates that appear at the ‘basis’ generating the Presburger predicates. I conclude collecting the main goals reached at the paper, and announcing several continuations. Some simple proofs have been omitted, and others sketched. 2 Preliminaries Throughout the paper I use the standard mathematical notation. In particular, Z denotes the set of integers, and N the set of natural numbers (i.e., non-negative integers). I use a..b with a ≤ b to denote an interval in any of those sets, and AB for the set of (total) functions from B to A, so that A1..k are the vectors with k elements in A. Also, (finite) multisets over Pa finite set X are the elements of NX . The size of α ∈ NX is defined P as |α| P = x∈X α(x). When the elements of X are summable, we define q∈α q = x∈X α(x) × x . We say that x ∈ X is in a multiset α, and write x ∈ α by abuse of notation, if α(x) > 0. Multisets 216 D. de Frutos Escrig will be represented either by extension, in the form {{x1 , . . . , xk }} or in a linear way k1 · x1 , . . . , kl · xl , where the elements xi will be different one another, and ki > 0 . α + β denotes multiset sum, which means (α + β)(x) = α(x) + β(x) , for x ∈ X. Besides, α ≤ β means α(x) ≤ β(x) for all x ∈ X, and when β ≤ α, α − β denotes the multiset difference, (α − β)(x) = α(x) − β(x) . Finally, for k ∈ N and α ∈ NX , we define the product k×α as the multiset given by (k×α)(x) = k α(x), for each x ∈ X. The empty multiset is denoted by 0. From classical population protocols to distributed protocols. A popu- lation protocol (as in [5]) is a tuple P = (Q, I, T, O), where I : X → Q , for some input alphabet X, is the input initialization function, T ⊆ Q2 × Q2 , and O : Q → Y is the output function , for some output alphabet Y . Transitions will be usually presented in the form q1 , q2 → q10 , q20 . We assume that T is total: for all (q1 , q2 ) ∈ Q2 there exists (q10 , q20 ) with q1 , q2 → q10 , q20 . Whenever this is not originally the case, the set of transitions is completed with the necessary iden- tity transitions q1 , q2 → q1 , q2 , that are said to be silent. In this paper we only consider protocols that compute a predicate, which corresponds to Y = {0, 1} . An alternative slightly different formalization used in many papers, even by their original creators (e.g. in [6],) removes the input alphabet X, taking directly I ⊆ Q . This means that there is a subset of initial states, so that concrete inputs are just the multisets in NI . In order to distinguish both definitions, I will call pure population protocols to those defined using this alternative formalization. The semantics of population protocols is the same in both cases. A configu- ration is any multiset in NQ . We say that a transition q1 , q2 → q10 , q20 is enabled in a configuration C, when {{q1 , q2 }} ≤ C. Then, it can be fired, leading to C 0 = C − {{q1 , q2 }} + {{q10 , q20 }} , and we write C → C 0 . An execution of P is an infinite sequence σ = C0 → C1 → C2 . . . . The output of a non-empty configu- ration C is defined by O(C) = b if and only if for all q ∈ C we have O(q) = b. Then, we say that an execution σ has output O(σ) = b , if there exists i ∈ N such that for all c ∈ N we have O(Ci+c ) = b. However, not all executions count, we only consider fair computations: σ is fair if ∗ ∀D ∈ NQ ( | {i ∈ N : Ci → D } | = ∞ =⇒ | {j ∈ N : Cj = D} | = ∞ ) . Now we say that a classical population protocol P is well-specified and com- putes the predicate φP on any input population α ∈ NX, if for any fair execution σ starting at the initial configuration C0 = I(α) we have φP (α) = O(σ). Instead, a pure population protocol P may compute a predicate on the set of input con- figurations NI : P indeed computes φP , if for any input configuration C0 , and any fair execution σ starting at C0 , we have φP (C0 ) = O(σ) . So, the only difference between these two formalisms is the way the input is presented: Ordinary P protocols take multisets α ∈ NX that are converted into X I(α) ∈ N : I(α)(q) = I(x)=q α(x) ; while in the second case we have directly any multiset C0 ∈ NI as input. It is true that taking X = I ⊆ Q and the identity function as input function we can see any pure protocol as a classical protocol, but this requires the use of input alphabets more elaborate that the usually considered in the classical protocols. However, whenever we are defin- ing the expressive power of a formalism we cannot assume/impose any ‘natural’ Distributed Population Protocols: Naturally! 217 presentation of the input: we cannot state that some states cannot be taken as initial. Following this idea, when the expressive power of population protocols was established their creators considered in [6] pure and not classical ones, al- though the ‘emulation’ result above proves that classical protocols have the same expressive power. Even so, it is true that the use of the external input alphabet looks as very suggestive, since it allows the separation of the description of the input of the solved problem from the details (the set of states) of the protocol that will try to solve it. Nevertheless, if we insist on the use of this input alpha- bet, sometimes this could turn into a too restrictive constraint, instead of being a guide for the definition of the desired protocols. Next I will try to motivate my distributed protocols seeing that the use of the input alphabet by itself is not the root of the problem. But we need to loosen up the one to one relation between the units of the input and the agents of the protocol if we want to design simple and powerful protocols in an easy way. Let us recall how it is proved [5, 12, 9] that the class of predicates definable by some class of protocols is algebraically closed with respect to Boolean operations. This is done considering classical and not pure protocols. In particular, given a fix input alphabet X = {x1 , ..., xk }, and a pair of protocols P1 , P2 computing φ1 (x1 , ..., xk ) and φ2 (x1 , ..., xk ) , a protocol P∧ computing φ1 ∧φ2 is constructed. The first problem with this approach is that whenever we talk about a predi- cate we typically assume a certain ‘universe’ (the set of variables of which ‘it depends’) where it is defined. We need to prove that the conjunction of two (arbitrary) definable predicates is also definable. But then they could ‘depend’ on two different sets of variables ... Yes, no (formal) problem, we can always (al- though artificially) enlarge the set of variables on which a predicate (formally) depends, but if we do this in this framework, it will not be for free! The natural implementation of each predicate will only receive as inputs those corresponding to the value of the variables it depends, but if now we enlarge the input alphabet there will be input units for all the variables on which either φ1 or φ2 depends. Then, both protocols will receive the agents generated by all the input units, even if those corresponding to the variables that are not needed in one of them should not play any role in its computation ... But now they must collaborate in it, and in particular they must receive the final output when it is computed ... We are obliged by the constraint introduced by the use of classical protocols to proceed this way. It seems really strange that we assume these costs, at least without any discussion. At least it is easy to incorporate the additional input agents in the two protocols as dummy agents, that are only there, only waiting for the reception of the computed output value, in order to obtain the required total stable consensus. Since at none of the papers cited above there is a single word about this annoying technical problem, I cannot speculate about whether they did not notice it or they considered the costs perfectly acceptable. But for me this was a strong motivation for looking for another more natural solution where we will need not to invest on totally useless agents. In particular, if φ1 and φ2 depend on two disjoint sets of variables, e.g. we have φ1 (x1 , ..., xk ), φ2 (y1 , ..., yl ), then we can avoid the introduction of all the 218 D. de Frutos Escrig dummy agents simply considering P1 working on X and P2 working on Y . In this way we obtain P∧ based on the aggregation of these two (sub)protocols: we only need a final phase for the calculation and dissemination of the conjunc- tion of the values computed by them. Quite natural, quite easy. And definitely exploding the natural distributed character of population protocols: there were two independent tasks to solve and we have distributed the needed inputs to do it in a totally independent way. However, this solution seems impossible whenever the two predicates ‘re- ally depend’ on the same set of variables X. Let us assume that we have now φ1 (x1 , ..., xk ) and φ2 (x1 , ..., xk ). Even if the states in P1 and P2 remain disjoint, we cannot define I : X → Q1 ∪ Q2 in a satisfactory way as above, since by definition we must direct all the agents corresponding to the same variable to the same state, and this can only correspond to either Q1 or Q2 . But the prob- lem disappears if we consider pure population protocols instead of classical ones. If we need to combine P1 = (Q1 , T1 , I1 , O1 ) and P2 = (Q2 , T2 , I2 , O2 ) , we can assume that Q1 and Q2 are disjoint, and then . . . I1 and I2 are too! This means that we can define P∧ as above, with Q based on the union of the states of Q1 and Q2 , taking I = I1 ∪ I2 , and everything works fine! Definitely, in the pure framework there is no reason for setting aside that simple definition of P∧ . Free of the constraint of the input alphabet, we have seen that pure protocols are more flexible (although formally remain equivalent) that classical protocols. Why should we insist on working ‘mainly’ with the latter? We can interpret the solution above in two different ways: the ‘algebraic interpretation’ renames the variables in φ2 , so that now the variables in both components are disjoint, and then we can proceed as in our introductory exam- ple. The second interpretation recovers the role of the (common) input alphabet X , that has been hidden by our pure protocols. What we have done can be understood as a replication of the (natural) input, so that both (sub)protocols will receive a separate copy of it. We have obtained two independent collection of agents that will compute φ1 (x1 , ..., xk ) and φ2 (x1 , ..., xk ) in a distributed way. Let me now reply to a possible criticism at this point: my protocol P∧ when considered in the pure protocols framework is not exactly computing φ(x1 , ..., xk ) = φ1 (x1 , ..., xk ) ∧ φ2 (x1 , ..., xk ), but . . . more than this! This is certainly true, but who cares? Indeed, when taking I = I1 ∪ I2 we are stating that we can use the states in both subsets as (independent) initial states for the agents participating in P∧ . As a consequence, what we have exactly con- structed is a protocol for the (general) computation of φ(x1 , ..., xk , y1 , ..., yk ) = φ1 (x1 , ..., xk ) ∧ φ2 (y1 , ..., yk ), since we can inject a different number of agents at the two states ‘representing’ each variable in X , at the two sets I1 and I2 . But we can perfectly claim that this more general protocol is also an imple- mentation of our desired predicate φ(x1 , . . . , xk ) = φ(x1 , . . . , xk ) ∧ φ2 (x1 , ..., xk ), simply injecting the same number of agents xi at the two states representing that argument in I1 and I2 , that’s all. Instead, when in [5, 12, 9] the corresponding protocol P∧ is defined, they need to use Q = Q1 × Q2 , so that the pure version of the protocol would also take Distributed Population Protocols: Naturally! 219 I = I1 ×I2 , since in order to preserve the one to one relation between the units defining the values of the variables in X and the agents of P∧ they need to pair the ‘subagents’ working in P1 and P2 using the notion of parallel composition. This produces a less distributed protocol and besides the pairing between the subagents does not reflect any logical connection between the two components, that could be paired in a totally arbitrary way. Let us conclude observing that the proposal above is also exploting the idea of population splitting, as in [2], although I got to it following a different path. Although in an implicit way, I am using a typing mechanism that separates the agents working in a protocol in several disjoint classes in such a way that the code of the protocol will preserve the type of the agents participating in each transition. In this way we get a safe modular methodology (for free!), in the sense typed programming languages provide. 3 Distributed population protocols Definition 1. A distributed population protocol is a tuple P = (Q, I, T, O), where I : X → NQ , for some input alphabet X = {x1 , . . . , xm } , is the input initialization function, T ⊆ Q2 × Q2 and O : Q → {0, 1} is the output function. Transitions are presented as for ordinary protocols. Since we only consider protocols that (possibly) compute a predicate, we have 0 and 1 as output values. Distributed population protocols compute as the ordinary ones, but considering the executions that start at Pthe initial configurations I(α), where α ∈ NX is the m input population: I(α) = i=1 α(xi ) × I(xi ) . Next, I give the definition of a simple distributed protocol computing the con- junction of φ1 (x1 , ..., xk ) and φ2 (x1 , ..., xk ), computed by two distributed popu- lation protocols P1 and P2 that work on the same input alphabet X. Definition 2. Given two distributed population protocols P1 = (Q1 , I1 , T1 , O1 ) and P2 = (Q2 , I2 , T2 , O2 ) that work on the input alphabet X = {x1 , . . . , xk } and compute φ. 1 (x1 , ..., xk ) and φ2 (x1 , ..., xk ), we define P∧ = (Q, I, T, O), taking Q = (Q1 ∪ Q2 ) × {0, 1}, I(x) = I1 (x)×{0} + I2 (x)×{0}, O((qi , b)) = b, and T containing the extended transitions 0 0 0 0 ( qi,1 , qi,2 → qi,1 , qi,2 ) ∈ Ti =⇒ ( (qi,1 , b1 ), (qi,2 , b2 ) → (qi,1 , b1 ), (qi,2 , b2 ) ) ∈ T and the communication transitions (q1,1 , b1 ), (q2,1 , b2 ) → (q1,1 , O1 (q1,1 ) ∧ O2 (q2,1 )), (q2,1 , O1 (q1,1 ) ∧ O2 (q2,1 )) where we are denoting by qi,j the states in Qi . Theorem 1. Given two distributed population protocols P1 = (Q1 , I1 , T1 , O1 ) and P2 = (Q2 , I2 , T2 , O2 ) , that work on the input alphabet X = {x1 , . . . , xk }, and compute the predicates φ1 (x1 , ..., xk ) and φ2 (x1 , ..., xk ), the protocol P∧ = (Q, I, T, O) defined in Definition 2 computes the predicate φ = φ1 ∧ φ2 . 220 D. de Frutos Escrig Proof. We decompose the protocol in two layers, as defined in [12], separating the extended and the communication transitions. The former work on the first component of the states in Q exactly as the transitions of P1 or P2 , so that any fair execution of the extended transitions will lead to a configuration C = C1 + C2 , where each Ci corresponds to one stable configuration of Pi , with O(Ci ) = φi (x) . Next the communication transitions will produce the value φ(x) at all the agents, getting a stable configuration preserving this output. t u Once we have defined the conjunction and disjunction of two well-specified distributed protocols, an immediate induction allows us to compute any Boolean combination of a collection of protocols P1 , . . . , Pk . I only consider expressions e with conjunction and disjunction as operators, since negation can be pushed to the leaves of the expression by applying De Morgan’s laws, and negation of a protocol is obtained simply interchanging 0 and 1 at its output function. Note that the list of protocols above corresponds to all the occurrences of the protocols at the k leaves of the expression, even if this may suppose repeated occurrences of some protocols. Therefore, the expression contains exactly k −1 binary operators. We need to proceed this way since the repeated application of Definition 2 cannot take any advantage of repeated occurrences of the protocols. Let us see which are the states of the protocol Pe that computes the value of e, having P1 , . . . , Pk as leaves. As usual, we can label each protocol argument with the binary path pti from the root of the expression to it. We denote by di the length of pti . We also denote by pt the operator at any internal node reached by pt. Then the protocol Pe obtained by iterated application of Definition 2 to the subexpressions of e can be explicitly described as follows: Definition 3. Given a tree Boolean expression e having the well-specified dis- tributed protocols P1 , . . . , Pk at its k leaves, we define P e = (Qe , I e , T e , Oe ) Pk taking Qe = ∪ki=1 ( Qpt di e i × {0, 1} ) ; I (x) = i 0 i=1 Ii (x) , where 0 adds di 0’s to e e obtain states in Q ; O((qi , s)) = s[1] ; and T contains the extended transitions (qji1 , qji2 → qji10 , qji20 ) ∈ Ti =⇒ ((qji1 , s1 ), (qji2 , s2 ) → (qji10 , s1 ), (qji20 , s2 )) ∈ T e 0 0 and the communication transitions ((qji1 , s1 ), (qji2 , s2 ) → ((qji1 , s01 ), (qji2 , s02 ) , where i 6= i0 , we are denoting by qji the states in Qi , and s01 and s02 are obtained from s1 and s2 by considering the longest common prefix pti,i0 of pti and pt0i and its length lcpi,i0 , simply turning the (lcpi,i0 +1)-th bit of them into v1 pti,i0 v2 where v1 = s1 [lcpi,i0 +2] when lcpi,i0 +1 6= di , and v1 = O1 (qji1 ) , otherwise; and 0 analogously v2 = s2 [lcpi,i0 +2] when lcpi,i0 +1 6= di0 , and v2 = O2 (qji2 ) , otherwise. A couple of examples may clarify this notation. First, we consider i with pti = (1, 1, 0, 1) and i0 with pt0i = (1, 1, 1, 0, 0), so that pti,i0 = (1, 1) and lcpi,i0 = 2 . Then, if s1 = (0, 1, 0, 0), s2 = (1, 0, 1, 1, 0) and pti,i0 = ∧, we obtain s01 = (0, 1, 0, 0) and s02 = (1, 0, 0, 1, 0) , since s1 [4] ∧ s2 [4] = 0 ∧ 1 = 0 . While if pt0i = (1, 1, 1) and 0 0 0 s2 = (1, 0, 1) we need to consider Oi0 (qji2 ) , obtaining s1 [4]∧Oi0 (qji2 ) = 0∧Oi0 (qji2 ) = 0 0 0 , which produces s1 = (0, 1, 0, 0) and s2 = (1, 0, 0) . Although an immediate inductive reasoning provides the correctness proof of this protocol, if we analyze it in a global way we can observe a layered structure, Distributed Population Protocols: Naturally! 221 with as many layers as the height of e . At the first layer the computation of all the argument protocols is done (possibly decomposed into sublayers, depending on the characteristics of each one of them), and then the following layers contain the computations of the subexpressions rooted at each internal node, ‘climbing’ the tree till its root. This observation will play an important role in the definition of a version of the protocol Pe whose state space size remains moderate in all the cases. Firstable, I present the general properties of Pe , as it has been defined. Proposition 1. Given a tree Boolean expression e , the protocol P e in Defini- tion 3 : a) Is correct, computing the value of e applied to the values computed Pk by the protocols Pj ; b) For S = j=1 |Qj | we have |Qe | ≤ S 2h , where h = height(e) ; c) For all c > 1 , whenever e is c-balanced (which means height(e) ≤ c log k) we have |Qe | ≤ k S 2c ; d) In the (very) worst case we have |Qe | ≤ S 2k . Proof. a) It is an immediate consequence of Theorem 1 , since P e is obtained by Pk iterative application of Definition 3. b) Obvious, since |Qe | = j=1 |Qj | × 2dj . c) and d) are immediate corollaries of b). t u In this way, |Qe | will have a moderate size and preserves succinctness of the protocol arguments in the average case, since it is well known that balanced trees are highly probable. However, we are interested in an universal succinctness result that will be obtained by reducing the number of bits s added at the definition of the states in |Qe | . This reduction will be proved correct by applying the following Fact 1 Any tree of size S (where here size means its number of leaves) contains some leave at depth log S. This result is immediate, by bipartition. e Then we define the reduced protocol Pred as follows: e Definition 4. Given a tree Boolean expression e, we define the protocol Pred = (Qered , Ired e e , Tred e , Ored ) taking Qered = ∪ki=1 (Qpt i i ×{0, 1}0..bdi ), where bdi = min({di, e Pk 0 dlog ke}) ; Ired (x) = i=1 Ii (x) , where we add bdi + 1 0’s to obtain states in Qered ; Orede e ((qi , s)) = s[0] ; and Tred contains the extended transitions (qji1 , qji2 → qji10 , qji20 ) ∈ Ti =⇒ ((qji1 , s1 ), (qji2 , s2 ) → (qji10 , s1 ), (qji20 , s2 )) ∈ Tred e 0 0 the communication transitions (qji1 , s1 ), (qji2 , s2 ) → (qji1 , s01 ), (qji2 , s02 ) when di ≤ dlog ke , with s01 [0] = s01 [1] , s02 [0] = s01 [1] and s01 [j] = s1 [j] , s02 [j] = s2 [j] for j > 0 0 0 ; and (qji1 , s1 ), (qji2 , s2 ) → (qji1 , s01 ), (qji2 , s02 ) , now only for i 6= i0 such that (di−lcpi,i0 < dlog ke) ∧ (di−lcpi,i0 < dlog ke) ∧ ((di−lcpi,i0 < dlogke−1)∨(d0i−lcpi,i0 < 0 dlog ke−1)) , and in such a case s01 and s02 are obtained from s1 and s2 by turning the (lcpi,i0 −di +dlog ke+1)-th bit of s1 and the (lcpi,i0 −di0 +dlog ke+1)-th bit of s2 into v1 pti,i0 v2 , where v1 = s1 [lcpi,i0 −di +dlog ke+2] when lcpi,i0 +1 6= di , and v1 = O1 (qji1 ) , otherwise; and analogously v2 = s2 [lcpi,i0 −d0i +dlog ke + 2] , 0 when lcpi,i0 +1 6= d0i , and v2 = O2 (qji2 ) , otherwise. Where in order to simplify the reading I have assumed bdi < di and bd0i < d0i , since in the opposite case the full sequence of bits added in Definition 4 is preserved, and then we work directly with the (lcpi,i0 +1)-th bit, as done there. 222 D. de Frutos Escrig I hope that the cumbersome notation above will not hide the ‘simple’ prun- ing mechanism of the added sequences, by preserving at most the dlog ke last bits attached at the agents of each protocol. These ones keep the values of the subexpressions that correspond to their closest ancestors. Now each agent will only be involved on those computations, leaving the ones for its oldest ancestors to the agents of the protocols that are in any of their first dlog ke generations of successors. Besides, all the agents (q, s) contain one bit (s[0])) for the value of the full expression e . Their values are obtained by firing the first communica- e tion transitions in Tred . This is enough, since Fact 1 guarantees that the correct computation of any subexpression of e is still possible. This can be proved by induction, proceeding bottom up at the tree, because at both sides of each in- ternal node there will be at least one agent (by the way, all those computing any of its closest protocols) that has correctly computed the value of the corre- sponding descendant. These two agents can communicate, since at least one of them still disposes of one additional bit for the saving of the computed value, thus accomplishing the correct computation of the value of the corresponding subexpression. e Proposition 2. Given a tree Boolean expression e , the protocol Pred defined in Definition 4 : a) Is correct, computing the value of e applied to the values Pk computed by the protocols Pj ; b) For S = j=1 |Qj | we have |Qe | ≤ k S ; c) e Whenever the subprotocols Pj are silent, Pred is too. Proof. a) (sketch) We can prove, by induction on the height of each subexpres- sion es of e that all the agents in the set Ps of arguments of es will get a (partial) consensus that includes the value of each of them at the supplied input, and those of each of the subexpressions es0 of es , whose values will remain stable at any of the added bits to keep those values. Moreover, for ks = |Ps |, by applying Fact 1 some of the protocols Pis ∈ Ps is at most dlog ks e levels below the root of es , and since ks < k all the agents working on that protocol contain a bit for the computation of the value of es . Then they will meet some of the agents including a bit for the computation of the value of the other child of the root of es , and applying s the correct value of es will be transferred to the added bit for its computation at the agents in Qis . In particular, the agents with di ≤ dlog ke will compute the value of e , and they communicate it to all the agents working e on Pred . b) Obvious, since we added at most dlog ke bits to each state of the proto- cols Pi . c) We can extend the inductive proof above including the silenceless requirement. Once the agents working at each protocol argument stabilize, the communication transitions will compute the final values of all the added bits, so that no later transition will change them anymore. t u One of the facts proved in [9] to obtain their main theorem stating that it is possible to obtain succinct protocols for the computation of Presburger predicates (this means that they have a polynomial number of states in the size of the predicate, when it is presented by means of a Boolean combination e of threshold and modulo predicates) is that the class of predicates that are Distributed Population Protocols: Naturally! 223 definable by succinct protocols is closed under Boolean operations. Their quite involved proof needs to combine a great number of complex techniques, and those needed to prove the latter result are particularly involved and introduce reverse transitions that make the obtained protocol no silent. Instead, using distributed protocols I have proved Proposition 2 above that in particular will give us succinct protocols for all the Presburger predicates as soon as we have succinct protocols to compute threshold and modulo predicates. In the following sections we will see that the distributed approach also pro- vides simple ways to reduce the number of states of the protocol that implements a certain predicate. These are obtained taking profit of the binary representation of natural numbers, as has been done in [10, 9] . 4 Counting with small agents In [10] a succinct protocol for counting populations based on the use of states for accumulating 2k units is presented. It transfers to the framework of population protocols the binary representation of integer numbers, although only internally at the protocol, while the input is still presented in unary form. To be precise, the considered problem was to decide if the size of the input, which means the number of agents in it, is bigger or equal than a certain natural number n. Their protocol has Q = {2k | k ∈ N, k ≤ log n}∪{0, n} and uses the fact that 2 + 2k = 2k+1 to promote the agents to higher powers. In order to detect the k bound value n they introduce a multiway transition that converts the collection of agents representing the bits of n into one agent n (e.g. for n = 45 , it turns 32+8+4+1 into 45+0+0+0). State n is the only one with output 1, and once it is reached it turns all the other agents into n by means of communicating transitions. Besides, in order to avoid that along an execution the value n will be exceeded (e.g. turning 32+32 into 64+0) without reaching it exactly, they need also reverse transitions that undo the promotion to higher powers. And in order to get a classical protocol, they have to encode the multiway transition generating the state n into a collection of 2-way transitions, something that requires again the introduction of reverse transitions. Next, I present a pure protocol for the counting task, that later I will present as a distributed one, which will be easily modified to solve another more general counting problems. I will show that the introduction of a few more states (dou- bling at most its number) makes possible a very efficient protocol that does not include any reverse transition. Definition 5. For each bound n > 0 we define the pure protocol Pncount = (Qn , In , Tn , On ) with Qn = Qpow n ∪ {0} ∪ Qapr n , where k X pow k Qn = { 2 | k ∈ 0..(l + 1) } Qn = {qn | 2 ≤ k ≤ p } with qnk = 2l + apr k 2ij j=2 where l = b log nc + 1 , the 2-base digits of n are dl . . . d0 (n = dj . . . d0 ) and 1n = {i | 0 ≤ i ≤ l ∧ di = 1 } taking 1n = {i1 , . . . ip } with i1 = l and ij > ij+1 for j ∈ 1..(p−1) , the decreasing enumeration of the bits of n. 224 D. de Frutos Escrig In = {2k | k ≤ l}. Tn = Tnup ∪ Tnapx ∪ Tngoal ∪ Tncomm , where : Tnup : 2k , 2k → 2k+1 , 0 k ∈ 0..l apx Tn : qnk , 2ik+1 → qnk+1 , 0 k ∈ 1..(p−1) Tngoal : qnk , 2j → n, n k ∈ 1..(p−1) , j > ik+1 Tncomm : f, q → f, f f ∈ {2l+1 , n} , q 6∈ {2l+1 , n} The example n = 45 will illustrate this definition. We have Q45 = {1, 2, 4, 8, 16, 32, 64, 0, 40, 44, 45} and some of the transitions in T45 , one for each of its subsets, are: 16, 16 → 32 ; 40, 4 → 44, 0 ; 40, 8 → 45, 45 ; 64, 1 → 64, 64 . Note that, even if we are including in Qn the states in Qaprn , we are maintain- ing its logarithmic size, since l ∈ O(log n), so that between 2l and n we introduce at most l interpolations (in the example, only two: 40 and 44), instead of all the values in the interval (33..45 in the example.) Proposition 3. For each Plinitial configuration C0 ∈ NIn , C0 = k0 · 20 , . . . , kl · 2l , count j Pn decides whether j=0 kj 2 ≥ n. Besides, |Qn | ≤ 2 l ≤ 2 log n . Proof. We decompose the set of transitions into Tnsmall = Tnup ∪ Tnapx , and Tnlarge = Tngoal ∪ Tncomm . Tnsmall contains the transitions that preserve the sum of the values of the evolving agents, while Tnlarge includes those ‘adding’ two agents whose sum is greater or equal than n, and producing two such values. When j large P j=0 j 2 < n , it is obvious that we can never apply a transition in Tn k , so l+1 that for any reachable configuration C we have O(C) = 0 , since 2 , n ∈ 6 C. Instead, when j=0 kjl 2l ≥ n , the application of each transition in Tn will pro- P duce two agents with a total value greater or equal than the sum of the two evolving ones, till we arrive to an stable configuration C. Whenever it contains any final state (2l+1 or n) , by applying the communication transitions we reach a consensus configuration C 0 , with O(C 0 ) = 1. An inductive argument proves that Pg−1 eventually we reach such P a configuration, based on the fact that 2g > k=0 2k , that combined with j=0 kj 2l ≥ n implies that either {{2k , 2k }} ≤ C , for some k ∈ 0..l , or {{qnl , 2j−1 }} ≤ C , with j ∈ 0..l , so that C would not be stable. t u Discussion 1 As explained in the introduction of this section, the presented protocol is an adaptation of the succinct protocol for counting populations in [10]. A fast comparison could conclude that its (correct) behaviour is based on the same ‘essential’ principle: simply the binary representation of integer numbers. However, looking into the details, several important differences arise, all of them (but a single one) representing important advantages of my solution here. I will start with the only (minor) disadvantage: here I have |Qn | ≤ 2 log n states, while the protocol in [10] had at most log n + 2 . Anyway, I maintain |Qn | ∈ O(log n) . Next the main advantage, from which emanate several interesting properties. Pncount satisfies total termination: by the way, revising the correctness proof above it is easy to quantify the duration of its two phases, seeing that there are at most n transitions in Tnsmall , and at most n in Tnlarge . After executing them we reach a silent configuration. So we have an extremely fast silent protocol that besides always terminates (once silent transitions are not considered). Distributed Population Protocols: Naturally! 225 This is a consequence of the fact that I have ‘totally’ avoided both multiway transitions and also reverse transitions by themselves, such as 32, 0 → 16, 16 . Obviously, any introduced reverse transition implies no total termination, and if not ‘explicitly’ somehow avoided, also no silence when a consensus is reached . This usually causes a very poor efficiency, as it is the case in [10]. For instance, in order to reach any (pre)successful configuration (those including one n agent) they need to reach just before the configuration 2 · 2l−1 + (2l − 2) · 0 . Then the 2 probability to execute the transition 2l−1 , 2l−1 → 2l , 0 is n(n−1 ). But these are far from being the worst news. The real problem is that, as a consequence, it is very probable that after executing the following two transitions the reached configuration will be 4 · 2l−2 + (2l −4) · 0 and then to recover our initial transition above we need two hit events whose probability is fairly smaller 2 (for the same reason!) than (n/2)(n/2−1) 2 . In fact, together with another author, the authors of [10] have presented in [11] a very nice executable paper where the reader can find a painful simulation of the protocol (since confirming my predictions above, she must be very very lucky to see its termination, even for very small values of n.) In fact, these ‘nested’ reverse mechanisms are used by the developers of se- quential protocols when they want to control that the second phase of a protocol can start after obtaining (with a certain ‘high’ probability) the result of the first phase (see e.g. [3]). For that they need to measure the passage of an (expected) exponential period of time, and this can be done by checking the termination of a counting protocol somehow ‘similar’ (but simpler) to the one in [10]. In Section 2 we have seen how we should introduce the agents corresponding to the input variables that do not appear in a certain predicate when we want to put together two protocols, for instance for the computation of the conjunction φ(x1 , ..., xk , y1 , ..., yk ) = φ1 (x1 , ..., xk ) ∧ φ2 (y1 , ..., yk ) . A quite natural way of introducing the required dummy agents in a protocol that is making some arith- metic calculation (at the end anyone is doing that, but at the definition of the protocol this can be ‘hidden’), as it is the case of the succinct counting protocols, is to introduce them as 0 agents. Obviously, these protocols will (qualitatively) remain correct after such an addition. However, any superfluous 0 agent will dra- matically delay (even more!) the stabilization of the protocol, since they trigger the execution of the reverse transitions undoing the work of the transitions that produce the progress toward the bound n. Therefore, we should avoid this un- desired effect introducing the dummy agents as totally ‘external’ to the working of the protocol, only participating in the dissemination of its output. Finally, protocols including any reverse cannot be W S 3 protocols, that are the protocols that again the authors of [10], together with another forth author, have shown to be efficiently verifiable in [12]. Instead, with a simple modification in order to satisfy the second condition in the definition of W S 3 protocols, my protocol Pncount becomes W S 3 , and thus efficiently verifiable. From the pure protocols Pncount we can derive a distributed protocol for the addition of (l + 1)-byte numbers in the set Bl = 0..(2l+1 − 1) . For each v ∈ Bl we define the set 1v as 1n in Definition 5, and we take D(v) = {{ 2k | k ∈ 1v }}. 226 D. de Frutos Escrig Definition 6. For each bound n ∈ N the distributed protocol Pnbad for the addi- tion of (l + 1)-byte numbers is defined as Pnbad = (Qn , I bad , Tn , On ) , with Qn , Tn and On as in Definition 5, X = Bl , and I bad : Bl → Qn , with I bad (b) = D(b). Corollary 1. For each bound n ∈ N the distributed protocol Pnbad decides if the Bl P given initial population α ∈ N satisfies b∈α b ≥ n . Finally, I present a distributed protocol for the computation of linear sums a1 x1 + · · · + am xm , with ai , xi ∈ N , for unary representation of the input x . In a similar way we can obtain the distributed protocol for binary inputs. Definition 7. For each vector a ∈ Nm and anyP bound n ∈ N , the distributed m protocol Pna for the computation of linear sums i=1 ai xi is defined as Pna = (Qn , In , Tn , On ) , with Qn , Tn and On as in Definition 5, and Ina : X → Qn , a with X = {x1 , . . . , xm }, and Ina (xi ) = D0 (ai ), where D0 (a) is defined as D(a) for a ∈ Bl , and taking D(a) = {{2l+1 }}, for a ≥ 2l+1 . m Corollary 2. For each vector a Pam ∈ N , and any bound n ∈ N , the distributed protocol Pn decides whether i=1 ai × xi ≥ n . 5 Distributed protocols for Presburger predicates It is well known that classical and pure population protocols compute exactly the family of Presburger predicates. Here we recall its modular characterization as the Boolean closure of the threshold Ps and remainder Pg predicates. Both are defined based on linear expressions i=1 a i x i − j=1 bi yi , with ai , bj > 0 . In the first case we check if the sum is greater or equal than some n ∈ Z , while in the second we check if it is equal to some value n ∈ 0..(m−1) , modulo some given m > 0 . It is not difficult to see that instead of the full family of threshold and remain- der predicates, we can take as basis for the generation of Presburger predicates the family of positive thresholds, that correspond to positive bounds n > 0 , and the bounded positive remainder predicates, that only include positive coefficients ai , and check if the considered sum is greater or equal to n, instead of equality. Next, I present a succinct distributed protocol for the computation of positive threshold predicates, that reduces the number of needed states, as in Section 4. Bounded positive remainder predicates can be implemented following the same ideas, although in that case the role of the transitions 2k − 2k = 0 simplifying the configurations, must be played by the transitions km + x ≡m x . Succinct distributed protocols for positive threshold predicates I tried to develop these protocols following the same ideas that for Pna in Definition 7, but in the beginning this seemed not possible. Why? Because the (simpler) predicate computed there was true-monotonic: whenever an input pop- ulation produces an affirmative output, any bigger population also leads to 1. This is exploited in the design and in the correctness proof of that protocol. In- stead, the negative part of the linear expression now is clearly ‘anti-monotonic’. Distributed Population Protocols: Naturally! 227 We need the balancing transitions that use 2k+(−2k ) = 0 to take into account the contribution of negative agents. If we try to manage approximation agents as in Definition 7, sometimes we will need to turn back these approximations in order to recover the required ‘small’ agents that will make possible some balancing transition. But in order to undo these transitions we need 0-agent partners. It could be the case that we have run out of them, and then we would be stuck. But going back to a protocol that only uses numerical agents with values 2k , as developed in [9], it is possible to circle these difficulties. However, now to check our goal we will need to detect the simultaneous presence of the agents in D(n). This is done in [9] by means of a multiway transition. Instead, we find here another application of our distributed protocols, by choosing an input function that generates a sufficient, but not too large, quantity of agents to play all the roles that are needed to get the desired protocol. Definition 8. For each pair of vectors a ∈ Ns , b ∈ Ng , and bound n > 0 , the thr distributed protocol Pa,b,n for deciding the positive threshold predicate φthr a,b,n ≡ Ps Pg thr thr thr thr thr ( i=1 ai xi − j=1 bj yj ≥ n) is defined as Pa,b,n = (Q , I , T , O ) , where taking z = max({ai | i ∈ 1..s} ∪ { bj | j ∈ 1..g } ∪ {n}) and vl = b log zc + 1, and being dh . . . d0 the 2-base digits of n , and 1n as in Definition 5, we have: Qthr = {(2k , b) | k ≤ h, b ∈ {0, 1}} ∪ {(2k , 1) | h < k ≤ l} ∪ {−2k | k ≤ l} ∪ {(0, 0), (0, 1)} ∪ Qthr thr lead,n , where Qlead,n = Qbn ∪ Qen with Qbn = {(i, ch, o) | i ∈ 1n , ch, o ∈ {0, 1} } and Qen = {eli | i ∈ 1n } In this case, the set X ∪ Y will be our input alphabet, with X = {x1 , . . . , xs } and Y = {y1 , . . . , yg } , and we take I thr (xi ) = {{(2i , 0) | i ∈ 1ai }}+(dlog ai e − |1ai |) · (0, 0) + Qen I thr (yj ) = {{−2j | j ∈ 1bj }}+(dlog bj e − |1bj |) · (0, 0) where we define the sets 1ai and 1bj in an analogous way as we defined 1n . O(q, b) = b , for q ≥ n ; O(q) = 0 , for q < 0 ; O((i, ch, o)) = o ; O(eli ) = 0 . T thr = Tupthr thr ∪ Tdown thr ∪ Tcancel thr ∪ Tmove thr ∪ Tlead ∪ Tcomm thr thr ∪ Tcheck . thr Tup : (2k , b1 ), (2k , b2 ) → (2k+1 , b1 ), (0, b2 ) k ∈ 0..(l−1) : (−2k , b1 ), (−2k , b2 ) → (−2k+1 , b1 ), (0, b2 ) k ∈ 0..(l−1) thr thr Tdown : reverse(Tup ) thr Tcancel : (2k , b), −2k → (0, b), (0, b) k ∈ 0..l : (k, ch, b), −2k → (0, b), (0, b) k ∈ 0..l thr Tmove : (2k , b), elk → (k, 0, b), (0, b) k ∈ 1n Tlead : l1 , (k, ch, b) → l1 , (2k , b) l1 ∈ { (k, ch, b), elk | ch, b ∈ {0, 1} } k ∈ 0..l thr : l1 , elk → l1 , (0, 0) l1 ∈ { (k, ch, b), elk | ch, b ∈ {0, 1} } k ∈ 0..l thr Tcomm propagates any output, either positive or negative, anywhere is possible. Finally, to check that all the leaders are busy (detecting a set of positive agents thr whose sum is n), we have the transitions in Ttest . We consider the enumeration in decreasing order of 1n = {i1 , . . . , ip } (e.g. 145 = {5, 3, 2, 0}), and we have: (i1 , v, b1 ), (i2 , 0, b2 ) → (i1 , v, b1 ), (i2 , 1, b2 ) (ik , 1, b1 ), (ik+1 , 0, b2 ) → (ik , 0, b1 ), (ik+1 , 1, b2 ) 1 < k < (p−1) (ip−1 , 1, b1 ), (ip , 0, b2 ) → (ip−1 , 0, b1 ), (ip , 1, 1) 228 D. de Frutos Escrig This corresponds to the general case of the definition: p > 2 . When p = 1 , which corresponds to n = 2h , we can simply put the value 2h in the set of states with fix output 1 , and then we can avoid the leader mechanism and the test transitions. While when p = 2 , we simply take (i1 , v, b1 ), (i2 , 0, b2 ) → (i1 , v, b1 ), (i2 , 1, 1) . Let me start by clarifying that even if I talk about leaders, they are not such in the usual meaning: they are ordinary agents created by each unit of some of the elements in the input alphabet. Next we will see that the protocol includes a mechanism for the selection of unique leaders between the initial population of leader agents, as in [15, 3]. This is why I keep this appellative in the definition. The first component of the protocol is the balancing procedure that will thr compensate equal agents of different sign, by means of the transitions in Tcancel . thr In order to get the matching pairs we have the transitions in Tdown , that could require the presence of 0-agents. This is why we introduce those agents in the definition of I thr . They will be (more than) enough to do their task. Fairness will guarantee that eventually we will have either no negative or no positive agents. In the latter case, a consensus on 0 output will be reached, thr by applying the transitions in Tcomm . In the former, the protocol must check whether the remaining positive units are n or more. The idea (already used in [9]) is that once only non negative agents remain, by means of the transitions thr thr in Tdown and Tup we can distribute the remaining units in such a way that we can reach a configuration C 0 , including a set of agents corresponding to the thr elements of 1n , if and only if φa,b,n (x, y) = 1 . We need a procedure to detect this situation. We do it by means of the tran- thr thr sitions in Ttest , assuming that previously the transitions in Tlead have selected a family of unique leaders, one for each value in 1n . It will be enough to check that all these leaders are busy to know that the current configuration contains positive agents whose total value is greater or equal than n. This works thanks to thr the transitions in Tmove , that after collecting 2k positive units of the configura- k tion in one 2 -agent, transfer them to the corresponding leader agent when it is empty, turning it into busy. Any successful test will ‘mark’ the output field of the ip -leader agent turning it into (ip , 1, 1) . Next, this 1-output will be broadcasted thr using the transitions in Tcomm . Certainly, when we check the leaders ‘too early’ we could get a hurried pos- itive, that however will not cause any problem, since whenever the balancing procedure discussed above will terminate, either we have no positive agent, and thr then we reach a stable 0 consensus by executing the transitions in Tcomm ; or no negative agent remains in the configuration. When this is the case we can (and we will) fill all the leader agents at the same time if and only if the value of the configuration is greater or equal than n. In the positive case, any test after all the leader agents are busy will succeed, and then the produced 1-output will reach everywhere and the obtained consensus will remain stable. While in the negative case, no test can succeed since the busy leader agents ‘crossed’ by the test will remain busy forever, since no negative agent remains to empty them. As a consequence, any successful test now implies that all the leader agents are Distributed Population Protocols: Naturally! 229 busy at the same time, and therefore the value of the configuration must be greater or equal than n , against our current hypothesis. Note that in the last reasoning above it is crucial that there is no negative agent around, since as long as they are present they could ‘inadvertently’ cause that a test could succeed, even when the total value of the positive agents at the configuration is less than n . This malfunction could occur because some positive units already checked by a test could be ‘liberated’ by a negative agent that expects to remove them by executing a later cancellation transition, but instead those liberated positive agents could fill any of the leader agents still to check, thus cheating the testing procedure since the same units would be used twice. But fortunately, this cause no problem in our protocol, as explained above. If we compare the solution with that in [9], we can see that I do not need any lock for checking that n positive units have been collected. In [9] success is claimed by the firing of the multiway transition, once and again, but this was only possible because they use a special kind of (standard!) leaders, that they call voters. Once more, my proposal here only uses regular agents, thanks to the flexibility of distributed protocols, also avoiding the centralization imposed by those voters. Perhaps you could think that using multiway transitions (that later could be turned into regular ones) I could avoid the introduction of my leader agents. This is not possible: if we look for the agents corresponding to 1n anywhere at the configuration, we could succeed in several directions. But it would be impossible to avoid that any agent that has been affirmatively tested, but then is immediately converted into one (0, 0) agent by one cancellation transition, could be next turned into (0, 1) by a communication with any 1-output agent. But if this happens just when the last negative agent has been cancelled, turning the value of the configuration below n, the broadcasted 1 could not be corrected anymore, thus producing a wrong output. This cannot happen when the removed positive agent is a busy leader, since empty leaders always claim 0 as output. Certainly, as brightly discussed in [18], leaders are always required to generate any ‘asymmetric’ behaviour of the agents in a protocol, and they always intro- duce a certain coordination, which requires some centralization, but that implied by the leaders in this protocol seems not big, since they are only involved in a small part of the transitions of the protocol. thr Let me next just to present the theorem that states the correctness of Pa,b,n . Its formal proof would just present in a more formal way the informal reasoning above. However, I will include below some technical results that are needed in that formal proof. Theorem 2. For each pair of vectors a ∈ Ns , b ∈ Ng , and any bound n > 0 , thr the distributed protocol Pa,b,n decides the positive threshold predicate φthr a,b,n ≡ Ps Pg ( i=1 ai xi − j=1 bj yj ≥ n ) . thr First, we define the value of a configuration C of Pa,b,n as the sum of all its numerical agents, adding 2i for each busy leader (i, v, b) ∈ C . All the transitions of the protocol preserve the value of the configuration, so that for 230 D. de Frutos Escrig any reachable Pg C from any initial configuration I(x, y), we have Psconfiguration value(C) = i=1 ai xi − j=1 bj yj . thr Definition 9. We say that a configuration C of Pa,b,n is simple positive (resp. negative), corresponding to 0 ≤ v < 2l+1 (resp. −(2l+1 ) < v < 0) when for each k ∈ 1v (resp. 1−v ) we have a single agent (2k , b) ∈ C and C((0, t)) + C((0, f )) = |{k : k < l ∧ k 6∈ 1v }| (resp. ∈ 1−v ) and C(q) = 0, for any other q ∈ Qthr . thr This definition captures the fact that along the computations of Pa,b,n we have enough 0-agents around, since the initial configurations can be decomposed into a disjoint union of simple configurations, by applying the definition of I thr . thr Lemma 1. Any simple positive (resp. negative) configuration C of Pa,b,n can be transformed, by applying transitions in Trad thr , into another configuration C 0 = C + {{(1, b)}}, (resp. (−1, b) ) where C either only contains agents (0, b0 ) , or 00 00 is also a simple positive (resp. negative) configuration C of the protocol. Corollary 3. From any initial configuration C0 of Pa,b,n thr we can reach C 0 that contains no (q, b) with q < 0 , or no (q, b) with q > 0 , and value(C 0 ) = value(C) . thr Proposition 4. For any initial configuration C0 of Pa,b,n with value(C0 ) ≥ n , ∗ ∗ if we have C0 → C 0 , we also have C 0 → C 00 , where C 00 contains a full set of busy leaders, i.e. a busy leader agent for each k with dk = 1 . Proof. (Of Theorem 2) Any fair execution will reach a configuration which con- tains one single k-leader, for each k ∈ 1n . Then, fairness also guarantees, as stated by Corollary 3, that we will reach a configuration which either con- tains no negative or no positive agent. Next, Proposition 4 guarantees that we will Ps reach a configuration Pg with single leaders, all of them busy, if and only if i=1 ai xi − j=1 bj yj ≥ n . These situations will be stable. In particular, in thr the affirmative case the execution of the transitions in Ttest will fix 1 as output thr of the leaders, and then the transitions in Tcomm will communicate this value to all the other agents. In the opposite case the set of busy leaders will also stabilize and some leader agent will remain empty forever, so that in the following any test will fail when reaching it. Then, the empty leaders will communicate their thr 0-output using the transitions in Tcomm and the consensus on the output 0 will stabilize. t u 6 Concluding Remarks and some Future Work Only after studying in detail most of the great papers in the References below I got the inspiration to discover the narrow bottleneck that one to one relationship between the units of the input and those of the input configuration, is imposing to classical population protocols. My distributed protocols, that in fact are only a particular case of pure protocols, are in my opinion a simple and elegant proposal that makes much easier the development of simple and more efficient protocols. Distributed Population Protocols: Naturally! 231 So, the introduction of my distributed protocols does not really mean a gen- eralization of the definition of population protocol, but just the confirmation of the fact that using this suggestive class of pure protocols, we can directly man- age specialized agents, without (formally) contradicting the uniformity of the (global) code that governs the behaviour of all the agents of the protocol. The agents can be now designed in a way that, depending on their initial state, each one can only reach a limited set of states (its type!). Then we can (in practice) specialize the code for each type, simply including in it the transitions that have as first agent one member of the type, although of course the met agent could be any. Since I did not want to generalize the notion of population protocol, I have maintained the uniform participation of all the agents in the dissemination of the global (final) output. However, you can find in Definitions 3, 4 two clear examples of structured protocols, based on a family of subprotocols (those cor- responding to all the internal nodes of the expression e) ‘locally’ conceived as ordinary protocols, but whose (local) output must be internalized. This is done in a way that only the agents participating in each subprotocol compute the corresponding local output, and it is only transmmited to other agents as far as they will need it to accomplish their tasks . This idea could be transferred to the global output, so that only the ‘principal’ agents will compute and transmit the final output, while the ‘auxiliary’ agents only would help doing its part, and even could disappear after accomplishing it, following the old notion of coroutine for parallel programming. I plan to continue the exploration of these structuring ideas, looking in particular for a higher level programming language for popula- tion protocols. In this case [16, 2] are interesting starting points. As continuation of this work, based on [12], I have already shown that dis- tributed protocols will also be easy to prove correct, and once more, even easier than classical protocols, specially when the corresponding proofs will be done by hand, but probably also when done in a mechanical way, if the tools can be adapted to take advantage of the modularity of protocols. Besides, I have just submitted [14] where I complete the development of succinct distributed protocols for Presburger predicates, as in [9], providing an alternative succinct threshold protocol, since finally I found the way to do it following the ideas in Definition 5, thus obtaining a silent protocol totally free of reverse transi- tions. And a more involved application of these ideas also produced the required succinct remainder protocol. Acknowledgement. I sincerely thank Javier Esparza, that introduced me to Pop- ulation Protocols, during my stay at TU Munich in April 2017. I also appreciate the indications of the referees of a previous version of this paper. Following them the presentation has been improved, making the paper more readable. This re- search was partially supported by project PID2019-108528RB-C22 and by Co- munidad de Madrid program S2018/TCS-4339 (BLOQUES-CM) co-funded by EIE Funds of the European Union. 232 D. de Frutos Escrig References 1. Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-space trade-offs in population protocols. In 28th ACM-SIAM SODA, pages 2560–2579. SIAM, 2017. 2. Dan Alistarh and Rati Gelashvili. Recent algorithmic advances in population protocols. SIGACT News, 49(3):63–73, 2018. 3. Talley Amir, James Aspnes, David Doty, Mahsa Eftekhari, and Eric E. Severson. Message complexity of population protocols. In 34th DISC, volume 179 of LIPIcs, pages 6:1–6:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. 4. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In 23rd ACM PODC, pages 290–299. ACM, 2004. 5. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Per- alta. Computation in networks of passively mobile finite-state sensors. Distributed Comput., 18(4):235–253, 2006. 6. Dana Angluin, James Aspnes, and David Eisenstat. Stably computable predicates are semilinear. In 25th ACM PODC, pages 292–299. ACM, 2006. 7. Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by popula- tion protocols with a leader. Distributed Comput., 21(3):183–199, 2008. 8. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computa- tional power of population protocols. Distributed Comput., 20(4):279–304, 2007. 9. Michael Blondin, Javier Esparza, Blaise Genest, Martin Helfrich, and Stefan Jaax. Succinct population protocols for presburger arithmetic. In 37th STACS, volume 154 of LIPIcs, pages 40:1–40:15. Schloss Dagstuhl - Leibniz-Zentrum für Infor- matik, 2020. 10. Michael Blondin, Javier Esparza, and Stefan Jaax. Large flocks of small birds: on the minimal size of population protocols. In 35th STACS, volume 96 of LIPIcs, pages 16:1–16:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 11. Michael Blondin, Javier Esparza, Stefan Jaax, and Antonı́n Kucera. Black ninjas in the dark: Formal analysis of population protocols. In 33rd ACM/IEEE LICS, pages 1–10. ACM, 2018. 12. Michael Blondin, Javier Esparza, Stefan Jaax, and Philipp J. Meyer. Towards efficient verification of population protocols. In 36th ACM PODC, pages 423–430. ACM, 2017. 13. Rachel Cummings, David Doty, and David Soloveichik. Probability 1 computation with chemical reaction networks. Nat. Comput., 15(2):245–261, 2016. 14. David de Frutos Escrig. Succinct and fast distributed population protocols. sub- mitted, 2021. 15. David Doty and David Soloveichik. Stable leader election in population protocols requires linear time. In 29th DISC, volume 9363 of LNCS, pages 602–616. Springer, 2015. 16. Bartlomiej Dudek and Adrian Kosowski. Universal protocols for information dis- semination using emergent signals. In 50th ACM SIGACT STOC, pages 87–99. ACM, 2018. 17. Rachid Guerraoui and Eric Ruppert. Names trump malice: Tiny mobile agents can tolerate byzantine failures. In 36th ICALP Proc. Part II, volume 5556 of LNCS, pages 484–495. Springer, 2009. 18. Othon Michail and Paul G. Spirakis. Elements of the theory of dynamic networks. Commun. ACM, 61(2):72, 2018.