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.
Population protocols were introduced by Angluin et al. [
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Probably, the first (intended) limitation of the original model was the
conservation 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
population protocols. Their creators characterized it as that of semilinear predicates,
or equivalently those definable in Presburger arithmetic [
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 probabilistic 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
protocols have been introduced. Doty et al. have developed a large collection of
papers where the dynamic creation of agents makes possible the delay of
certain 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) [
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 [
The rest of the paper is organized as follows. In the next section the basic 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 succinct 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
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 a finite set X are the elements of NX . The size of 2 NX is defined as j j = Px2X (x). When the elements of X are summable, we define Pq2 q = Px2X (x) x . We say that x 2 X is in a multiset , and write x 2 by abuse of notation, if (x) > 0. Multisets will be represented either by extension, in the form ffx1; : : : ; xkgg 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 2 X. Besides, means (x) (x) for all x 2 X, and when , denotes the multiset difference, ( )(x) = (x) (x) . Finally, for k 2 N and 2 NX , we define the product k as the multiset given by (k )(x) = k (x), for each x 2 X. The empty multiset is denoted by 0.
From classical population protocols to distributed protocols. A
population protocol (as in [
An alternative slightly different formalization used in many papers, even by
their original creators (e.g. in [
The semantics of population protocols is the same in both cases. A configuration is any multiset in NQ. We say that a transition q1; q2 ! q10; q20 is enabled in a configuration C, when ffq1; q2gg C. Then, it can be fired, leading to C0 = C ffq1; q2gg + ffq10; q20gg , and we write C ! C0 . An execution of P is an infinite sequence = C0 ! C1 ! C2 : : : . The output of a non-empty configuration C is defined by O(C) = b if and only if for all q 2 C we have O(q) = b. Then, we say that an execution has output O( ) = b , if there exists i 2 N such that for all c 2 N we have O(Ci+c) = b. However, not all executions count, we only consider fair computations: is fair if 8D 2 NQ ( j fi 2 N : Ci ! D g j = 1 =) j fj 2 N : Cj = Dg j = 1 ) .
Now we say that a classical population protocol P is well-specified and computes the predicate P on any input population 2 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 configurations 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 protocols take multisets 2 NX that are converted into
I( ) 2 NX : I( )(q) = PI(x)=q (x) ; while in the second case we have directly
any multiset C0 2 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
defining the expressive power of a formalism we cannot assume/impose any ‘natural’
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 [
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 [
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 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 conjunction 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 ‘really 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 problem 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 example. 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 constructed 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 implementation 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 [
Let us conclude observing that the proposal above is also exploting the idea
of population splitting, as in [
Definition 1. A distributed population protocol is a tuple P = (Q; I; T; O), where I : X ! NQ , for some input alphabet X = fx1; : : : ; xmg , is the input initialization function, T Q2 Q2 and O : Q ! f0; 1g 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 the initial configurations I( ), where 2 NX is the input population: I( ) = Pim=1 (xi) I(xi) .
Next, I give the definition of a simple distributed protocol computing the conjunction of 1(x1; :::; xk) and 2(x1; :::; xk), computed by two distributed population 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 = fx1; : : : ; xkg and compute :1(x1; :::; xk) and 2(x1; :::; xk), we define P^ = (Q; I; T; O), taking Q = (Q1 [ Q2) f0; 1g; I(x) = I1(x) f0g + I2(x) f0g, O((qi; b)) = b, and T containing the extended transitions
( qi;1; qi;2 ! qi0;1; qi0;2 ) 2 Ti =) ( (qi;1; b1); (qi;2; b2) ! (qi0;1; b1); (qi0;2; b2) ) 2 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 = fx1; : : : ; xkg,
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 .
Proof. We decompose the protocol in two layers, as defined in [
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
distributed protocols P1; : : : ; Pk at its k leaves, we define Pe = (Qe; Ie; T e; Oe)
taking Qe = [ik=1( Qipti f0; 1gdi ) ; Ie(x) = Pik=1 Ii(x)0, where 0 adds di 0’s to
obtain states in Qe ; O((qi; s)) = s[
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[
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, 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 Pe in Definition 3 : a) Is correct, computing the value of e applied to the values computed by the protocols Pj ; b) For S = Pjk=1 jQj j we have jQej 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 jQej k S 2c ; d) In the (very) worst case we have jQej S 2k. Proof. a) It is an immediate consequence of Theorem 1 , since Pe is obtained by iterative application of Definition 3. b) Obvious, since jQej = Pjk=1 jQj j 2dj . c) and d) are immediate corollaries of b). tu
In this way, jQej 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 jQej . 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 = (Qreed; Ireed; Treed; Oreed) taking Qreed = [ik=1(Qipti f0; 1g0::bdi ), where bdi = min(fdi; dlog keg) ; Ired(x) = Pk
e i=1 Ii(x)0, where we add bdi + 1 0’s to obtain states in
Qreed ; Oreed((qi; s)) = s[0] ; and Treed contains the extended transitions
(qji1 ; qji2 ! qji0 ; qji0 ) 2 Ti =) ((qji1 ; s1); (qji2 ; s2) ! (qji0 ; s1); (qji0 ; s2)) 2 Treed
1 2 1 2
the communication transitions (qji1 ; s1); (qji02 ; s2) ! (qji1 ; s01); (qji02 ; s02) when di
dlog ke , with s01[0] = s01[
I hope that the cumbersome notation above will not hide the ‘simple’ pruning 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 communication transitions in Treed. 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 internal 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 corresponding 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 computed by the protocols Pj ; b) For S = Pjk=1 jQjj we have jQej 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 subexpression 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 = jPsj, by applying Fact 1 some of the protocols Pis 2 Ps is at most dlog kse 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 on Preed.
b) Obvious, since we added at most dlog ke bits to each state of the protocols 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. tu
One of the facts proved in [
In the following sections we will see that the distributed approach also
provides 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 [
In [
Their protocol has Q = f2k j k 2 N; k log ng [ f0; ng and uses the fact that 2k + 2k = 2k+1 to promote the agents to higher powers. In order to detect the 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 (doubling 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 = Qpnow [ f0g [ Qanpr , where Qpnow = f 2k j k 2 0::(l + 1) g
Qanpr = fqn j 2 k k p g with qnk = 2l + j=2 where l = b log nc + 1 , the 2-base digits of n are dl : : : d0 (n = dj : : : d0) and 1n = fi j 0 i l ^ di = 1 g taking 1n = fi1; : : : ipg with i1 = l and ij > ij+1 for j 2 1::(p 1) , the decreasing enumeration of the bits of n. k X 2ij In = f2k j k lg. Tn = Tnup [ Tnapx [ Tngoal [ Tncomm , where : TTnnauppx :: q2nkk;; 22kik!+1 2!k+q1nk;+01; 0 kk 22 10::::l(p 1) Tngoal : qnk; 2j ! n; n k 2 1::(p 1) , j > ik+1 Tncomm : f; q ! f; f f 2 f2l+1; ng ; q 62 f2l+1; ng
The example n = 45 will illustrate this definition. We have Q45 = f1; 2; 4; 8; 16; 32; 64; 0; 40; 44; 45g 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 Qanpr, we are
maintaining its logarithmic size, since l 2 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 initial configuration C0 2 NIn , C0 = k0 20; : : : ; kl 2l,
Pncount decides whether Plj=0 kj 2j n. Besides, jQnj 2 l 2 log n .
TPnrlaorogfe. =WTengdoaelc[omTnpcoomsem.thTensmsaeltl coofnttarainnssitthioentsrainnstiotioTnnssmtahllat=prTensueprv[e Tthnaepxs u,manodf
the values of the evolving agents, while T large includes those ‘adding’ two agents
n
whose sum is greater or equal than n, and producing two such values. When
Pj=0 kj 2j < n , it is obvious that we can never apply a transition in Tnlarge, so
that for any reachable configuration C we have O(C) = 0 , since 2l+1; n 62 C .
Instead, when Pj=0 kjl 2l n , the application of each transition in Tn will
produce 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 C0, with O(C0) = 1. An inductive argument proves that
eventually we reach such a configuration, based on the fact that 2g > Pgk=10 2k ,
that combined with Pj=0 kj 2l n implies that either ff2k; 2kgg C , for some
k 2 0::l , or ffqnl; 2j 1gg C , with j 2 0::l , so that C would not be stable. tu
Discussion 1 As explained in the introduction of this section, the presented
protocol is an adaptation of the succinct protocol for counting populations in [
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 T small , and at most n in T large . After executing them n n we reach a silent configuration. So we have an extremely fast silent protocol that besides always terminates (once silent transitions are not considered).
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 [
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 [
In fact, these ‘nested’ reverse mechanisms are used by the developers of
sequential 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. [
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 arithmetic 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 dramatically 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 undesired 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 S3 protocols, that are
the protocols that again the authors of [
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 2 Bl we define the set 1v as 1n in Definition 5, and we take D(v) = ff 2k j k 2 1v gg. Definition 6. For each bound n 2 N the distributed protocol Pnbad for the addition of (l + 1)-byte numbers is defined as Pnbad = (Qn; Ibad; Tn; On) , with Qn; Tn and On as in Definition 5, X = Bl, and Ibad : Bl ! Qn, with Ibad(b) = D(b). Corollary 1. For each bound n 2 N the distributed protocol Pnbad decides if the given initial population 2 NBl satisfies Pb2 b n .
Finally, I present a distributed protocol for the computation of linear sums a1 x1 + + am xm , with ai; xi 2 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 2 Nm and any bound n 2 N , the distributed protocol Pna for the computation of linear sums Pm i=1 ai xi is defined as Pna = (Qn; Ina; Tn; On) , with Qn; Tn and On as in Definition 5, and Ina : X ! Qn, with X = fx1; : : : ; xmg, and Ia(xi) = D0(ai), where D0(a) is defined as D(a) for n a 2 Bl, and taking D(a) = ff2l+1gg, for a 2l+1 .
Corollary 2. For each vector a 2 Nm, and any bound n 2 N , the distributed protocol Pna decides whether Pim=1 ai xi n . 5
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 and remainder predicates. Both are defined based on linear expressions Pis=1 ai xi Pjg=1 bi yi , with ai; bj > 0 . In the first case we check if the sum is greater or equal than some n 2 Z , while in the second we check if it is equal to some value n 2 0::(m 1) , modulo some given m > 0 .
It is not difficult to see that instead of the full family of threshold and remainder 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 population 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. Instead, the negative part of the linear expression now is clearly ‘anti-monotonic’. 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 [
Definition 8. For each pair of vectors a 2 Ns; b 2 Ng, and bound n > 0 , the distributed protocol Path;br;n for deciding the positive threshold predicate tah;br;n (Pis=1 ai xi Pjg=1 bj yj n) is defined as Path;br;n = (Qthr; Ithr; T thr; Othr) , where taking z = max(fai j i 2 1::sg [ f bj j j 2 1::g g [ fng) 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 = f(2k; b) j k h; b 2 f0; 1gg [ f(2k; 1) j h < k lg [ f 2k j k lg [ f(0; 0); (0; 1)g [ Qltehard;n , where Qltehard;n = Qbn [ Qen with Qbn = f(i; ch; o) j i 2 1n ; ch; o 2 f0; 1g g and Qen = feli j i 2 1ng
In this case, the set X [ Y will be our input alphabet, with X = fx1; : : : ; xsg and Y = fy1; : : : ; ygg , and we take
Ithr(xi) = ff(2i; 0) j i 2 1ai gg+(dlog aie j1ai j) (0; 0) + Qen
Ithr(yj ) = ff 2j j j 2 1bj gg+(dlog bj e j1bj j) (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 = Tuthpr [ Tdtohwrn [ Tctahnrcel [ T mthorve [ Tltehard [
Tuthpr : (2k; b1); (2k; b2) ! (2k+1; b1); (0; b2)
: ( 2k; b1); ( 2k; b2) ! ( 2k+1; b1); (0; b2) Tdtohwrn : reverse(Tuthpr) Tctahnrcel : (2k; b); 2k ! (0; b); (0; b)
: (k; ch; b); 2k ! (0; b); (0; b) T mthorve : (2k; b); elk ! (k; 0; b); (0; b) Tltehard : l1; (k; ch; b) ! l1; (2k; b) l1 2 f (k; ch; b); elk j ch; b 2 f0; 1g g k 2 0::l : l1; elk ! l1; (0; 0) l1 2 f (k; ch; b); elk j ch; b 2 f0; 1g g k 2 0::l Tctohmrm 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 whose sum is n), we have the transitions in Tttehsrt . We consider the enumeration in decreasing order of 1n = fi1; : : : ; ipg (e.g. 145 = f5; 3; 2; 0g), 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) k 2 0::(l 1) k 2 0::(l 1) k 2 0::l k 2 0::l k 2 1n 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 [
The first component of the protocol is the balancing procedure that will compensate equal agents of different sign, by means of the transitions in Tctahnrcel. In order to get the matching pairs we have the transitions in Tdtohwrn, that could require the presence of 0-agents. This is why we introduce those agents in the definition of Ithr. 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,
by applying the transitions in Tctohmrm. In the former, the protocol must check
whether the remaining positive units are n or more. The idea (already used
in [
We need a procedure to detect this situation. We do it by means of the transitions in Tttehsrt , assuming that previously the transitions in Tltehard 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 the transitions in T mthorve , that after collecting 2k positive units of the configuration in one 2k-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 using the transitions in Tctohmrm .
Certainly, when we check the leaders ‘too early’ we could get a hurried positive, that however will not cause any problem, since whenever the balancing procedure discussed above will terminate, either we have no positive agent, and then we reach a stable 0 consensus by executing the transitions in Tctohmrm; 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 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 [
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 [
Let me next just to present the theorem that states the correctness of Path;br;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 2 Ns ; b 2 Ng, and any bound n > 0 , the distributed protocol Path;br;n decides the positive threshold predicate tah;br;n ( Pis=1 ai xi Pjg=1 bj yj n ) .
First, we define the value of a configuration C of Path;br;n as the sum of all its numerical agents, adding 2i for each busy leader (i; v; b) 2 C . All the transitions of the protocol preserve the value of the configuration, so that for any reachable configuration C from any initial configuration I(x; y), we have value(C) = Pis=1 ai xi Pjg=1 bj yj . thr is simple positive (resp.
Definition 9. We say that a configuration C of Pa;b;n negative), corresponding to 0 v < 2l+1 (resp. (2l+1) < v < 0) when for each k 2 1v (resp. 1 v) we have a single agent (2k; b) 2 C and C((0; t)) + C((0; f )) = jfk : k < l ^ k 62 1vgj (resp. 2 1 v) and C(q) = 0, for any other q 2 Qthr.
This definition captures the fact that along the computations of Path;br;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 Ithr. Lemma 1. Any simple positive (resp. negative) configuration C of Path;br;n can be transformed, by applying transitions in Trtahdr , into another configuration C0 = C00 + ff(1; b)gg, (resp. ( 1; b) ) where C00 either only contains agents (0; b0) , or is also a simple positive (resp. negative) configuration C of the protocol. thr Corollary 3. From any initial configuration C0 of Pa;b;n we can reach C0 that contains no (q; b) with q < 0 , or no (q; b) with q > 0 , and value(C0) = value(C) . Proposition 4. For any initial configuration C0 of Path;br;n with value(C0) if we have C0 ! C0 , we also have C0 ! C00 , where C00 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 contains one single k-leader, for each k 2 1n. Then, fairness also guarantees, as stated by Corollary 3, that we will reach a configuration which either contains no negative or no positive agent. Next, Proposition 4 guarantees that we will reach a configuration with single leaders, all of them busy, if and only if Pis=1 ai xi Pjg=1 bj yj n . These situations will be stable. In particular, in the affirmative case the execution of the transitions in Tttehsrt will fix 1 as output of the leaders, and then the transitions in Tctohmrm 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 0-output using the transitions in Tctohmrm and the consensus on the output 0 will stabilize. tu 6
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.
So, the introduction of my distributed protocols does not really mean a generalization of the definition of population protocol, but just the confirmation of the fact that using this suggestive class of pure protocols, we can directly manage 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
corresponding 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
population protocols. In this case [
As continuation of this work, based on [
Acknowledgement. I sincerely thank Javier Esparza, that introduced me to Population 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 research was partially supported by project PID2019-108528RB-C22 and by Comunidad de Madrid program S2018/TCS-4339 (BLOQUES-CM) co-funded by EIE Funds of the European Union.