Joffroy Beauquier

Janna Burman
email: burman@lri.fr

Laurent Rosaz
email: rosaz@lri.fr

Brigitte Rozoy
email: rozoy@lri.fr

Non-deterministic Population Protocols (Extended Version)

Keywords: networks of mobile agents, population protocols, non-determinism vs. determinism

In this paper we show that, in terms of generated output languages, non-deterministic population protocols are strictly more powerful than deterministic ones. Analyzing the reason for this negative result, we propose two slightly enhanced models, in which non-deterministic population protocols can be exactly simulated by deterministic ones. First, we consider a model in which interactions are not only between couples of agents, but also between triples and in which non-uniform initial states are allowed. We generalize this transformation and we prove a general property for a model with interactions between any number of agents. Second, we simulate any non-deterministic population protocol by a deterministic one in a model where a configuration can have an empty output. Non-deterministic and deterministic population protocols are then compared in terms of inclusion of their output languages, that is, in terms of solvability of problems. Two transformations, which realize this inclusion, are presented. The first one uses (again) the natural model with interactions of triples, but does not need non-uniform initial states. As before, this result is generalized for the natural model with interactions between any number of agents. The second transformation is a parameterized one with parameters depending on the transition graph of the considered non-deterministic protocol and on the population. Note that the transformations in the paper apply to a whole class of non-deterministic population protocols (for a proposed model), in contrast with the transformations proposed in previous works, which apply only to a specific sub-class of protocols (satisfying a so called "elasticity" condition).

Introduction

Population protocols have been introduced [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF] as a computation model (of functions or predicates) for asynchronous networks of simple (anonymous, resource limited) mobile agents, interacting pairwise. A characterization of what can be computed in this model is given in [START_REF] Angluin | The computational power of population protocols[END_REF], namely the first order predicates in Presburger arithmetic. There, the protocols are assumed to be deterministic, meaning that, when two agents interact, there is a unique executable transition. The computational power of non-deterministic population protocols has been only partially studied in [START_REF] Angluin | Stably computable properties of network graphs[END_REF][START_REF] Angluin | Self-stabilizing population protocols[END_REF].

The question concerning the comparison, in terms of computability and expressiveness, of deterministic and non-deterministic machines is a natural question in all computation models. Concerning population protocols, this question appears at different levels.

As population protocols were originally introduced in the context of function and predicate computation [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], at the first level, the question is whether or not deterministic and non-deterministic population protocols compute the same functions and the same predicates (in the sense of [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF][START_REF] Angluin | The computational power of population protocols[END_REF]).

The second level concerns expressiveness in general. Some common method to define any problem (and not only a problem of function or predicate computation) is to define a set of (correct) execution sequences (see, e.g., [START_REF] Tel | Introduction to Distributed Algorithms[END_REF]). An execution of a population protocol generates an output sequence, each configuration being associated to an output value. Thus, a problem can be also defined by the set of (correct) output sequences. Then, a population protocol can be defined to solve a problem, if its (non-empty) set of output sequences is included in the set of output sequences characterizing the problem. 3 At this level, the question is whether or not non-deterministic population protocols solve the same family of problems as the deterministic ones. In other words, are they equivalent in terms of the problems they can solve? This issue is not only theoretical. Indeed, implementing non-determinism is usually made by randomization. However, non-determinism is not randomization. Why using randomization, if a deterministic solution for the same problem is available? At the same time, designing a non-deterministic solution is sometimes easier and more elegant than the equivalent deterministic one. Thus, the availability of automatic transformers of non-deterministic protocols into deterministic ones, could be of some help for a developer. Note that such transformers are generally a by-product of the study on expressiveness.

The third level concerns the generating power of population protocols. In finite automata and language theory, a label is associated to each transition, so that an execution generates a word, and an automaton produces a language. The Rabin and Scott construction [START_REF] Rabin | Finite automata and their decision problems[END_REF] shows that, in terms of generated languages, non-deterministic and deterministic finite automata are equivalent, both generating the family of regular languages. However, language theory is related to programming language analysis and compilation, so its tools and outcomes hardly apply in a model of mobile agents. For instance, the definitions of non/determinism in population protocols are very different. Even if the rules defining a population protocol are deterministic, the resulting global transition system is not, because of the unpredictable interactions assumed between the agents. What is more relevant for the study of the generating power of population protocols is to consider and compare (for equivalence or inclusion) the generated languages of output sequences.

To motivate the study on this third level, note that proving inclusion of the output language of a protocol in the output language of another one implies that the former protocol solves the same problem as the latter. This may appear useful in practice, as already explained before in context of solvability of problems. At the same time, having equivalence of generated output languages can be also of practical help. For instance, if an implementation of a deterministic version of a protocol is preferable to that of a non-deterministic one (e.g., due to some development cost reasons), it can be useful and even necessary to have the same set of output sequences generated by the corresponding deterministic protocol. For instance, one reason may be efficiency in terms of time complexity. That is, e.g., the average complexity or the complexity of prevalent execution scenarios could be much better when concerning the larger set of executions/output sequences. Another reason may be the necessity to perform statistics over the whole set of execution/output sequences that can be generated by the non-deterministic protocol. Thus, it will be helpful to study whether the deterministic version of the protocol generates the same language. Now, we summarize what is already known and what are the new results in this paper about population protocols in terms of the three types of questions explained above. First, the question about the computational power (in terms of predicate or function computability) of non-deterministic population protocols has been already raised in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF]. One can consider it received an answer in [START_REF] Angluin | Stably computable properties of network graphs[END_REF], where it is actually only stated that the nondeterministic population protocols compute exactly the Presburger predicates, exactly like the deterministic ones. 4In the context of problem solvability in general, (rather than in the context of computability of predicates or functions), [START_REF] Angluin | Self-stabilizing population protocols[END_REF] proves that the protocols solving the, so called, elastic problems (elastic behaviors, in terms of [START_REF] Angluin | Self-stabilizing population protocols[END_REF]), have a deterministic counterpart solving the same problem. To define elastic problem, first, define the repetition closure of a sequence t as the set of sequences obtainable from t by repeating each element of t one or more times. Extend this definition to a set of sequences O by taking the union of repetition closures of every sequence t ∈ O. Then, O is said elastic if it is closed by repetition closure. An elastic problem is a problem characterized by an elastic set of output sequences. Note however that this result of [START_REF] Angluin | Self-stabilizing population protocols[END_REF] does not imply that the output language of the deterministic counterpart is included in the output language of the given non-deterministic protocol. Still, one can deduce the following different result for some smaller class of protocols that we call strongly elastic.

A population protocol is strongly elastic, if for every rule (p, q) → (p ′ , q ′ ) of the protocol, there is an idempotent rule (p, q) → (p, q). Then, it can be easily deduced from [START_REF] Angluin | Self-stabilizing population protocols[END_REF] that, if a problem is elastic and if there exists a strongly elastic non-deterministic population protocol solving this problem, then there exists a transformation giving a deterministic population protocol solving the same problem and moreover, with an output language included in the output language of the non-deterministic protocol.

However, the transformation in [START_REF] Angluin | Self-stabilizing population protocols[END_REF] does not provide the equality between the output languages of the strongly elastic non-deterministic population protocol and of its deterministic transformed version. In this paper, we study a way to obtain such an equality for population protocols in general (Sec. 3). Unfortunately, we come with a counter example (Sec. 3.1). When studying carefully the reason for this negative result, it appears that a natural way for simulating the non-determinism in the transitions of a non-deterministic population protocol is to use the non-determinism in the interactions between the agents. The negative result comes from the fact that, when there are not enough possible interactions between agents, a high degree of non-determinism in the transitions cannot be simulated.

In order to circumvent this negative result, we propose (in Sec. 3.2) to increase the number of possible interactions by allowing interactions between more than two agents. Without changing the total number of agents, this allows more non-determinism. As a matter of fact, we prove that a non-deterministic population protocol with pairwise interactions can be exactly simulated by a deterministic population protocol with three agent interactions, under the assumption that the initial states of the agents may be different. We show how this result can be generalized to k agent interactions, for any integer k > 1.

A second attempt to obtain equality of output languages consists in modifying slightly the definition of what can be an output value of a configuration (Sec. 3.3). Thus, an empty output value for a configuration is introduced such that, when it appears in the output sequence, it is taken as an identity element. We show that, in this extended model, the equality of output languages of non-deterministic and deterministic population protocols is obtained.

The results about equality of output languages yield also results about inclusion. However, we try to weaken the assumptions (that are made to obtain equality) in order to obtain stronger results about inclusion. It happens that, when considering interactions with more than two agents, we do not need non-uniform initial agent states, as we require for obtaining equality (see Sec. 4.1). This involves that, if the model does not restrict the number of agents in the interactions, non-deterministic and deterministic population protocols are equivalent, in terms of solvability of problems.

Finally, in the original model of pairwise interactions, we extend the result of inclusion for strongly elastic population protocols to the whole class. Contrary to [START_REF] Angluin | Self-stabilizing population protocols[END_REF], we cannot provide a transformation that is independent from the non-deterministic population protocol it transforms. We believe that such a general transformation does not exist and we explain the reason why (see appendix). However, for getting the inclusion result, we do not need this independence. Indeed, in Sec. 4.2, we propose a parameterized transformation. The parameters are the considered non-deterministic protocol and the population (the number of agents and their interaction graph). Given these parameters, the transformation constructs a deterministic population protocol solving the same problem as the given non-deterministic one.

Basic Model and Notations

As a basic model, we use the model of population protocols, as defined in [START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Fischer | Self-stabilizing leader election in networks of finite-state anonymous agents[END_REF]. A population  consists of a set A of n agents together with a weakly connected directed graph G(A,E). An agent represents a finite state sensing device and n is unknown to the agents. G(A, E) is called the interaction (or communication) graph, where E ⊆ A × A. An edge (u, v) ∈ E represents the possibility of a communication (an interaction) between u and v in which u is the initiator and v is the responder.

Population protocols can be modeled as transition systems. Thus, each agent is represented by the same finite transition system. The states of agents are from a finite set Q. Each agent has a constant input value and different agents may have different input values. For simplicity and as we assume constant input values, we consider the inputs as a part of the state of an agent. There is an output value associated to each state of an agent. A transition function δ maps each element of

Q × Q to a subset of Q × Q. Let (p, q) ∈ Q × Q. If (p ′ , q ′ ) ∈ δ(p, q), then (p, q) → (p ′ , q ′ )
is called a transition, and (p, q) → δ(p, q) is called a rule. When, two agents u, in state p, and v, in state q, interact (meet), respectively playing the roles of initiator and responder, they execute a transition (p, q) → (p ′ , q ′ ) such that (p ′ , q ′ ) ∈ δ(p, q). As a result, u changes its state from p to p ′ and v from q to q ′ . It is possible that p = p ′ and/or q = q ′ . The transition function and the protocol are deterministic, if δ(p, q) always contains just one pair of states (in other words, if each rule provides just one transition). Otherwise, if |δ(p, q)| = k > 1, δ and the protocol are said non-deterministic (then u, v execute one of the k transitions in δ(p, q) chosen non-deterministically). Let us call k the degree of non-determinism of the rule (p, q) → δ(p, q). Let d = max (p,q)∈Q×Q {|δ(p, q)|} be the degree of non-determinism of δ and of the protocol. For simplicity, for any non-deterministic protocol, if for some (p, q) ∈ Q × Q, |δ(p, q)| < d, we duplicate some pairs of states in δ(p, q) in order to obtain |δ(p, q)| = d. Thus, w.l.o.g., we assume that

∀(p, q) ∈ Q × Q, |δ(p, q)| = d.
A population protocol is also a finite transition system whose states are called configurations. A configuration is a mapping C : A → Q. A subset of configurations C 0 defines the initial configurations. We say that C goes to C ′ via pair (interaction

) π = (u, v), denoted C π → C ′ , if the pair (C ′ (u), C ′ (v)) is in δ(C(u), C(v))
and for all w ∈ A \ {u, v}, C ′ (w) = C(w). We say that C can go to C ′ in one step (or

C ′ is reachable in one step from C), denoted C → C ′ , if C π → C ′ for some edge π ∈ E. If there is a sequence of configurations C = C 0 , C 1 , . . . , C k = C ′ , such that C i → C i+1 for all i, 0 ≤ i < k, we say that C ′ is reachable from C, denoted C * → C ′ .
An execution is an infinite sequence of configurations C 0 , C 1 , C 2 , . . . such that C 0 ∈ C 0 and for each i, C i → C i+1 . The output of a configuration C is the multi-set of the output values of agents in C. The output word (or the output trace) of an execution e = C 0 , C 1 , C 2 . . . is a sequence O 0 , O 1 , O 2 , . . . resulting from the concatenation of the successive outputs of the configurations of e. That is, for all i ≥ 0, O i is the output of the configuration C i . The set of output words of a protocol P is called the (generated) output language of the protocol and denoted by L(P ).

Let P 1 and P 2 be two protocols with sets of states

Q 1 and Q 1 ×Q ′ respectively, for some set Q ′ . For a state s 2 = [s 1 s ′ ] ∈ Q 1 × Q ′ of P 2 , where s 1 ∈ Q 1 and s ′ ∈ Q ′ , Π P1 (s 2 ) = s 1 . That is, Π P1 (s 2 )
denotes the state of P 1 which is the projection of s 2 on P 1 (in other words, which is the mapping of s 2 to the state component of P 1 ). We extend the notation of Π in the natural way to configurations, sets of states or configurations, rules, transitions and executions.

A problem is defined by some conditions on executions, or equivalently by the sub-set of the executions that satisfy the conditions. As an output word associated to an execution can be defined to be the execution sequence itself (by defining the output of each agent as being the whole state), a problem can be well defined by giving conditions only on output words. Thus, w.l.o.g. and for the sake simplicity, we assume that a problem is defined by conditions on output words, i.e., by a sub-set B of output words. A population protocol is said to solve a problem, if and only if the set of its output words O is non-empty and each output word o ∈ O satisfies the conditions defining the problem, i.e., o ∈ B or equivalently, O ⊆ B (see, e.g., [START_REF] Tel | Introduction to Distributed Algorithms[END_REF]).

The transition graph G(P, Â) of a protocol P running in population  is a directed graph whose nodes are all possible population configurations and whose edges are all possible transitions on those nodes. A strongly connected component of a directed graph is final iff no edge leads from a node in the component to a node outside.

As originally for population protocols, we assume a strong fairness condition on the executions that is called global fairness. An execution is said globally fair, if for every two configurations C and C ′ such that C → C ′ , if C occurs infinitely often in the execution, then C ′ also occurs infinitely often in the execution.

Results about Equality of Output Languages

In this section, we study the strong relation of equality between the sets of output languages of deterministic and non-deterministic population protocols. First, we give a negative result (Theorem 1, Sec. 3.1) showing that in the basic model of Sec. 2, in terms of the equality between the sets of generated output languages, nondeterministic protocols are more powerful. Then, in sections 3.2 and 3.3, we propose two model extensions that allow to circumvent this negative result.

A Negative Result

The following example provides some simple preliminary intuition for the result stated in Theorem 1 below. Consider a population of two agents in the initial configuration (q 0 , q 0 ) and the non-deterministic protocol P with two rules (q 0 , q 0 ) → {(q 0 , q 0 ), (q 1 , q 1 )} and (q 1 , q 1 ) → (q 0 , q 0 ). Assume that the output of an agent in P is its state. Then, each output word is an infinite concatenation of the output sequences of the form (q 0 , q 0 ) k , (q 1 , q 1 ), for any positive integer k. Thus, P has an output language of infinite size. However, the output language of any deterministic protocol executing on two agents (with finite states) has a finite size. This example proves the theorem below for two agent populations. Note that the same argument is wrong in larger populations, since then, intuitively, there exists a non-determinism in the choice of interactions that can lead to an infinite output language size. In the proof of the theorem, we give an example that works for a population of any size n.

Theorem 1. Given a population of size n, the set of output languages of non-deterministic population protocols strictly contains the corresponding set of deterministic population protocols.

Proof. It consists in exhibiting an example of a non-deterministic protocol whose output language is not equal to the output language of any deterministic protocol.

Consider a population of n agents and a non-deterministic population protocol P . Let t = n•(n-1). Let P to have a single non-deterministic rule (p 0 , p 0 ) → {(p 1 , p 1 ), (p 2 , p 2 ), . . . , (p t+1 , p t+1 )}, and t + 1 deterministic rules (p 1 , p 1 ) → (p 0 , p 0 ), (p 2 , p 2 ) → (p 0 , p 0 ), . . . , (p t+1 , p t+1 ) → (p 0 , p 0 ). Let o i be the output value associated to a state p i . We choose o i = p i . The initial configuration of P is C 0 = (p 0 , p 0 , p 0 , p 0 ). Note that the output of C 0 is the multi-set M 0 = {p 0 , p 0 , p 0 , p 0 }. Assume, for the sake of contradiction, that there is a deterministic population protocol P ′ such that L(P ′ ) = L(P ).

In P , consider all the prefixes of execution of a type e = (C 0 , C). There are exactly t + 1 different configuration output prefixes corresponding to these execution prefixes. Now, consider the concatenation of two such prefixes e e , which is also a prefix of a possible execution in P . The number of different configuration output prefixes for e e is (t + 1) 2 , and more generally, for the concatenation of k prefixes of e , the number is (t+1) k . Denote by H k the set of these output prefixes (|H k | = (t+1) k ). Since L(P ′ ) = L(P ), all the prefixes in H k are also output prefixes of P ′ . However, if P ′ has a single configuration with output {p 0 , p 0 , p 0 , p 0 } = M 0 , P ′ can "generate" only t output prefixes of length 2, starting from C 0 . More generally, P ′ can "generate" only t k output prefixes composed by concatenation of k output prefixes of length 2, starting from C 0 . The number t = n • (n -1) is the maximum number of different pairs of states that n agents can have (with the distinction between initiator and responder).

Thus, since |H k | = (t + 1) k > t k , but L(P ′ ) = L(P ), P ′ has necessarily more than one configuration with output {p 0 , p 0 , p 0 , p 0 } = M 0 . Assume then that P ′ has r different configurations with output M 0 . Each of them "generates" at most t k different concatenated (k times) output prefixes of length 2 starting with C 0 . That is, P ′ can "generate" at most r • t k different such output prefixes. However, since L(P ′ ) = L(P ), r • t k must be at least as large as (t + 1) k . This involves that r is at least as large as (t+1) k t k and that, for every integer k ≥ 1. A contradiction arises from the fact that r is bounded by the number of the configurations of P ′ which is finite.

⊓ ⊔ An immediate corollary from the proof of Theorem 1, is that one of the reasons for the theorem correctness is the assumption that each agent in population protocols has only a finite size state. One can also notice that the negative result comes from the fact that, when there are not enough possible interactions between agents, a high degree of non-determinism in the transitions cannot be simulated by any deterministic protocol. That is why, increasing the number of agents in an interaction, as in Sec. 3.2, allows to overcome the negative result.

Equality with Interactions of More than Two Agents

One way to increase the degree of non-determinism through the interactions of agents is to consider a more general population protocol model, where the interactions concern more than only two agents. The issue of considering such a generalization was raised already in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], but to our knowledge, it was not dealt in the literature in the context of non-deterministic protocols as in this work.Thus, to obtain the desired equality of output languages, we consider interactions involving more than two agents. Roughly, the idea is to assign a different integer from [1, d] to each agent, where d is the degree of non-determinism of the given nondeterministic protocol. Then, we simulate deterministically the k th (k ∈ [1, d]) choice of a non-deterministic transition between two agents u and v, by an interaction between three agents u, v and an agent holding the integer k.

Let us denote by PP k the model of population protocols in which possible interactions are between k agents or less. The definition of PP k follows the definition of the basic model of population protocols in Sec. 2. However, for PP k , we should generalize the definition of the transition function δ and the notion of initiator and responder. During an interaction of k ′ agents, u 1 , u 2 , . . . , u k ′ , 2 ≤ k ′ ≤ k, we say that u 1 is the initiator, u 2 is the primary responder, u 3 is the secondary responder, and so on. Now, δ maps each element in

Q k ′ , for each 2 ≤ k ′ ≤ k, to a subset of Q k ′ .
We first prove the following result.

Theorem 2. Consider a non-deterministic population protocol P 1 with the degree of non-determinism d. Let Â, be any population with n ≥ d + 2 and a complete interaction graph. Given a protocol P 1 executing on  in PP 2 (the basic model of Sec. 2), there exists a deterministic population protocol P 2 executing on  in PP 3 (with d + 2 non-uniform initial states) 5 and generating the same output language as P 1 .

The proof consists in, first, constructing for any population protocol P 1 a deterministic population protocol P 2 and then, in proving that L(P 1 ) = L(P 2 ). Thus, we first construct P 2 . As explained in Sec. 2, we assume, w.l.o.g., that all the rules of P 1 have the same degree d of non-determinism. The state of an agent in P 2 is a couple [p c], where p is a state of P 1 (p is the projection of [p c] on P 1 , denoted Π P1 ([p c]) = p), and c is an input value of P 2 which is an integer in [1, m], m = d + 2. The purpose of c is to serve as a switch value to decide deterministically, in P 2 , on a transition of a non-deterministic rule of P 1 . For every initial configuration C 0 of P 1 , there is one initial configuration C ′ 0 of P 2 such that Π P1 (C ′ 0 ) = C 0 . We make an important assumption about the input value c. During an execution, each value in [1, m] is the input value c of at least one agent (in all this section, we assume n ≥ m). The output of the state [p c] in P 2 is the output of p in P 1 . To each rule (p, p ′ ) → {(p 1 , p ′ 1 ), (p 2 , p ′ 2 ), ..., (p d , p ′ d )} of P 1 , the construction associates three types of deterministic rules of P 2 : i. For c in [1, d],

([p c 1 ], [p ′ c 2 ], [q c]) → ([p c c 1 ], [p ′ c c 2 ], [q c]) ii. For c 1 in [1, d], ([p c 1 ], [p ′ c 2 ]) → ([p c1 c 1 ], [p ′ c1 c 2 ]) iii. For c in {d + 1, d + 2}, ([p c 1 ], [p ′ c 2 ], [q c]) → ([p c2 c 1 ], [p ′ c2 c 2 ], [q c])
The intuition behind the rules of P 2 is, for any pair of states (p 2 , p ′ 2 ) with Π P1 (p 2 , p ′ 2 ) = (p, p ′ ), to be able to simulate any possible transition in the set δ(p, p ′ ) of P 1 , and this by executing only one transition of P 2 . For obtaining the equality of output languages, it is important to be able to execute exactly one transition for this purpose. 6 Thus, the rule of type i. serves to execute a projected transition (p, p ′ )

(u,v) → (p c , p ′ c )
, for two agents u, v, in the case where there exists another agent holding the switch input value c. Otherwise, the rules of type ii. and iii. are provided for the case where the same "needed" switch value is unique and held either by the initiator or by the primary responder (respectively). Below, we prove the equality of the output languages of P 1 and P 2 . For that, we first prove the following basic lemma that actually validates the intuitive ideas explained above. Lemma 1. Let C 2 be a configuration of the deterministic protocol P 2 given by the construction above. Let

C 1 = Π P1 (C 2 ) and let C ′ 1 be any configuration of P 1 such that C 1 → C ′ 1 . Then, there exist a configuration C ′ 2 of P 2 and C 2 → C ′ 2 such that C ′ 1 = Π P1 (C ′ 2 ).
Proof ) is a globally fair execution of P 1 and thus the output word of e 2 is in the output language of P 1 . Then, we show that for every globally fair execution e 1 of P 1 , there is a globally fair execution of P 2 whose projection on P 1 is e 1 and thus, the output word of e 1 is in the output language of P 2 . Thus, let e 2 be a globally fair execution of P 2 . The projection e 1 = Π P1 (e 2 ) is an execution of P 1 , since, by construction, the projection of each transition of P 2 is a transition of P 1 . In the following, we show that e 1 is globally fair. Let C 1 be a configuration of P 1 appearing infinitely often in e 1 , and let C ′ 1 be a configuration reachable in one step from

C 1 , C 1 → C ′ 1 .
Then, since e 1 is the projection of e 2 , there are infinitely many configurations appearing in e 2 , whose projection is C 1 . Thus and by the finiteness of the states of the agents, there is such a configuration C 2 , appearing infinitely often in e 2 . By Lemma 1, a configuration C ′ 2 of P 2 whose projection is C ′ 1 is reachable from C 2 in one step. As e 2 is globally fair, C ′ 2 appears infinitely often in e 2 . Thus C ′ 1 appears infinitely often in e 1 . That proves that e 1 is globally fair. Now consider a globally fair execution e 1 of P 1 . Consider the prefix of e 1 of length r, e r 1 , for some integer r ≥ 1 and assume (by induction on r) that there exists a segment e r 2 , prefix of an execution of P 2 , with projection e r 1 on P 1 (the basis of the induction, for r = 1, holds by construction). Assume that

e r+1 1 = (e r-1 1 , C 1 , C ′ 1
) and e r 2 = (e r-1 2 , C 2 ). By Lemma 1, a configuration C ′ 2 of P 2 whose projection is C ′ 1 is reachable from C 2 in one step. Thus, there is a prefix of an execution of P 2 , e r+1 2 , whose projection on P 1 is e r+1 1 . Thus, by induction, an execution e 2 whose projection is e 1 can be built. As e 1 is globally fair and as the switch values are constant, e 2 is also globally fair.

⊓ ⊔

The result of Theorem 2 can be generalized for any k.

: i. For c in [1, d], ([p 1 c 1 ], [p 2 c 2 ], . . . , [p k ′ c k ′ ], [q c]) → ([p c1 c 1 ]), [p c2 c 2 ], . . . , [p ck ′ c k ′ ], [q, c]) ii. For c in [d + x • k + 1, d + x • k + k] and for any integer x, 0 ≤ x < k ′ , ([p 1 c 1 ], [p 2 c 2 ], . . . , [p ′ k c k ′ ], [q c]) → ([p c x 1 c 1 ], [p c x 2 c 2 ], . . . , [p c x k ′ c k ′ ], [q c])
Another transformation protocol to simulate the non-deterministic protocol P 1 , denoted P ′ 3 , differs from P 3 by the value of m, the conditions on the inputs and by the transition function δ. Thus, for P ′ 3 , m = d. During any execution, each value in [1, m] is the input value c of at least k + 1 agents. To each rule of P 1 , (p 1 , p 2 , . . . , p k ′ ) → {(p 11 , p 12 , . . . , p 1k ′ ), (p 21 , . . . , p 2k ′ ), . . . , (p d1 , . . . , p dk ′ )}, for 2 ≤ k ′ ≤ k, the construction associates the following deterministic rule of P ′ 3 :

([p 1 c 1 ], [p 2 c 2 ], . . . , [p k ′ c k ′ ], [q c]) → ([p c1 c 1 ], [p c2 c 2 ], . . . , [p ck ′ c k ′ ], [q c]
). To see the correctness of the transformations, notice that Lem. 1 holds also for P 3 and P ′ 3 . That is, given any configuration C 3 of the transformed protocol (P 3 or P ′

3 ) and its projection C 1 on P 1 , for any

C ′ 1 such that C 1 → C ′ 1 , there exists a configuration C ′ 3 such that C 3 → C ′ 3 , and C ′ 1 = Π P1 (C ′ 3
). The rest of the correctness proof follows the proof of Theorem 2. 7 ⊓ ⊔

Equality by Simulation with Empty Outputs

Theorem 1 states that there is no Rabin and Scott-like construction for population protocols, at least with the original definitions of [START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Fischer | Self-stabilizing leader election in networks of finite-state anonymous agents[END_REF]. We note that the negative property strongly depends on the definition of what an output value can be. We think this definition can be changed, without reappraisal of the basic model of population protocols. In the sequel, we investigate the way of modifying the definition of the output of a configuration, in order to get an equivalence result for the output languages. The idea we develop is to consider an empty output ϵ for a configuration, serving as an identity element in the monoid generated by output values of configurations. That is, we allow the empty output ϵ to be a possible output value for a configuration such that for any segment of an output word o,

(o, ϵ) = (ϵ, o) = o.
Intuitively, this idea of introducing empty outputs in the model can be helpful in the following way. For instance, assume that agents, in the deterministic protocol (simulating the non-deterministic one), hold different integers used as a switch to indicate one of the possible non-deterministic choices. These switch values can be changed by the protocol. A problem arises when an agent u in a state p, holding the switch value c, interacts with an agent v in a state q, but the non-deterministic choice c ′ has to be simulated to obtain a specific output word (to obtain equality of output languages with the non-deterministic protocol). In this situation, one would like to perform some transitions (called null-transitions, in the sequel) to obtain a configuration where the switch value c ′ is in u and the rest of the states of u and v stays unchanged. However, the outputs of the intermediary configurations reached by these null-transitions are repetitions of the same value. This may result in an output word that is not in the output language of the corresponding non-deterministic protocol. With empty outputs, it is possible to remove such repetitions of the same output and obtain the equality of the output languages. Notice that a difficulty comes from the fact that the same configuration can be reached either by a null or a non-null-transition. In the first case, it is required to output the empty output, but not in the second.

Theorem 4. In terms of generated output languages, the non-deterministic and the deterministic population protocols are equivalent in the model allowing empty outputs for configurations.

To prove the theorem, we present a general technique to transform the rules of any non-deterministic population protocol P 1 into the deterministic rules of a population protocol P 3 , in the model with empty outputs. Next, we prove that L(P 1 ) = L(P 3 ) (see Theorem 5). The transformation we propose, denoted D, takes as an input a protocol P 1 and another deterministic transformation D ′ . It is required that D ′ applied to P 1 , denoted D ′ (P 1 ), results in a deterministic protocol P 2 satisfying conditions defined in Property 1 below. We write P 2 = D ′ (P 1 ) and P 3 = D(D ′ (P 1 )). In the sequel, we show that there exists such a transformation D ′ , e.g., the transformation presented in [START_REF] Angluin | Self-stabilizing population protocols[END_REF] (see Lem. 4). Recall that this transformation (in [START_REF] Angluin | Self-stabilizing population protocols[END_REF]) only applies to some sub-class of protocols and does not provide the equality of languages for non/deterministic protocols even for this sub-class.

We use the following definitions to state Property 1 and to define D. Let P and P ′ be two protocols with sets of states Q and Q × Q ′′ respectively, for some set Q ′′ . A transition t of P ′ , (p, q) → (p ′ , q ′ ), is called a (P -)null-transition, if (p, q) ̸ = (p ′ , q ′ ), but Π P (p, q) = Π P (p ′ , q ′ ). Two consecutive and different configurations C 1 , C 2 in an execution of P ′ are called (P -)similar, if C 2 is obtained from C 1 by a P -null-transition (that is, Π P (C 1 ) = Π P (C 2 )).

Property 1. Let P 1 be any non-deterministic population protocol with a set of states Q 1 . Protocol P 2 is said to satisfy Property 1, if it satisfies the following conditions:

1. The protocol P 2 is a deterministic protocol with a set of states Q 1 × Q ′ , for some set Q ′ . The projection of the rules of P 2 on P 1 , is the set of rules of P 1 . 2. The output of a configuration C in P 2 is the output of the configuration Π P1 (C) of P 1 .

For every initial configuration

C 0 of P 1 , there is one initial configuration C ′ 0 of P 2 such that Π P1 (C ′ 0 ) = C 0 . 4. For every two configurations C, C ′ of P 2 , if C → C ′ , then C ̸ = C ′ . 5. Let C 2 be a configuration of P 2 such that C 1 = Π P1 (C 2 ). Let C ′ 1 be a configuration of P 1 such that C 1 → C ′ 1 .
Then, there exists a configuration

C ′ 2 such that C 2 * → C ′ 2 and Π P1 (C ′ 2 ) = C ′ 1 . In addition, C ′ 2
is reachable from C 2 using a finite number of null transitions of P 2 , except for the last transition that results in C ′ 2 .

Definition of the transformation D.

The main idea of the transformation D is to simulate P 2 = D ′ (P 1 ) (satisfying Property 1) while eliminating the effect of the P 1 -null-transitions of P 2 in the output words. This is done by introducing empty outputs, for obtaining the equality of output languages. Now, we define the protocol

P 3 = D(P 2 ). Let Q 1 and Q 2 = Q 1 × Q ′ be
the sets of states of P 1 and P 2 , respectively. Starting from P 2 , we build a deterministic population protocol P 3 , which has a lot of similarities with P 2 , but differs mainly in the definition of states (configurations) and configuration outputs. The set of states of

P 3 is Q 3 = Q 2 ×Q 2 .
Then, a configuration of P 3 can be viewed as a pair (C * , C) of configurations of P 2 . For every transition (rule) of P 2 , (p, q) → (p ′ , q ′ ), D associates a transition ([

p * p], [q * q]) → ([p p ′ ], [q q ′ ]) of P 3 . Thus, iff C → C ′ in P 2 , then (C * , C) → (C, C ′ ) in P 3 .
In an execution of P 3 , a component C * of a configuration (C * , C) can be viewed as the previous configuration in the corresponding execution of P 2 , and C can be viewed as the actual configuration. The reason of doing that is to be able to locate P 1 -similar configurations in an execution (resulting from the null-transitions in P 2 ) and "eliminate" their output from the output word. Thus, the output of a configuration (C * , C) is defined to be the empty output ϵ, if C * and C are P 1 -similar.

Otherwise, the output of (C * , C) is the output of C in P 2 (which is the output of Π P1 (C) in P 1 , by Property 1). For every initial configuration C 0 of P 2 , (C 0 , C 0 ) is the initial configuration of P 3 .

Theorem 5. Consider a population protocol model allowing empty outputs for configurations. Let P 1 be any non-deterministic population protocol and a protocol P 2 = D ′ (P 1 ) (satisfying Property 1). Let P 3 = D(P 2 ).

Then, L(P 1 ) = L(P 3 ).

We prove the theorem by proving the following two lemmas.

Lemma 2. Consider a population protocol model allowing empty outputs for configurations. Let P 1 be any non-deterministic population protocol. Let P 2 = D ′ (P 1 ) and P 3 = D(P 2 ). Then, the output word of any globally fair execution of P 3 is the output word of a globally fair execution of P 1 (that is, L(P 3 ) ⊆ L(P 1 )).

Proof. Let E be an (infinite) globally fair execution of P 3 and w its output word. In E, we replace any two consecutive configurations (C * , C), (C, C ′ ), by C, C ′ and a starting configuration (C 0 , C 0 ) by C 0 . Then, in the resulting sequence E 2 , we replace any sequence of consecutive similar configurations by the first configuration of the sequence. Let E ′ be the resulting sequence. By the construction of P 3 and the definition of the empty output, the output word of E ′ is w. The projection of E ′ on P 1 is an execution e of P 1 . To prove the lemma we show that e is globally fair for P 1 and thus, its output, which is also w, is an output word of P 1 . Note that by construction of D, E 2 is a globally fair execution of P 2 . Now, consider a configuration c of P 1 appearing infinitely often in e, and assume that there is a configuration c ′ , reachable from c in one step. Since e is the projection of E ′ , there exist in E ′ , and then in E 2 , infinitely many configurations whose projection is c. Since the set of configurations of P 2 is finite, at least one of these configurations, C, appears infinitely often in E 2 . By Property 1, condition 5, there is a configuration C ′ such that C * → C ′ using only P 1 -null-transitions but the last, and such that c ′ = Π P1 (C ′ ). As E 2 is globally fair, the sequence of configurations from C to C ′ , using only null-transitions but the last, appears infinitely often in E 2 . Thus, by construction of e, c ′ appears infinitely often in e. That involves that e is globally fair.

⊓ ⊔ Lemma 2 is sufficient for proving the inclusion of the output languages of P 3 and P 1 , involving that the class of problems solved by non-deterministic and deterministic population protocols is the same (when empty outputs are allowed). For proving the equality of the output languages, we need to prove the converse inclusion.

Lemma 3. Consider a population protocol model allowing empty outputs for configurations. Let P 1 be any non-deterministic population protocol. Let P 2 = D ′ (P 1 ) and P 3 = D(P 2 ). Then, the output word of any globally fair execution of P 1 is the output word of a globally fair execution of P 3 (that is, L(P 1 ) ⊆ L(P 3 )).

Proof. Consider a globally fair execution e 1 = C 0 , C 1 , C 2 , C 3 , . . . of P 1 . First, we build a corresponding globally fair execution e 2 of P 2 . By a simple induction, and using conditions 5 and 3 of Property 1, there is e 2 = C ′ 0 , e ′ 0 , C ′ 1 , e ′ 1 , C ′ 2 , . . . such that ∀i ≥ 0, e ′ i is a finite sequence of P 1 -similar configurations and C ′ i = Π P1 (C i ). As e 1 is globally fair and the states of P 2 are finite, each e ′ i can be chosen such that e 2 is globally fair. Now, we build an execution

e 3 = (C ′ 0 , C ′ 0 )(C ′ 0 , C ′′ 1 )(C ′′ 1 , C ′′ 2 )(C ′′ 2 , C ′′ 3 ) . . . of P 3 such that, ∀i ≥ 2, (C ′′ i-1 , C ′′ i ) → (C ′′ i , C ′′ i+1 ) in e 3 , if C ′′ i → C ′′ i+1 in e 2 .
It is easy to see that if e 2 is globally fair, then e 3 is globally fair. By construction of D, the output word of e 3 is the output word of e 1 . Thus, the lemma holds.

⊓ ⊔ Lemma 4. Given any non-deterministic population protocol P 1 and the transformation D ′ presented in [START_REF] Angluin | Self-stabilizing population protocols[END_REF], D ′ (P 1 ) = P 2 is a deterministic protocol satisfying Property 1.

Proof. All conditions of Property 1, except the last, trivially hold for P 2 , by the construction of D ′ in [START_REF] Angluin | Self-stabilizing population protocols[END_REF]. Condition 5 holds by lemmas 3.1 and 3.2 in [START_REF] Angluin | Self-stabilizing population protocols[END_REF] and the fact that the statements of these lemmas are achieved by executing P 1 -null-transitions only, as it is shown in their proofs. ⊓ ⊔

Results about Inclusion of Output Languages

In this section, we consider the weaker requirement of inclusion for output languages of non/deterministic protocols. As noted in the introduction, [START_REF] Angluin | Self-stabilizing population protocols[END_REF] gives a transformation of any strongly elastic non-deterministic population protocol into a deterministic one, whose output language is included in the output language of the former. Dropping the "elasticity" condition, without introducing empty output values, is difficult (we explain the reason for that in the appendix). One way to solve this difficulty is to use a parameterized transformation, presented in Sec. 4.2 below. In contrast with the transformation of [START_REF] Angluin | Self-stabilizing population protocols[END_REF], it uses non-uniform initial states for agents and depends on the transition graph of a given non-deterministic protocol and on the population.

Another, more natural (and coherent with population protocols) way to obtain inclusion of output languages is, like in Sec. 3.2, to allow interactions with three (or more) agents. The idea is to use the secondary responder with a required switch value to be always able to execute deterministically any possible transition of the non-deterministic transition function. It appears that, when only inclusion is required (in contrast with Sec. 3.2), it is not necessary for the switch values to be initially distinct. Indeed, we provide a protocol (Protocol 1 below) that, starting from a symmetrical initial configuration, distributes the different switch values between the agents. The idea of Prot. 1 is to generalize a (circulating) leader election population protocol proposed in [START_REF] Angluin | Stably computable properties of network graphs[END_REF] to manage several (instead of one) leader marks (which we call here tokens). Note that Prot. 1 cannot be used to obtain equality.

Inclusion with Interactions of More than Two Agents

Thus, we propose a deterministic protocol Prot. 1 that distributes tokens of m (n ≥ m ≥ 1) different types (represented by integers in [1, m]) between n agents. By Lem. 5 proven below, eventually, there is exactly one token of each type and every agent holds at most one token. 8It is assumed that there are at least m agents and that initially, each agent holds one token of each type. Note that these initial states are uniform and the protocol works in any PP k model, for any integer k > 1.

Protocol 1 -to distribute m tokens of different types between n agents

Initialization:

Every agent x has a set Tx = {t1, t2, . . . , tm} of m ≥ 1 different tokens. For every pair of agents x, y, Tx = Ty.

1: when an initiator x interacts with a primary responder y do 2:

if (Tx ∩ Ty) = ∅ ∧ |Tx| = |Ty| then 3:
T ′ ← Tx, Tx ← Ty, Ty ← T ′ // exchange the tokens 4:

// distribute the tokens 5:

if Proof. Let us denote lines 2-3 of the protocol, by action 1; lines 5-8, by action 2; and lines 9-12, by action 3. Note that, according to all the actions, the number of tokens held by an agent is non-increasing. Thus and because of the initial configuration, two interacting agents can have at most two tokens of a similar type (each agent, at most one such token). When two agents, holding tokens of a similar type, interact as initiator and primary responder, action 2 is applied. Then, exactly one of the two tokens of the similar type remains in one of the agents. No action removes a token appearing only in one of the interacting agents. Thus, there is always at least one token of type r, for every type 1 ≤ r ≤ m. Now, assume for the sake of contradiction that there are two tokens of the same type existing during an infinite suffix of some execution. However, by action 1 and the global fairness assumption, eventually, two agents, each having one of these two tokens, interact (as initiator and primary responder), and action 2 is applied. Thus, only one of these tokens remains. Then, if still at least two tokens of the same considered type exist, a similar execution repeats, until only one token of the type remains -a contradiction.

(Tx ∩ Ty) ̸ = ∅ ∧ (T ′ ← (Tx ∩ Ty) = {t ′ 1 , t ′ 2 , . . . , t ′ |T ′ | }) then 6: Ty ← Ty \ {t ′ 1 , t ′ 2 , . . . , t ′ ⌈ |T ′ | 2 ⌉ } 7: if |T ′ > 1| then 8: Tx ← Tx \ {t ′ ⌈ |T ′ | 2 ⌉+1 , . . . , t ′ |T ′ | } 9: if (Tx ∩ Ty) = ∅ ∧ (dif ← |Tx| -|Ty|) > 1 ∧ (Tx = {t x 1 ,
Finally, assume for the sake of contradiction that there is an agent u with at least two tokens in infinitely many configurations. By the paragraph above, eventually, for each type, there is at most one token of the type. Then, first, there are exactly m ≤ n tokens (u holding at least two of them) and thus, there are some agents with no tokens. Second, only action 3 or 1 can be applied. Action 1 can only move these two tokens together from agent to agent. Then, if the tokens are still at one agent, an agent holding them, eventually interacts (by the global fairness) with an agent with no token (they interact as initiator and primary responder) and action 3 is applied. If the two tokens are still at one agent after this interaction (it can happen in case where there are more than two tokens in u), a similar execution repeats until the two are finally "separated" by action 3 -a contradiction.

⊓ ⊔

Now, given a non-deterministic population protocol P 1 in PP 2 (or in PP k , for any integer k > 1), we build a deterministic version P DI of P 1 (given by Protocol 2 below) such that L(P DI) ⊆ L(P 1 ) (see Theorem 6). That is, the deterministic protocol P DI solves the same problems as P 1 . To build P DI, we combine Prot. 1 with protocol P 2 (for PP 3 ), or with its generalization P 3 (for PP k+1 ), constructed in Sec. 3.2. In the following, either of these protocols is denoted by P * . In Sec. 3.2, P * is constructed in such a way that L(P 1 ) = L(P * ). For that, in particular, non-uniform initial states are assumed by the transformations in Sec. 3.2. Here, to achieve only inclusion, we can drop this assumption with the help of Prot. 1.

Thus, the composition P DI is obtained by taking the Cartesian product of the state sets of Prot. 1 and P * , and by updating the states for each protocol independently. The output of a configuration C in P DI is the output of the configuration Π P * (C) in P * .

Protocol 2 P DI -deterministic transformation in PP k+1 with uniform initial states

Initialization:

Initialize the variables of Prot. Proof. In the composition P DI, P * reads the variables of Prot. 1 (the content of the set of tokens T ), on each interaction (lines 5,7, Prot. 2). However, Prot. 1 neither reads, nor writes in the variables of P * . Thus, for P DI, the conditions of a fair composition [START_REF] Herman | Adaptivity through Distributed Convergence[END_REF][START_REF] Tel | Introduction to Distributed Algorithms[END_REF] holds, as well as Lem. 5. Thus and by line 8, eventually, the requirement of P * on the switch values c is satisfied. That is, eventually, each value in [1, m] is the value c of at least one agent. Thus, eventually, Lem. 1 holds for the projection of P DI on P * . Then, by Lem. 1, exactly as in the proof of Theorem 2, one proves that given any globally fair execution e 4 of P DI, Π P1 (e 4 ) is a globally fair execution of P 1 . Then, the output word of e 4 is in the output language of P 1 . ⊓ ⊔

Inclusion with Parameterized Transformation

The phenomenon described in the appendix makes difficult to prove the inclusion result by exhibiting a general transformation, in the original model of population protocols. We even conjecture that such a transformation does not exist. Thus, in this section, we present a parameterized transformation, the parameter depending on the transition graph of the non-deterministic protocol that we want to transform for a given population.

Theorem 7. Given a non-deterministic population protocol P 1 (with a set Q of states) and population  of n agents, there exists a deterministic population protocol P 2 for population  (with a state space of Ω(|Q| 2n ) and using non-uniform initial states) such that L(P 2 ) ⊆ L(P 1 ).

Proof Sketch. Consider the transition graph G(P 1 , Â). Let a traveling salesmen walk, TSW, be a closed path in G(P 1 , Â) that starts from the initial configuration, goes through any possible configuration at least once, and gets back to the same initial configuration. As a first step, we assume that G(P 1 , Â) contains TSW. We consider the other case later. TSW can be viewed as a sequence of transitions denoted S = σ 1 , σ 2 , . . . , σ m . Note that, for each transition in TSW, the pair of interacting agents is defined. The idea is to construct a population protocol P 2 , which is forced to execute a very similar (if, in G, there exist several pathes to reach the same configuration). sequence of transitions S infinitely often.

The state of an agent in P 2 is composed of: a state of P 1 ; the sequence S; a pointer toward one of the transitions in S; and for each transition in S, an order number and an indicator of a role (initiator/responder). An order number can be 0, which means that the agent has not to execute the corresponding transition. If the order number of the pointed transition is i ̸ = 0, then this transition corresponds to the i th transition, σ i = (p, p ′ ) → (q, q ′ ), in S. Moreover, the next transition of the agent (in P 2 ) is of the type ([p i . . .], [p ′ i . . .]) → ([q j . . .], [q ′ k . . .]). This transition can be executed only between two agents in states [p i . . .], [p ′ i . . .] and with appropriate role indicators. After an execution of the transition, the pointer of an agent (participated in the transition) points to the next transition to be executed. This is the next transition in S with a non-zero order number (transition j for initiator, and k for responder, in the example above). The pointer "moves" cyclically in S, ensuring an infinite execution of all the transitions in S.

In the initial configuration of P 2 , all agents are in the initial state p 0 of P 1 , have the same sequence of transitions S, but have different pointers, different order numbers and roles. This non-uniform information can be provided to agents by, e.g., inputs. Note that in every configuration reached by an execution of P 2 , every agent has a unique state and thus, P 2 executes a very similar sequence of transitions in TSW.

It comes directly from the construction that the output word of any globally fair execution of P 2 is the output word of an execution of P 1 . So, it remains to prove that the projection on P 1 of any execution of P 2 is globally fair. That comes from the fact that the projection on P 1 of execution of P 2 reach infinitely often all the configurations in TSW, which are by definition all the infinitely often reachable configurations of P 1 . Now, consider the case where there is no TSW in G(P 1 , Â). As a matter of fact, this case is not very different of the previous one. If there are infinite executions, there necessarily exist a final connected component F (see definition in Sec. 2) which admits a TSW for F . Then, P 2 is built by choosing any path f toward F , and by applying the protocol above for S = f F , when the pointers in agents move on the transitions of f and then cyclically on F .

⊓ ⊔

  . Let C ′ 1 be reachable from C 1 by executing a transition (p, p ′ ) → (p i , p ′ i ), corresponding to the i th choice in δ(p, p ′ ). As C 1 is a projection of C 2 , in C 2 , there are two agents, one in a state [p c p ], and another one in a state [p ′ c p ′ ]. If c p = i, then applying rule ii. of P 2 , in configuration C 2 , gives a configuration C ′ 2 whose projection is C ′ 1 . Otherwise, if c p ′ = i, then, by the construction of P 2 , there are at least two agents with switch value equal to either d + 1 or d + 2. Then, rule iii. can be applied in C 2 , which results in configuration C ′ 2 whose projection is C ′ 1 .In case neither c p , nor c p ′ is equal to i, there is at least one additional agent with a switch value equal to i. Then, rule i. can be applied in C 2 , which results in configuration C ′ To prove the theorem, we first show that given any globally fair execution e 2 of P 2 , its projection e 1 = Π P1 (e 2

	projection is C ′ 1 . Thus, in all cases, C ′ 2 is reachable from C 2 .	2 whose ⊓ ⊔
	Proof (of Theorem 2).

  Eventually, in each configuration reached by an execution of Prot. 1, there is exactly one token of each type and every agent holds at most one token.

		t x 2 , . . . , t x |Tx| }) then
	10:	sizex ← |Tx|, sizey ← |Ty|
	11: 12:	Tx ← {t x 1 , . . . , t x ⌈ dif 2 ⌉+sizey } Ty ← Ty ∪ {t x ⌈ dif 2 ⌉+sizey +1 , . . . , t x sizex }
	Lemma 5.

  1 and the switch variable cx of P * to 1 (cx ← 1, for every agent x ∈ A). Initialize the projection of states of P DI on P * as in P * .

	1: when interaction occurs do
	2:	⟨execute transition of Prot. 1⟩
	3:	⟨execute transition of P * ⟩
	4:	for all agent x in the interaction do
	5:	if |Tx| > 1 then
	6:	cx ← 1
	7:	else if Tx = {ti} then
	8:	cx ← i

Theorem 6. Consider any population  with n ≥ d + k 2 and with complete interaction graph. Let P 1 be a non-deterministic population protocol in PP k (for any integer k > 1) on population Â. Then, the protocol P DI, given by Protocol 2, is the deterministic version of P 1 on  in the model of PP k+1 such that L(P DI) ⊆ L(P 1 ). That is, the deterministic protocol P DI solves the same problems for Â, in PP k+1 , as the non-deterministic protocol P 1 , in PP k .

One can see the terms "problem", "output sequence" and "solving a problem" as equivalent to the terms "behavior", "output trace" and "implementing a behavior", respectively. These terms are used in the literature about population protocols as well (see, e.g.,[START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Fischer | Self-stabilizing leader election in networks of finite-state anonymous agents[END_REF]).

In some unpublished submitted version, one can find only the sketch of proof of the statement. There, the proof uses a transformation technique also used in[START_REF] Angluin | Self-stabilizing population protocols[END_REF] and one can understand how a complete equivalence proof would use this transformation.

Note that this assumption cannot be used to assign identifiers to agents, if n ≫ d + 2. As for population protocols, it is generally assumed that n ≫ |Q|, that implies that n ≫ d + 2. In any case, we show in the sequel (Sec. 4.1) that this assumption can be dropped to obtain a weaker property of inclusion for the output languages.

Note, however, that by changing the model definitions, e.g., for the output words of a protocol, as in Sec. 3.3, it is possible to drop this requirement when still having the equality of output languages for non/deterministic protocols.

. However, when k ≪ d, P3 may be more advantageous. In this case, the state space requirements for the two transformations differ only slightly, though the minimum number of agents required by P ′ 3 may be much larger than the one of P3.

Note that the property given by the lemma does not state that eventually the same token stays with the same agent. On the contrary, the protocol ensures that the tokens are always exchanged between the agents (lines 2-3). This makes the protocol work for populations with interaction graph of any topology.

Acknowledgments. The authors would like to thank the reviewers for their thoughtful comments and suggestions.

A Appendix

Dropping the "Elasticity" Condition is Difficult

We conjecture that a generic transformation giving the output languages inclusion property, applicable to all non-deterministic population protocols, in the original population protocol model, does not exist. We explain the intuition behind this conjecture.

As noted in the introduction, [START_REF] Angluin | Self-stabilizing population protocols[END_REF] gives a transformation of any strongly elastic (defined in the introduction) non-deterministic population protocol into a deterministic one, whose output language is included in the output language of the former. Dropping the "elasticity" condition, without introducing empty output values, is difficult.

Consider a non-elastic non-deterministic population protocol P 1 and assume it is a solution to the same problems as a deterministic population protocol P 2 . That means that the set of output words of P 2 is included in the set of output words of P 1 . As the output values depend on the states of the agents, the states of P 2 are necessarily composite states, with one part in connection with the states of P 1 (ensuring that the output words of P 2 are controlled by P 1 ), and a second part with supplementary information (counter values, work variables, etc.), whose role is to eliminate the non-determinism. However, the difficulty is not in constructing P 2 in such a way that any execution of P 2 has a strong correspondence with an execution of P 1 (for instance, it can be obtained by ensuring the property that the projection of an execution of P 2 is an execution of P 1 ). The problem is that, although the execution of P 2 is globally fair for P 2 , for the correspondence to be meaningful, the corresponding execution of P 1 has to be globally fair for P 1 . Indeed, saying that P 1 solves some problem means that the globally fair executions of P 1 satisfy the specification of the problem, which says nothing about the non-globally fair executions.

To understand why it is not straightforward to overcome the latter problem, consider a configuration C of P 2 , which appears infinitely often in an execution E of P 2 . In the execution e of P 1 corresponding to E, there is a configuration c appearing infinitely often. From c (in P 1 ), all the possibilities given by the non-determinism of P 1 can be used (yielding configurations c 1 , c 2 , . . . , c k ), while from C, the supplementary information (in the state of P 2 ) forces a particular choice, for being deterministic. With null-transitions (yielding "elasticity"), using all the chose possibilities is easy, since the values for the chose counters and other work variables can be modified by a sequence of transitions, which do not change the projection of the configuration on P 1 . However, without null-transitions, the risk is that getting some values for the counters, changes also the projection on P 1 . That is, one could have either the right counter values (corresponding to some choice of a non-deterministic rule), but not c as projection; or c as projection, but not with the right counter values. In this case, a possibility of transition given in P 1 would never be given in P 2 , involving that the projection of a globally fair execution of P 2 on P 1 would not be globally fair for P 1 . Thus, P 2 could not generate the same output words as the globally fair executions of P 1 .


Catherine Delgoulet

Jean-Caude Marquié

Active ageing, development of skills and Long-life Learning at work 1

This paper presents directions worth being explored to improve skill development and long-life learning at work. It also highlights learning specificities of the older workers and difficulties they may encounter in training situations. Measures that come within an ergonomics framework are proposed.

Introduction

The ageing of the work force in most of our societies (Parent-Thirion et al., 2007) has led many European countries to take steps to lengthen occupational life. In France, the activity rate of workers 55 years old and over is one of the lowest in Europe: 39% of them were active in 2009 (INSEE data). Generalizing and intensifying "Lifelong training" appears more and more as a necessary consequence of these changes. It is advantageous not only for employees who are encouraged to greater mobility and polyvalence [START_REF] Gollac | Les conditions de travail[END_REF], but also for unemployed people, as it makes it easier for them to find a job. However, in practice, much is still to be done to fully meet this goal.

In this paper we present a few ideas and facts about how work policies and organization can contribute to promote:

• greater access to training for older workers,

• training methods better suited to the adult's characteristics,

• the integration of continuous learning and long term development opportunities in the job itself.

Promoting greater access to occupational training for older workers

In Europe, especially in France, access to occupational training becomes more difficult with advancing age. This fact is old but still relevant [START_REF] Fournier | Continuing training in the private sector put to the test of age[END_REF]Parent-Thirion et al., 2007). Trying to change it has several implications. It first requires changing representations and throwing off the yoke of negative stereotypes, where they exist, both in employers and in employees themselves. In a European survey on aging workers [START_REF] Walker | The employment of older people: employers' attitudes and practices[END_REF], 43% of employers perceived older workers as having learning difficulties. In other surveys (Le [START_REF] Minez | Les entreprises et le vieillissement de leur personnel : faits et opinions[END_REF]Collis & Mallier, 1999) employers also reported lack of willingness or ability to adjust to changes as being associated to older age. In a more recent survey, Gaudart and Delgoulet (2006) found that workers and unemployed persons over 40 were submitted to a more severe selection and had less access to certifying training and less chance to find a job at the end of the training. In addition to negative stereotypes, the integration of the trainee's experience may be problematic for the training staff. This is the case when the trainee's experience cannot be easily integrated into his/her project or when it is associated with painful experiences, such as unemployment. Some attitudes toward ageing workers can lead them to feel unfit for learning [START_REF] Marquié | Age influence on attitudes of office workers faced with new computerized technologies[END_REF] and to express less needs for future training courses [START_REF] Lainé | Les seniors et la formation continue : un accès en général limité mais avec de grandes différences selon les situations professionnelles[END_REF]. Long-lasting lack of access to training may generate a feeling of being left out. However, there is now a broader social and political consensus than before about the need to increase the frequency and regularity of occupational training opportunities throughout the occupational lifetime (national and European programmes for "life-long learning"). Many psychological and social benefits are expected.

First, this is a condition for maintaining the worker's learning motivation because, as shown by extensive surveys on continuing training carried out in France [START_REF] Fournier | Continuing training in the private sector put to the test of age[END_REF]), the less training the worker has received, the less he/she is willing to be trained, and vice-versa.

Second, increasing the frequency of training is a means of maintaining learning skills. Learning involves specific skills, which can be lost if they are not used. In a field study on age differences in learning railway maintenance skills, we found a significant negative relationship between the time elapsed since the worker's last training experience and the learning performance: the more distant the previous training experience, the poorer the performance [START_REF] Delgoulet | Age differences in learning maintenance skills: a field study[END_REF]. This was even truer for the most abstract part of the tests that assessed learning performance. This suggests that skills involved in generalisation and abstraction are those most affected by disuse. A related issue concerns the relationship between training and overspecialisation at work. Even in highly-qualified working populations, overspecialisation involves several risks with regard to personal and occupational development. For instance, it has been found that compared to younger ones, older pilots from 25 French and foreign airline companies being trained to fly the Airbus A320 on a flight simulator in France (Amalberti, Pèlegrin, & Racca, 1991) exhibited slower progression rates (as assessed by the number of additional training sessions requested), and greater failure rates in the final examination. One interesting result of the study was that the A320 training seems to have been easier for pilots who had moved around in the previous few years. Indeed a positive correlation was found between failure rates in the final examination and time spent on the most recently piloted aircraft model. Note that more frequent moving around between different aircraft models also implies more frequent training opportunities.

A third expected benefit of the increased frequency of the workers' training is that it would allow them to compensate for any initial inequalities in education. Indeed, people with lower academic credentials are also those with the lowest rates of access to training, in both the public and private sectors [START_REF] Perez | Continuing training in the public service[END_REF][START_REF] Fournier | Continuing training in the private sector put to the test of age[END_REF]. Occupational training policies thus maintain initial disparities and may even increase them because of some cumulative processes at work.

Fourth, regular training was reported in earlier work such as that of [START_REF] Davies | Age and work behaviour[END_REF], as counteracting seniority-related obsolescence and preserving performance levels at a relatively greater extent in the older workers.

Promoting training methods better suited to the older and experienced worker's characteristics

Once obstacles preventing senior workers from accessing formal training courses have been overcome, older and experienced workers may still encounter specific learning difficulties in these situations. From studies conducted in real-world training situations and experimental studies carried out in the laboratory, we can extract some recommendations or research directions whenever our knowledge is too scarce.

One important measure for older learners consists in making errors less dramatic for them during the learning process, by convincing them that making errors is necessary to progress. Adopting such a view is less easy for them, as was observed in a real training session on learning how to use a word processor (Baracat & Marquié, 1994). Techniques derived from the Signal Detection Theory were applied to assess the decision criteria used by young and older trainees, when judging and deciding whether procedures that were submitted to them, and which they were expected to execute in a subsequent phase, were right or wrong. The older trainees (age range of participants: 25-55) exhibited stricter decision criteria, especially at the beginning of the training week. This means that they made a higher proportion of omission errors, which revealed a greater reluctance to commit to an action when they were not entirely sure that the proposed procedure was correct. This attitude was interpreted as reflecting a higher level of anxiety in this learning situation compared to the younger trainees, an interpretation whose plausibility was confirmed in subsequent studies. This was observed, for instance, in a four-week training course on accounting and office automation [START_REF] Delgoulet | Training older workers: relationships between age, other trainee characteristics and learning anxiety[END_REF] where the older trainees showed significantly higher anxiety throughout the first three weeks, with learning anxiety being assessed by the Spielberger state anxiety test. The same was observed in a one-week training course for railway operators, who were trained to use magnetoscopic techniques for maintaining bogie trucks [START_REF] Delgoulet | Age differences in learning maintenance skills: a field study[END_REF]. Beyond the fear of errors, learning anxiety may also come from the above-mentioned lack of practice in training settings, from previous unsuccessful training experiences, or from a generational complex, with older people comparing themselves to younger ones who are supposedly or actually better prepared.

There are domains where age is associated with negative stereotypes. In these cases, trainers are therefore required to use compensatory measures to increase or consolidate the older trainee's self-efficacy beliefs. New technologies may be an instance of such a domain, as shown by the results it obtained in experiments using feeling-of-knowing (FOK) tasks [START_REF] Marquié | Age differences in feeling-of-knowing and confidence judgments in two semantic knowledge domains[END_REF]Marquié, Jourdan-Boddaert & Huet, 2001). The FOK is a prospective judgment of one's ability to retrieve a particular piece of information that cannot be brought to consciousness at that moment. For two semantic knowledge domains, general and computerrelated, FOK ratings were recorded in young and older adults, after test difficulty was equated across age groups. The older adults were found to be less confident than the young ones when rating their FOK, but only for computer-related items, not for general knowledge items. Thus, although their actual knowledge in the computer domain (as in the general domain) was exactly the same as the young participants, the older participants significantly underestimated their knowledge only in the domain where negative age-related stereotypes are present. We believe that this type of judgement bias may have deleterious consequences in learning situations, because people do not make an appropriate effort to mobilise the relevant cognitive resources and do not persevere as much if they do not believe that they possess these cognitive resources.

Various types of experience are strongly associated to ageing at work. This includes "technical experience", namely know-how and skills related to specific occupational tasks, but also "job or unemployment experience" and "the experience of one's own ageing". These three dimensions of experience are too often forgotten in the training course design. Formal technical knowledge may be partly taken into account through the prerequisite skills to attend a vocational course, but technical know-how and the other two dimensions of experience are generally little recognized. The message carried by the vocational training system can be summarized this way: "Forget all you have made and learned before", a message that older workers find sometime unacceptable [START_REF] Delgoulet | La construction des liens entre situations de travail et situations d'apprentissage dans la formation professionnelle[END_REF] or take with resignation. Moreover, failing to take into account these cognitive dimensions leads to many troubles in learning situations for older and experienced workers (Gaudart, 2000a;[START_REF] Delgoulet | La construction des liens entre situations de travail et situations d'apprentissage dans la formation professionnelle[END_REF]or

Promoting the integration of continuous learning and sustainable development opportunities in the job itself

Working and learning are too often opposed to each other. Narrowing the links between the two, in the many aspects of the relationship, is a major way of combating qualification obsolescence, and of maintaining and even increasing the worker's cognitive and motivational potential. This implies, first, a work organisation that actually makes room for formally programmed training sessions, such as those devoted to learning new tasks in companies where job rotation is highly encouraged. In organisations under pressure, these in-service training sessions are often the first to be abandoned when time constraints are too great, as reported in field studies by ergonomists (e.g., Gaudard, 2000b). This also implies that the work organisation provides workers with opportunities to experience more or less structured thinking and social exchange about their job practices and working conditions. We have learnt from cognitive psychology that competence does not progress through piling up knowledge, but rather through the close integration of new knowledge within existing knowledge. This is an active, deliberate and effortful process. This also requires a meta-cognitive effort that makes procedural knowledge, which is encapsulated and clearly unconscious, become declarative, namely accessible to consciousness and thus modifiable. Such opportunities are insufficiently provided in the workplace, especially for the older workers [START_REF] Molinié | Age and working conditions in the European Union[END_REF]. Moreover, some current work organisation trends, such as task individualisation, increasing time pressure, and tracking down and chasing idle time lead to the elimination of several of the informal but quite necessary occasions when the worker can perform this "unproceduralisation". Doing such a meta-cognitive job increases awareness of all the accumulated skills. It allows workers to re-appropriate their skills, to improve or consolidate their self-confidence and thus their ability to take up new occupational challenges. It has also been shown that not perceiving one's job as "allowing to learn new things" is associated with a higher probability of "not feeling capable" to stay in one's job until retirement [START_REF] Molinié | Se sentir capable de rester dans son emploi jusqu'à la retraite. Pistes, 7 (1), www.unites.uqam.ca/pistes Parent[END_REF].

Moreover, current literature on the psychology of ageing and work provides more and more evidence that formal and informal learning occasions in and out of work may also contribute to protecting the worker from cognitive ageing, to some extent [START_REF] Schooler | The continuing effects of substantively complex work on the intellectual functioning of older workers[END_REF]. In a recent study this hypothesis was examined by using data from the VISAT (ageing, health and work) longitudinal study [START_REF] Marquié | The VISAT (ageing, health, & work) prospective study: overview and methodology[END_REF]. Data concerned 3 237 workers who were seen three times in a ten-year interval and were between 32 and 62 years old at baseline. Cognitive stimulation received at work was assessed on the first measurement occasion through a score computed from seven items, including:

• occupational training opportunities,

• qualifying aspects of the job, with items referring to the cognitive richness of the work content and to whether the job allowed workers to increase their abilities (e.g., "My job enables me to learn new things"),

• cognitive effort, with items reflecting a more intensive aspect of the work (e.g., "Having to hold a lot of information in memory at the same time").

Cognitive efficiency was assessed three times (at baseline and at the two followups) through episodic verbal memory and processing speed tests. Results showed that greater mental stimulation received at work was associated with higher levels of cognitive functioning, and with a more favorable change over the ten years. These results were obtained after adjustment for age, education, sex, occupational status, intellectual ability, and a variety of other possible confounders. The study thus supports the hypothesis that exposure to jobs that are mentally demanding but offer learning opportunities increases the level of cognitive functioning and possibly attenuates age-related decline (Marquié, Rico Duarte, Bessièress, Dalm, Gentil, & Ruidavets, in press).

Finally, learning situations can be seen from two points of view in the occupational context. Older workers are learners when they face new situations or difficulties in their job, but also when they train colleagues. Because of the demographic trends and the senior employment agreements in France, a new learning dimension has to be considered: the transmission of skills and the tutorial system. The intergenerational transmission of knowledge and know-how is a real opportunity for older workers to be recognized, to share their own knowledge and to learn much through this interaction. However, studies conducted so far [START_REF] Delgoulet | Job entry and on-the-job skills acquisition in the construction sector[END_REF][START_REF] Thébault | Skills transmission between experienced and new hospital workers[END_REF][START_REF] Cloutier | Penetrating professional culture: An essential key for novices for accessing the prudent and professional know-how of experienced film industry workers[END_REF] have revealed several features of the working organization likely to hinder learning and deteriorate working conditions: lack of skilled people in teams, insufficient time to take care of new comers, lack of training of tutorial skills for experienced workers, lack of time formally devoted to transmission, etc.

Conclusion

Long life learning is perfectly feasible, but it takes a "conditional approach" according to working and training conditions [START_REF] Delgoulet | Les « capacités » des travailleurs vieillissants : une approche conditionnelle[END_REF]. Useful information is already available for improving access to training and more suitable training methods for older workers. However, on most of the issues outlined in this paper, much research effort must still be accomplished to better understand measures most likely to develop the worker's technical and nontechnical skills throughout his/her entire occupational life. One major way of achieving this goal is to favour the "learning organisation" [START_REF] Sen | Development as freedom[END_REF], where working and learning are no longer opposed, and where the continuous development of human capabilities is seen as a profitable long-term investment both for the worker and the company. Health has also cognitive components.

Maintaining and increasing competence all over one's occupational life contributes to health preservation. We believe that the ergonomics approach and the "activity" framework [START_REF] Daniellou | Activity-oriented approaches to ergonomics: some traditions and communities[END_REF] may help to identify the best learning conditions, both in formal training courses and at work, that allow older workers to maintain motivation and competence.

  the presentation of Cau-Bareille, et al. at this congress): poor understanding, conflict with trainers, wide gap between actual work activity and the knowledge that it is transmitted in the training course, etc.Training methods little suited to the older trainee's specific characteristics in terms of time pressure, mental overload, especially at the beginning of a training programme, lack of connection with the worker's own experience, etc, are also a cause of lack of motivation for these populations. Many studies (see Paumès Cau-Bareille & Marquié, 1998 for a literature review) have shown that the older trainees succeed when learning conditions are well suited.