Joroy Beauquier
email: beauquier@lri.fr

Peva Blanchard
email: peva.blanchard@epfl.ch

Janna Burman
email: burman@lri.fr

Oksana Denysyuk

On the Power of Oracle Ω? for Self-Stabilizing Leader Election in Population Protocols

Keywords: networks of mobile agents, population protocols, self-stabilization, leader election, oracles

This paper considers the fundamental problem of self-stabilizing leader election (SSLE) in the model of population protocols. In this model an unknown number of asynchronous, anonymous and nite state mobile agents interact in pairs. SSLE has been shown to be impossible in this model without additional assumptions. This impossibility can be circumvented for instance by augmenting the system with an oracle (an external module providing supplementary information useful to solve a problem). Fischer and Jiang have proposed solutions to SSLE, for complete communication graphs and rings, using the oracle Ω?, called the eventual leader detector. In this paper, we investigate the power of Ω? on larger families of graphs. We present two important results. Our rst result states that Ω? is powerful enough to allow solving SSLE over arbitrary communication graphs of bounded degree. Our second result states that, Ω? is the weakest (in the sense of Chandra, Hadzilacos and Toueg) for solving SSLE over rings. We also prove that this result does not extend to all graphs; in particular not to the family of arbitrary graphs of bounded degree.

Introduction

There are fundamental problems in distributed computing that are subject to impossibility results. The impossibility can be related to the system asynchrony, limited resources, the presence of failures, their type, or other general conditions. For instance, the consensus problem has been shown to be impossible in asynchronous systems even with only one crash fault [START_REF] Fischer | Impossibility of consensus with one faulty process[END_REF]. An elegant approach for circumventing the impossibility of consensus is the abstraction known as failure detectors introduced by Chandra and Toueg [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. A failure detector can be viewed as an oracle, which provides to the system nodes a supplementary information about failures allowing to solve a given problem. A fundamental issue is to determine the oracle providing the minimum amount of information for solving the problem. Among the dierent failure detectors proposed to solve consensus in the conventional asynchronous communication model, the eventual leader elector Ω, has been proven to be the weakest [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF]. Informally, that means that it supplies the minimum supplementary information necessary to obtain a solution.

In this work, we consider a very basic communication model called population protocols. It has been introduced as a model for large networks of tiny, anonymous and asynchronous mobile agents communicating in pairs [START_REF] Angluin | Computation in networks of passively mobile nite-state sensors[END_REF]. The network has an unbounded but nite population of agents, each with only O(1) states, implying that the size of the population is unknown to the agents. With such minimal assumptions, the impossibility results are not a surprise. For example, consensus is impossible in such a model even without any crash failure [START_REF] Beauquier | The weakest oracle for symmetric consensus in population protocols[END_REF]. Another impossibility concerns a problem called self-stabilizing leader election (SSLE), which consists in electing a leader (a distinguishable agent) in a self-stabilizing way. Self-stabilization [START_REF] Dijkstra | Self-stabilizing systems in spite of distributed control[END_REF] is a framework for dealing with transient state-corrupting faults and can be viewed as allowing the system to start from an arbitrary conguration. In this work, we focus on this fundamental problem SSLE that is shown to be impossible in many dierent cases [START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF][START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF].

The eventual leader elector Ω of Chandra and Toueg and other classical failure detectors cannot be used with population protocols, because they assume that the network nodes have unique identiers, unavailable to anonymous bounded state agents in population protocols. Many other previous oracles, like those proposed for anonymous models (e.g., [START_REF] Bonnet | Anonymous asynchronous systems: The case of failure detectors[END_REF]), cannot be used in population protocols either, e.g., because they assume nite, but unbounded memory depending on the size of the network (see a survey in [START_REF] Beauquier | The weakest oracle for symmetric consensus in population protocols[END_REF]).

To deal with this issue, Fischer and Jiang introduced a new type of oracle, called the eventual leader detector [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF] and denoted by Ω?. Instead of electing a leader, like Ω, Ω? simply reports to each agent an (eventually correct) estimate about whether or not one or more leaders are present in the network (see Sec. 2 and 3.2 for a formal denition). This oracle does not require unique identiers and has additional drastic dierences. One of the important dierences is motivated by the self-stabilizing nature of the SSLE problem considered in [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF]. While Ω is designed to circumvent impossibility related to crash faults, Ω? is designed to deal with state-corrupting faults. Thus, while Ω is related to a failure pattern and is independent of the protocol using it, Ω? interacts with the protocol, providing information related to the system congurations reached during the execution. With Ω?, there is some sort of feedback loop: the outputs of the oracle inuence the protocol; and conversely, the protocol inuences the outputs of the oracle. Yet, there are some features in common with Ω. Both Ω and Ω? are unreliable in the sense that Ω? can make errors, that is, to give false information at some point and at some agents, and is only required to eventually provide correct answers, similarly to Ω. Finally, such weak guarantees allow both Ω and Ω? to be implemented in practice using timeouts and other features often found in real systems (more details about the implementation of Ω? can be found in [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF]; about Ω, in [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]).

To demonstrate the power of Ω?, [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF] gives a uniform solution to SSLE using Ω? in complete communication graphs and rings. Uniform means that the solution is independent of the actual communication graph; the agents only know the graph family to which the graph belongs. Our focus here is on uniform solutions too. [START_REF] Angluin | Computation in networks of passively mobile nite-state sensors[END_REF] Contribution. In this work, we investigate the power of Ω?. In particular, in Sec. [START_REF] Angluin | Self-stabilizing population protocols[END_REF], we show that its power exceeds considerably the case of rings and complete graphs (concerned in [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF]). In fact, Ω? is sucient for solving SSLE on almost all graphs, the only restriction being that the graph must be connected (obvious) and of bounded degree (related to the model requirement of bounded agent states).

In Sec. 5, we show that SSLE allows to implement Ω? on rings. Coupled with the fact that Ω? is sucient for solving SSLE on rings [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF], this implies that any oracle strong enough for solving SSLE on rings can be used to implement Ω? (on rings); i.e. Ω? is the weakest oracle for solving SSLE on rings.

In contrast with the previous case, we also show that over arbitrary communication graphs of bounded degree (and more generally, over non-simple graph families), SSLE is not equivalent to Ω? (Th. 2). Intuitively, our results mean that, whereas SSLE and Ω? are not equivalent over certain families of graphs, this dierence disappears on rings due to the strong communication constraints imposed by this topology.

For modeling oracles and problems, and obtaining relations between them, we use the formal framework proposed in [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF] and adapted to population protocols (see Sec.

2.2)

. In this framework, there is no dierence between an oracle and a problem, so the relations that we exhibit can equivalently be viewed as relations between oracles or between problems. Note that the framework and our results concern an extremely general class of oracles. Related Work. Being an important primitive in distributed computing, leader election has been extensively studied in various other models, however much less in population protocols. Because of model dierences, previous results do not directly extend to the model considered here. For surveys on these previous results in other models, refer to [START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF]. In the following, we mention only the most relevant works to SSLE in population protocols.

It was shown, e.g. in [START_REF] Angluin | Fast computation by population protocols with a leader[END_REF][START_REF] Beauquier | On utilizing speed in networks of mobile agents[END_REF], that fast converging population protocols can be designed using an initially provided unique leader. Moreover, many self-stabilizing problems on population protocols become possible given a leader (though together with some additional assumptions, see, e.g., [START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Beauquier | Self-stabilizing synchronization in mobile sensor networks with covering[END_REF]). Nevertheless, SSLE is impossible in population protocols over general connected communication graphs [START_REF] Angluin | Self-stabilizing population protocols[END_REF]. Yet, [START_REF] Angluin | Self-stabilizing population protocols[END_REF] presents a non-uniform solution for SSLE on rings. A uniform algorithm for rings and complete graphs is proposed in [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF], but uses Ω?. Recently, [START_REF] Cai | How to prove impossibility under global fairness: On space complexity of self-stabilizing leader election on a population protocol model[END_REF] showed that at least n agent states are necessary and sucient to solve SSLE over a complete communication graph, where n is the population size (unavailable in population protocols). For the enhanced model of mediated population protocols (M P P ) [START_REF] Michail | Mediated population protocols[END_REF], it is shown in [START_REF] Mizoguchi | On space complexity of selfstabilizing leader election in mediated population protocol[END_REF] that (2/3)n agent states and a single bit memory on every agent pair are sucient to solve SSLE. It is also shown that there is no M P P that solves SSLE with constant agent's state and agent pair's memory size, for arbitrary n. In [START_REF] Canepa | Self-stabilizing tiny interaction protocols[END_REF], versions of SSLE are considered assuming Ω? together with dierent types of local fairness conditions. In the current paper, we consider only global fairness (classical for population protocols).

In [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF], it is shown that the diculty in solving SSLE in population protocols comes from the requirement of self-stabilization. Indeed, [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF] presents a solution for arbitrary graphs with a uniform initialization without any oracle. Then, [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF] proposes also a solution for SSLE over arbitrary graphs, but the protocol uses a much stronger oracle. This oracle can be viewed as a composition of two copies of Ω?, where one copy is used to control the number of (stationary) leaders and another one to control the number of moving tokens. There, tokens are used for eliminating supplementary leaders. In this paper, we prove that, surprisingly enough, there is no need to control the number of tokens and that a single instance of Ω? is enough (at least, in the case of bounded degree graphs). Finally, [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF] shows that SSLE and Ω? are not equivalent over complete communication graphs. Here, we extend this result to so called nonsimple families of graphs (Th. 2).

Model and Denitions

Population Protocol

We use here the denitions of [START_REF] Angluin | Computation in networks of passively mobile nite-state sensors[END_REF][START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF] with some slight adaptations. A communication graph is a directed graph G = (V, E) with n vertices. Each vertex represents a nitestate sensing device called an agent, and an edge (u, v) indicates the possibility of a communication (interaction) between u and v in which u is the initiator and v is the responder. The orientation of an edge corresponds to this asymmetry in the communications. In this paper, every graph is weakly connected.

A population protocol A(Q, X, Y, Out, δ) consists of a nite state space Q, a nite input alphabet X, a nite output alphabet Y , an output function Out : Q → Y and a transition function δ : (Q × X) 2 → P(Q 2 ) that maps any tuple (q 1 , x 1 , q 2 , x 2 ) to a non-empty (nite) subset δ(q 1 , x 1 , q 2 , x 2 ) in Q 2 . 1 A (transition) rule of the protocol is a tuple (q 1 , x 1 , q 2 , x 2 , q 1 , q 2 ) s.t. (q 1 , q 2 ) ∈ δ(q 1 , x 1 , q 2 , x 2 ) and is denoted by (q 1 , x 1 )(q 2 , x 2 ) → (q 1 , q 2 ). The protocol A is deterministic if for every tuple (q 1 , x 1 , q 2 , x 2 ), the set δ(q 1 , x 1 , q 2 , x 2 ) has exactly one element.

A conguration is a mapping C : V → Q specifying the states of the agents in the graph, and an input assignment is a mapping α : V → X specifying the input values of the agents. An input trace T is an innite sequence T = α 1 α 2 . . . of input assignments. It is constant if α 1 = α 2 = . . . . An input trace can be viewed as the sequence of input values given to the agents from the outside environment.

We now dene agents' interactions (called here actions) involving the input values. An action is a pair σ = (e, r) where r is a rule (q 1 , x 1 )(q 2 , x 2 ) → (q 1 , q 2 ) 1 The input alphabet can be viewed as the set of possible values given to the agents from the outside environment, like sensed values, output values from another protocol or from an oracle. The output alphabet can be viewed as the set of values that the protocol itself outputs outside. X and Y are both the interface values of the protocol.

and e = (u, v) is a directed edge of G, representing a meeting of two interacting agents u and v. Let C, C be congurations, α be an input assignment, and u, v be distinct agents. We say that σ is enabled in

(C, α) if C(u) = q 1 , C(v) = q 2 and α(u) = x 1 , α(v) = x 2 . We say that (C, α) goes to C via σ, denoted (C, α) σ -→ C , if σ is enabled in (C, α), C (u) = q 1 , C (v) = q 2 and C (w) = C(w) for all w ∈ V -{u, v}.
In other words, C is the conguration that results from C by applying the transition rule r to the pair e of two interacting agents. We write (C, α) → C when (C, α)

σ -→ C
for some action σ. Given an input trace

T in = α 0 α 1 . . . , we write C * -→ C if there is a sequence of congurations C 0 C 1 . . . C k s.t. C = C 0 , C = C k and (C i , α i ) → C i+1 ,
for all 0 ≤ i < k, and we say that C is reachable from C given the input trace T in .

An execution is a sequence of congurations, input assignments and actions

(C 0 , α 0 , σ 0 ) (C 1 , α 1 , σ 1 ) . . . such that for each i, (C i , α i ) σi -→ C i+1 .
In addition, the sequence satises global fairness if, for every C, C , α s.t. (C, α) → C , if (C, α) = (C i , α i ) for innitely many i, then C = C j for innitely many j. This denition together with the nite state space assumption, implies that, if in an execution there is an innitely often reachable conguration, then it is innitely often reached [START_REF] Angluin | The computational power of population protocols[END_REF].

Global fairness can be viewed as an attempt to capture the randomization inherent to real systems, without introducing randomization in the model.

E = (C 0 , α 0 , σ 0 )(C 1 , α 1 , σ 1 ) . . . is given by the sequence T out = Out(C 0 )Out(C 1 ) . . . .
In the sequel, we use the word trace for both input and output traces.

Behaviour, Oracle, Problem and Implementation

The denitions below are adopted from [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF] and dierent from the ones in [START_REF] Angluin | Self-stabilizing population protocols[END_REF][START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF].

They are required to obtain a proper framework for dening oracles and establishing relations between them and/or between problems.

1 In particular, this framework is real time independent, which in turn provides self-implementable oracles, in contrast with the traditional failure detectors [START_REF] Charron-Bost | In search of lost time[END_REF][START_REF] Cornejo | Asynchronous failure detectors[END_REF]. In short, in this framework, we dene a general notion of behaviour, which is a relation between input and output traces.

A problem and an oracle are dened as behaviours. Then, to compare behaviours, we dene a partial order relation using an abstract notion of implementation by a population protocol using a behaviour.

In the following, a communication graph G is supposed to be xed and is sometimes implicitly referenced.

A schedule is a sequence of edges (representing meetings). An input or an output trace T = α 0 α 1 . . . is said to be compatible with the schedule S = (u 0 , v 0 )(u 1 , v 1 ) . . . if, for every meeting i, for every agent w dierent from u i and v i , α i (w) = α i+1 (w).

That is, any two consecutive assignments of a compatible trace can dier only on the values of the two meeting (neigboring) agents. This denition is natural since an agent can only be activated during a meeting, and it makes no sense to allow a 1 In [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF], where Ω? has been introduced, the oracle is dened in a rather informal way. change in inputs which cannot be detected by the agents. Note also that the output trace (associated with an execution with a schedule S) is necessarily compatible with S by denition.

A history H is a couple (S, T ) where S is a schedule and T is a trace compatible with S. Depending on the type of trace, a history can be either an input or an output history. A behaviour B over a family of graphs F is a function that, for a graph G ∈ F and a schedule S on G, maps every input history H in with schedule S to a set B(G, H in ), or simply B(H in ), of output histories with the same schedule S.

The output histories of B(H in ) are the legal output histories of B given H in .

In a natural way, behaviours can be composed in series, parallel, or by selfloop. For instance, in the serial composition, an output trace of a behaviour is the input trace of another one. Formally, consider two behaviours B 1 , B 2 over the same family F of graphs, with input alphabets X 1 , X 2 (for the input traces), and output alphabets Y 1 , Y 2 (for the output traces). In the following, T Z denotes a trace with values in Z.

Let S be a schedule on

G ∈ F. If Y 1 = X 2 = Z, the serial composition B = B 2 • B 1 is the behaviour over F, with alphabets X 1 , Y 2 s.t. (S, T Y2 ) ∈ B(S, T X1 ) i there exists a trace T Z compatible with S, s.t. (S, T Z ) ∈ B 1 (S, T X1 ) and (S, T Y2 ) ∈ B 2 (S, T Z ).
The parallel composition B = B 1 ⊗ B 2 is the behaviour over F, with alphabets

X 1 × X 2 , Y 1 × Y 2 s.t. (S, T Y1 , T Y2 ) ∈ B(S, T X1 , T X2 ) i (S, T Y1 ) ∈ B 1 (S, T X1 ) and (S, T Y2 ) ∈ B 2 (S, T X2 ).
If X 1 = U ×V and Y 1 = U ×W , the self-loop composition B = Self U (B 1 ) on U is the behaviour over F, with alphabets V, W , s.t. (S, T W ) ∈ B(S, T V ) i there exists a trace T U compatible with S s.t. (S, T U , T W ) ∈ B 1 (S, T U , T V ). As already mentioned, the self-loop composition is necessary to describe the interactions between a protocol and an oracle.

Given a (possibly innite) set U of behaviours, a composition of behaviours in U is dened inductively as either a behaviour in the family U, or the parallel, serial or self-loop composition of compositions of behaviours in U.

The behaviour B 2 is called a sub-behaviour of B 1 if they are dened over the same family of graphs F, and for every graph G ∈ F, for every history

H on G, B 2 (G, H) ⊆ B 1 (G, H).
Given a population protocol A with input alphabet X and output alphabet Y , the behaviour Beh(A) associated to the protocol A is the behaviour with input alphabet We say that a behaviour B 1 is weaker than a behaviour B 2 over a graph family F, denoted by B 1 F B 2 , if there exists a self-stabilizing1 population protocol that implements B 1 using B 2 over F. The two behaviours are equivalent over F, denoted

X, output alphabet Y s.t. (S, T Y ) ∈ Beh(A)(S, T X ) i
B 1 F B 2 , if B 1 F B 2 and B 2 F B 1 .
In the case where B 2 is a problem and B 1 is an oracle, B 1 is the weakest oracle for implementing B 2 over F. The reason is that, because B 1 F B 2 , any oracle that can be used to implement B 2 , can be used to implement B 1 , and thus, B 1 is weaker than any such oracle.

3 Specic Behaviours

Eventual Leader Election Behaviour ELE

ELE is dened with the input alphabet {⊥} (i.e., no input) and the output alphabet {0, 1} such that, given a graph G and a schedule S on G, a history (S, T ) ∈ ELE(S) if and only if the output trace T has a constant sux T = ααα . . . and there exists an agent λ such that α(λ) = 1 and α(u) = 0 for every u = λ. In other words, λ is the unique leader. Notice that for all our protocols, there is an implicit output map that maps a state to 1 if it is a leader state, and to 0 otherwise.

In our framework, the problem of Self-Stabilizing Leader Election (SSLE) consists in dening a population protocol that solves ELE using another behaviour (if necessary) and starting from arbitrary initial congurations.

Oracle Ω?

Informally, Ω? (introduced in [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF]) reports to agents whether or not one or more leaders are present. Thus, it does not distinguish between the presence of one or more leaders in a conguration (of a protocol composed with Ω?).

Formally, Ω? is simply a relation between input and output traces with binary values. The input and output alphabets are {0, 1}. Given an assignment α, we denote by l(α) the number of agents that are assigned the value 1 by α. Given a graph G and a schedule S on G, (S, T out ) ∈ Ω?(S, T in ) if and only if the following conditions hold for input and output traces T in and T out . If T in has a sux α 0 α 1 . . . such that ∀i, l(α i ) = 0, then T out has a sux during which at each output assignment at least one agent is assigned 0. If T in has a sux α 0 α 1 . . . such that ∀s, l(α s ) ≥ 1, then T out has a sux equal to the constant trace where each agent is permanently assigned the value 1. Otherwise, any T out is in Ω?(S, T in ).

Ω? is easy to implement in practice, provided that timeouts are available. Each leader periodically broadcasts a "leader signal". Each agent resets the timer when it receives the signal. If the timeout expires, the agent sets a ag to false, signaling the absence of leader. The ag is reset to true when a "leader signal" is received. In a chaotic environment in which communications are bad or nodes are malfunctioning, the implemented oracle can give incorrect answers, making the system unstable. But, eventually, after the environment has regain its consistency, Ω? will give a correct information and the system will stabilize.

4 SSLE using Ω? over Graphs with Bounded Degree

In this section, we show that, for any given integer d, the behaviour ELE can be implemented in a self-stabilizing way using Ω? over the family of weakly connected graphs with a degree bounded above by d. Precisely, we present a population protocol A d and prove that the behaviour given by the composition Self (Beh(A d ) • Ω?)

is a sub-behaviour of ELE. We rst give a solution over the family of strongly connected graphs with bounded degree. The transformation of this solution into one over weakly connected graphs with bounded degree is formally presented in the appendix (Sec. A.2, Th. B). We rst briey recall how the Fischer and Jiang's protocol for rings [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF] works.

As said before, the information given by Ω? does not allow to distinguish between the presence of a single or more leaders. Thus, a leader should try to eliminate other leaders, while avoiding a scenario where all leaders are eliminated innitely often (without any help from the oracle). On a ring, a strategy performing this goal is relatively simple to install. Leaders send tokens, circulating on the ring in one direction and send also shields, circulating in the opposite direction. Shields absorb tokens when they meet, but a leader that receives a token is eliminated. When there remains a single leader, it sends a token and a shield (in opposite directions) and the ring structure ensures that the token cannot avoid the shield, so that a unique leader cannot eliminate itself.

The situation is completely dierent on arbitrary graphs, since tokens and shields can take dierent routes. This requires a completely dierent management for a single leader not eliminating itself. As the agents are nite-state, a bounded degree is needed for implementing such a management.

For distinguishing between the dierent possible routes, each agent has to give dierent (local) names to its neighbors. For that, we use the 2-hop coloring selfstabilizing population protocol, denoted by 2HC, proposed in [START_REF] Angluin | Self-stabilizing population protocols[END_REF]. A 2-hop coloring is a coloring such that all neighbours of the same agent have distinct colors. We denote by Colors the corresponding set (of size O(d 2 )) of possible colors.

The input variables (read-only) of our protocol A d at each agent x are: the oracle output Ω? x (values in {0, 1}); and the agent color c x (values in Colors), which stores the output of 2HC. The working variables are: the leader bit leader x (values {0, 1}); the token vector token x (vector with values in {0, 1} indexed by Colors); and the shield vector shield x (vector with values in {0, 1} indexed by Colors).

The idea of the protocol is the following. An agent may hold several shields (resp. tokens), each of them waiting to be forwarded to an out-neighbour, from initiator to responder, with associated color, lines 14 18 (resp. in-neighbour, from responder to initiator, lines 7 12). The information required for implementing this is encoded in the shield and token vectors. The purpose of the tokens is to eliminate leaders (line 10), whereas the purpose of the shields is to protect them by absorbing tokens (line 17). A leader is created when the oracle reports that there are no leaders in the system (lines 2, 3). When a leader is created, it comes with (loads) a shield for every color (line 5), and thus is protected from any token that could come from one of its out-neighbors. To maintain the protection, each time an agent receives a shield from its in-neighbor, it reloads shields for every color (line 16). Dually, any time an agent receives a token, it reloads tokens for every color (line 11). In addition, whenever a leader interacts as an initiator, it loads tokens for every color (line 22). Before proving the correctness of the algorithm, we introduce some denitions. A path in G is a sequence of agents π = x 0 . . . x r such that (x i , x i+1 ) is a directed edge of G. If x 0 = x r , π is a loop at x 0 . If u is an agent that appears in π, we denote it by u ∈ π, and by ind π (u) the index of the rst occurrence of u in π, i.e. the minimum

Algorithm 1: Protocol

A d -initiator x, responder y 1 (Create a leader at x, if needed) 2 if Ω?x = 0 then 3 leaderx ← 1 4 ∀c ∈ Colors, tokenx[c] ← 1 5 ∀c ∈ Colors, shieldx[c] ←
i such that x i = u. If (x, y
) is an edge of G, we say that x has a shield against y if shield x [c y ] = 1. Similarly, we say that y has a token against

x if token y [c x ] = 1.
The crucial idea of the proof relies on the notion of protected leader. Intuitively, a leader λ is protected if, in any loop at λ, some agent (the protector) protects λ thanks to a shield against its successor, and no agent between λ and the protector has a token against its predecessor.

Denition 1 (Protected Leader). Consider a loop π = x 0 . . . x r+1 at a leader λ (= x 0 = x r+1 ). We say that λ is a leader protected in π if there exists i ∈ {0, . . . , r} such that x i has a shield against x i+1 and, if i ≥ 1, x i is not a leader and has no token against x i-1 . In addition, for every j ∈ {1, . . . , i -1}, x j is not a leader, has no shield against x j+1 and no token against x j-1 . The agent x i is the protector of λ in π; the path x 0 . . . x i is the protected zone in π. The agent λ is a protected leader if it is protected in every loop at λ.

Note that a new leader or a leader that receives a shield becomes protected by loading shields for every color.

Given an execution E, S E denotes the maximum (innite) sux of E such that each couple (C, α) (C being a conguration, and α an input assignment) in S E occurs innitely often. IRC E denotes the (nite) set of congurations occurring in S E , i.e., the set of congurations that occur innitely often in E. The following lemma constitutes the core of our argument. We give a detailed proof.

Lemma 1. If C ∈ IRC E has a protected leader, then every conguration in IRC E has a protected leader.

Proof. Consider a couple (C, α) that occurs in S E , C being a conguration (in IRC E ) and α an input assignment. The assumption on the protocol 2HC states that α yields a correct 2-hop coloring. Consider a conguration C that follows the occurrence of (C, α) in S E . In particular, (C, α) → C . We note (x, y) be the pair of edges involved (initiator x, responder y).

When a leader is created, it is already protected by itself since it has a shield against every of its out-neighbors. We thus focus on transition rules that do not involve the creation of a leader. Hence, such a transition may eliminate a leader, or move or create shields and tokens.

Let λ be a protected leader in γ and π be any loop at λ. Let µ be the protector of λ in π. If x and y do not appear in the protected zone in π, then after the transition, the states of the agents in the protected zone have not changed and λ is still protected in π. Then, assume that x or y appear in the protected zone. Let z ∈ {x, y} be the agent with the lowest index ind π (z). The previous assumption implies ind π (z) ≤ ind π (µ).

Consider rst the case ind π (z) < ind π (µ). If z = x, then z cannot receive a token (from y), i.e., either x has a shield against y or y has no token against x. Otherwise, the path that goes from λ to (the rst occurrence of ) z = x followed by any path that goes from y to λ yields a loop within which λ is not in protected in C; hence a contradiction. Hence, if z = x, after the transition, λ is still protected by µ in π. Now, if z = y, y may only receive a shield, and thus, after the transition, λ is still protected in π (by µ or y).

Now, assume that ind π (z) = ind π (µ). This implies that z = µ ∈ {x, y}, and that every agent in the protected zone, except µ, is dierent from x and y. If µ = y, then during the transition, µ may only receive a shield (which merges with its shield); hence, λ is still protected by µ in π after the transition. We now focus on the case µ = x. First consider the subcase where y is not the agent that follows the rst occurrence of µ in π. Then µ cannot receive a token during the transition, otherwise, the same argument as above shows the existence of a loop at λ within which λ is not protected in C. After the transition, (the rst occurrence of ) µ still has a shield against the agent right after it, which proves that λ is still protected in π. Consider now the subcase where y is the agent that follows the rst occurrence of µ in π. If y is not a leader, then after the transition, y becomes the new protector of λ in π. If y is a leader, then after the transition, λ is no longer protected, but y is protected since the reception of a shield produces shields for every color. In both cases, after the transition, there is a protected leader in C .

We thus have shown that, in every case, C contains a protected leader. Given any conguration C ∈ IRC E , there must be a sequence of actions from (C, α) to (C , α ) during S E , for some input assignment α . Since C has a protected leader, the previous argument shows that every conguration in this sequence has a protected leader, in particular C . Therefore, any conguration in IRC E has a protected leader.

Lemma 2. All congurations in IRC E have the same number l ≥ 1 of leaders. In addition, no conguration in IRC E contains an unprotected leader.

Proof (Sketch). Full details are presented in the appendix, Sec. A. there is either no leader, then at some point, Ω? will force the creation of a (protected) leader. If there is always at least one leader, but they are all unprotected, then it means that innitely often there is a possibility to kill a leader. Global fairness ensures that all the unprotected leaders will eventually be eliminated, which is a contradiction. In all cases, it means that every conguration in IRC E contains at least one protected leader. In particular, Ω? will not create new leaders. This implies that, once all unprotected leaders have been killed, there is a constant number of protected leaders.

Theorem 1. The protocol A d solves the problem ELE using Ω? (i.e., Ω? ELE) over strongly connected graphs with degree less than or equal to d.

Proof (Sketch). See the appendix, Sec. A for full details. Any conguration in IRC E has the same number l ≥ 1 of (protected) leaders. Assume that l ≥ 2, consider two protected leaders λ 1 , λ 2 and the loop π built from the shortest path from λ 1 to λ 2 followed by the one from λ 2 to λ 1 . By moving the protector of λ 1 behind λ 2 , and making λ 2 res a token, it is possible to eliminate λ 1 . The global fairness ensures that this eventually happens, which reduces the number l; hence a contradiction. Thus, there is eventually a unique leader. [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF] Is Ω? the Weakest Oracle for Solving SSLE?

Now, we come to the second important result of this paper. The search for weakest oracles, since the weakest failure detector of Chandra and Toueg, has been a constant quest in distributed computing. The weakest oracle, for solving a problem elsewhere impossible, represents the minimum supplementary information needed.

As this supplementary information can be provided naturally by the environment, its determination is of great interest for implementing a solution. Our approach here is dierent from the approach of failure detectors, in the sense that the oracles we consider are in a larger class. Indeed, failure detectors only observe a pattern of failures, whereas oracles like Ω? are able to react to the output of the protocol. We would like to emphasize the fact that, for dealing with transient failures (state corruptions) an oracle must have access to the states of the agents. It is not a choice that we make, but a necessity. In such a general setting, the issue of the weakest oracle is reduced to the issue of the equivalence of such an oracle with the problem itself. In consequence, we have to prove that SSLE allows to implement this oracle.

We answer this issue relatively to dierent communication topologies.

An Impossibility Result for Non-Simple Families of Graphs

It turns out that for some graph families, a negative answer (Th. 2) holds. A somewhat similar result, for the case of complete graphs, has been presented in our previous work [START_REF] Beauquier | Self-stabilizing leader election in population protocols over arbitrary communication graphs[END_REF]. Here we present a more general result that applies to innite families of graphs, called here non-simple (like in [START_REF] Angluin | Self-stabilizing population protocols[END_REF]). A family F is non-simple if there exists a graph G ∈ F, and two disjoint subgraphs

G 1 , G 2 of G such that G 1 , G 2 ∈ F.
Complete and arbitrary graphs of bounded degree are some examples of non-simple families of graphs. In contrast, notable simple families of graphs include rings, or, more generally, connected d-regular graphs.

The following theorem states the impossibility of a self-stabilizing implementation of Ω? using ELE over any non-simple family of graphs. Coupled with the result of Sec. 4, i.e. Ω? ELE over connected arbitrary graphs of bounded degree, we have Ω? ELE over the same graph family. Similarly, Ω? is not the weakest oracle for SSLE over complete graphs, and, by the SSLE protocol of [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF], we have Ω? ELE over complete graphs. The proof of Theorem 2 uses a classical partitioning argument and appears in the appendix (Sec. B).

Theorem 2. For any non-simple family of graphs F, there is no self-stabilizing population protocol A implementing Ω? over F using the behaviour ELE (i.e., there is no composition B = Beh(A) • ELE ⊆ Ω?). In particular, Ω? ELE over complete graphs and over arbitrary connected graphs of bounded degree.

Ω? is the weakest oracle for SSLE over rings

Now, we show that Ω? can be implemented in a self-stabilizing way given the behaviour ELE over oriented rings. Note that this is not about detecting the agent selected by ELE (which would be trivial). Instead, we dene a protocol which uses the eventual presence of a distinguishable agent (guaranteed by ELE), hereafter called the master, to detect the presence or absence of leaders in the input trace. This implementation is given by the RingDetector protocol presented below (see Algorithm 2). This result is straightforward to extend to non-oriented rings thanks to the self-stabilizing ring orientation protocol presented in [START_REF] Angluin | Self-stabilizing population protocols[END_REF]. The meaning of this result, coupled with the result of Sec. 4, is that Ω? rings ELE, when self-stabilization is concerned; i.e., Ω? is the weakest oracle for solving SSLE over rings.

Implementing Ω? by the RingDetector protocol using ELE (Alg. 2)

The input variables (read-only) at each agent x are: the master bit master x (values in {0, 1}) that keeps the output of ELE; and the leader bit leader x (values in {0, 1}), which represents the input of Ω?. The working variables are: the probe eld probe x (with values: ⊥ -no probe, or 0 -white probe, or 1 -black probe); the token eld (with values: ⊥ -no token, or 0 -white token, or 1 -black token); the ag bit f lag x (with values: 0 -cleared, 1 -raised); and the output bit (values in {0, 1}), which represents the corresponding output of Ω?.

Each time an agent has its leader bit set to 1, it raises its ag (and the ag of the other agent in the interaction) line 5. A token moves clockwise, and its purpose is to detect a leader (actually, a raised ag) and to report it to the master (lines 18 26). A probe moves counter-clockwise, and its purpose is to report to the master the lack of tokens (lines 7 13). The master loads a white probe each time it is the responder of an interaction (line 2). When a probe meets a token, the probe becomes black (line 10). When two probes meet, they merge into a black probe if one of them was black, and into a white probe otherwise (line 12). The master loads a token colored with its ag only when it receives a white probe (line 17). Each time a token meets an agent with its ag raised, the token becomes black (line 21) and the ag is cleared (line 25). Two meeting tokens merge into a black token if one of them is black, and into a white token otherwise (line 23). When the master receives a token, it whitens the token, and it outputs 0 if the token is white, and 1 otherwise (lines 28 31). In any interaction, the responder copies the output of the initiator, unless the responder is the master (line 33).

Correctness

We use the same notations S E and IRC E as in the previous section. By the definition of ELE, a unique agent eventually becomes the master permanently. We focus on the corresponding sux of the execution (S E is included in this sux). Furthermore, we denote by C(x).token (resp. C(x).probe, etc.) the value of the variable token (probe, etc.) in the conguration C at agent x. Similarly, we denote by α(x).leader (resp. α(x).master) the value of the variable leader (resp. master) in the input assignment α at x. The following lemma states that, eventually, a unique token circulates in the ring. Lemma 3. In any conguration C ∈ IRC E , there is exactly one token (white or black) in C, i.e., there exists a unique agent x such that C(x).token = ⊥.

Proof (Sketch). If there are no tokens, some probe sent by the master will return to the master with the color white (recall that the probes and tokens move in opposite directions). This causes the master to re a token. Two colliding tokens merge into one. This implies that there will always be at least one token. In particular, all the probes sent by the master will return to the master with the color black; thus no more tokens are created. Moreover, thanks to the global fairness, if there are several tokens, they eventually all merge into a unique token. This unique circulating token (from the lemma above) allows to divide the execution into rounds. We dene a round to be a segment of S E that begins with the token loaded at the master, and ends up right before the token returns to the master.

The following lemma describes the output of the master at the end of each round. tokeny ← 0 32 (a non-master responder copies the output of the initiator) 33 if mastery = 0 then outy ← outx Lemma 4. Consider a round R in S E . We denote by (C 0 , α 0 ) . . . (C r , α r ) the corresponding sequence of congurations and input assignments. Case (a) If there are no leaders during R, i.e., for every 0 ≤ i ≤ r, and every agent x, we have α i (x).leader = 0, then after the last action of the round, all the agents have their ags cleared (set to zero). Case (b) If there are no leaders during R, and if all the agents have their ags cleared at the beginning of the round, then after the last action of the round, the master outputs 0 and all the agents have their ags cleared. Case (c) If there is at least one leader in each assignment during R, i.e., for every 0 ≤ i ≤ r, there is some agent x i such that α i (x i ).leader = 1, then after the last action of the round, the master outputs 1.

Proof (Sketch). We only prove here the case (c). Full proof details are presented in the appendix, Sec. B. Assume that there is a leader in each input assignment. Let µ be an agent that holds a leader in assignment α 0 , i.e., α 0 (µ).leader = 1. During the round, there must be some i, such that µ = v i is the responder and the initiator u i holds the token. If µ holds a leader in assignment α i , then after the transition, the token must have turned black. If µ does not hold a leader in assignment α i , since µ did hold a leader in assignment α 0 , there must be some j < i such that α j (µ).leader = 1 and α j+1 (µ).leader = 0. Now, since the input trace is compatible with the schedule, µ must be the initiator u j or the responder v j in the transition (C j , α j ) → C j+1 . Hence, µ must raise its ag, i.e., we have C j+1 (µ).f lag = 1 (j + 1 ≤ i). Recall that there is a unique token, so the ag cannot be cleared during the remaining actions until i. Hence, at i, the token turns black when the token moves from the initiator u i to the responder v i = µ. In all cases, the master receives a black token at the end of the round, and thus outputs 1.

Theorem 3. The protocol RingDetector is a self-stabilizing implementation of Ω? using ELE (i.e., ELE Ω?) over oriented rings. Moreover, Ω? rings ELE (by [START_REF] Fischer | Self-stabilizing leader election in networks of nite-state anonymous agents[END_REF]), and thus Ω? is the weakest oracle for solving ELE over rings.

Proof (Sketch). See the appendix, Sec. B, Th. D, for full details.We divide the execution in rounds as dened above. If there are no leader forever, then Lemma 4 ensures that after a nite number of rounds, the master permanently outputs 0. If there is a leader in each input assignment, then Lemma 4 ensures that after a nite number of rounds, the master permanently outputs 1. In both cases, the propagation of the master's output ensures that the output trace of the protocol satises the oracle Ω? conditions (see Sec. 3.2 for its denition). transition, the states of the agents in the protected zone have not changed and λ is still protected in π. Then, assume that x or y appear in the protected zone. Let z ∈ {x, y} be the agent with lowest index ind π (z). The previous assumption implies ind π (z) ≤ ind π (µ).

Consider rst the case ind π (z) < ind π (µ). If z = x, then z cannot receive a token (from y), i.e., either x has a shield against y or y has no tokens against x. Otherwise, the path that goes from λ to (the rst occurrence of ) z = x followed by any path that goes from y to λ yields a loop within which λ is not in protected in C; hence a contradiction. Hence, if z = x, after the transition, λ is still protected by µ in π. Now, if z = y, y may only receive a shield, and thus, after the transition, λ is still protected in π (by µ or y).

Now, assume that ind π (z) = ind π (µ). This implies that z = µ ∈ {x, y}, and that every agent in the protected zone, except µ, is dierent from x and y. If µ = y, then during the transition, µ may only receive a shield (which merges with its shield); hence, λ is still protected by µ in π after the transition. We now focus on the case µ = x. First consider the subcase where y is not the agent that follows the rst occurrence of µ in π. Then µ cannot receive a token during the transition, otherwise, the same argument as above shows the existence of a loop at λ within which λ is not protected in C. After the transition, (the rst occurrence of ) µ still has a shield against the agent right after it, which proves that λ is still protected in π. Consider now the subcase where y is the agent that follows the rst occurrence of µ in π. If y is not a leader, then after the transition, y becomes the new protector of λ in π. If y is a leader, then after the transition, λ is no longer protected, but y is protected since the reception of a shield produces shields for every color. In both cases, after the transition, there is a protected leader in C .

We thus have shown that, in every cases, C contains a protected leader. Given any conguration C ∈ IRC E , there must be a sequence of actions from (C, α) to (C , α ) during S E , for some input assignment α . Since C has a protected leader, the previous argument shows that every conguration in this sequence has a protected leader, in particular C . Therefore, any conguration in IRC E has a protected leader.

Lemma B If no conguration in IRC E has a leader, then all input assignments in S E equal an input assignment that assigns 0 to every variable Ω? x and yields a 2-hop coloring. If every conguration in IRC E has a leader, then all input assignments in S E equal an input assignment that assigns 1 to every variable Ω? x and yields a 2-hop coloring.

Proof. This stems from the denition of Ω? and the assumption on 2HC.

Lemma C Every conguration in IRC E has at least one leader, and every input assignment in S E is equal to an input assignment α E that assigns 1 to every variable Ω? x and yields a 2-hop coloring.

Proof. Assume that some conguration C in IRC E lacks a leader. On the one hand, if no conguration in IRC E has a leader, then by Lemma B, every input assignment in S E assigns 0 to every Ω? x . Hence, in S E , during every transition, a protected leader is created. On the other hand, if IRC E contains a conguration C with a leader, then there is a sequence of actions from (C, α) to (C , α ) for some input assignments α, α , since both C and C occur innitely often in S E . According to the protocol, during one of the actions, a protected leader must be created. In both cases, we have a conguration C ∈ IRC E with a protected leader. By Lemma A, this implies that all congurations in IRC E has a protected leader, in particular C; hence a contradiction. Thus any conguration in IRC E has a leader. The assumption on the protocol 2HC and Lemma B yield the last claim.

Lemma D All congurations in IRC E have the same number of leaders.

Proof. By Lemma C, every input assignment in S E assigns 1 to every variable Ω? x .

Thus no leader is created during S E . Assume there exists two congurations C, C in IRC E such that the number l of leaders in C is dierent from the number l of leaders in C . Without loss of generality, we can assume l < l . By denition, there must be a sequence of actions in S E from (C, α) to (C , α ) for some input assignments α, α . The fact that l < l implies that during this sequence a leader is created; hence a contradiction.

Lemma E No conguration in IRC E contains an unprotected leader.

Proof. Suppose that C ∈ IRC E contains an unprotected leader λ. By Lemma C, there is an input assignment α E such that (C, α E ) occurs in S E and α E assigns 1 to every variable Ω? x . We describe a sequence of actions with the input assignment α E at each step. Since λ is not protected in C, there exists a path π = x 0 . . . x r from agent x 0 = λ to some agent x r such that for every 0 ≤ i < r, agent x i has no shield against x i+1 and x r either is a leader or has a token against x r-1 . If x r is a leader, any transition where x r is a initiator makes x r creating a token against x r-1 . Then by moving (backward) the token along this path, it is possible to kill the non-protected leader λ. We reach a conguration C within which λ is not a leader. Since no leaders have been created during the sequence, C has fewer leaders than C. The global fairness ensures that C ∈ IRC E ; this contradicts Lemma D.

Theorem A The protocol A d solves the problem ELE using Ω? over strongly connected graphs with degree less than or equal to d.

Proof. By Lemma D and E, we know that any conguration in IRC E has the same number l of protected leaders and no unprotected leaders; and also that all input assignments are equal to some α E that gives a 2-hop coloring and assigns the value 1 to every variable Ω? x . Lemma C ensures that l ≥ 1. Assume, by contradiction, that l ≥ 2. Let C ∈ IRC E . Let λ 1 , λ 2 be two protected leaders in C. Consider p 1 (resp. p 2 ) the shortest path from λ 1 to λ 2 (resp. from λ 2 to λ 1 ). We dene the loop π 1 = p 1 p 2 at λ 1 and the loop π 2 = p 2 p 1 at λ 2 . We note µ 1 (resp. µ 2 ) the protector λ 1 (resp. λ 2 ) in π 1 (resp. π 2 ). Necessarily, the rst occurrence of µ 1 (resp. µ 2 ) is in p 1 (resp. p 2 ). We describe a sequence with input assignment α E at every step. The protocol allows to move the (rst occurrence of the) protector µ 1 right before λ 2 . Another such action makes the protector transfer its shield to λ 2 , thus turning λ 1 into a non-protected leader (λ 2 is still a protected leader). Then λ 2 can re a token that kills λ 1 . Since, no leader is created during the sequence, we reach a conguration C with less than l leaders. The global fairness ensures that C ∈ IRC E . This contradicts Lemma D. Therefore, all congurations in IRC E have a unique leader. Since the leaders cannot move, there is a permanent leader.

A.2 From Strongly to Weakly Connected Graphs

Now we show that the results above can be extended to the more general family of weakly connected graphs with bounded degree. We actually exhibit a slightly more general transformation.

First, we give some specic denitions. Given an edge e = (x, y) of a graph G, we denote by ē = (y, x) the opposite edge (not necessarily an edge of G). The symmetric closure of a graph G, is the graph G sym with the same set of vertices obtained from G by adding the opposite edges. Consider a family F of graphs closed by symmetric closure, G ∈ F ⇒ G sym ∈ F, and let B be a behaviour over F. We say that B is undirected when, for any graph G ∈ F, for any schedule S = e 1 e 2 . . . on G, (S, T out ) ∈ B(G, S, T in ) if and only if (S , T out ) ∈ B(G sym , S , T in ) for any schedule S = e 1 e 2 . . . on G sym such that e i ∈ {e i , ēi }. Intuitively, a behaviour is undirected if the legal output histories do not depend on the orientation of the edges of G.

Theorem B Consider a graph family F 0 , and let F be the family of graphs G such that G sym ∈ F 0 . The family F is closed by symmetric closure. Let B, O be undirected behaviours over F such that there exists a population protocol A implementing B using O over the family F 0 . Then there exists a population protocol A (given in the proof) implementing B using O over the family F.

Proof. We give a constructive proof. We show how to transform A into a population protocol A . Given A, we dene below a (possibly) non-deterministic protocol A N D .

It can be transformed into a deterministic one using the transformer proposed in [START_REF] Angluin | Self-stabilizing population protocols[END_REF], provided that the behaviour B is an elastic behaviour (see [START_REF] Angluin | Self-stabilizing population protocols[END_REF] for more details).

A N D has the same state space, inputs and outputs as A, and the following transition rules. The rule (p, x)(q, y) → (p , q ) is a rule of A N D if and only if (p, x)(q, y) → (p , q ) is a rule of A or (q, y)(p, x) → (q , p ) is a rule of A. For instance, if A has a unique rule (p, x)(q, y) → (p , q ), then A N D has two rules, (p, x)(q, y) → (p , q ) and (q, y)(p, x) → (q , p ). In this example A N D is deterministic but it would not be the case if A had also a rule (q, y)(p, x) → (q , p ).

Intuitively, A N D , executing over a graph G ∈ F, simulates A over the symmetric closure G sym ∈ F 0 . Alternatively, it is as if A N D simulated a scheduler, over a non directed graph induced by G, which could choose at every interaction which agent is the initiator, and which is the responder.

We claim that, if E = (C 0 , α 0 , σ 0 )(C 1 , α 1 , σ 1 ) . . . is a globally fair execution of A N D on G, then there is a sequence of actions σ i , i ∈ N, such that the sequence E = (C 0 , α 0 , σ 0 )(C 1 , α 1 , σ 1 ) . . . is a globally fair execution of A on G sym . Hence, since A solves B over G sym using the oracle O, the protocol A N D solves B over G using the same oracle O. The corresponding sequence of actions σ i is dened as follows. If σ i = (u i , v i , (q, y)(p, x) → (q , p )) but (q, y)(p, x) → (p , q ) is not a rule of A, then dene σ i = (v i , u i , (p, x)(q, y) → (p , q )). If (q, y)(p, x) → (q , p ) is a rule of A, then dene σ i = σ i .

Note that the fact that B and O are undirected ensures that the input history of E on G sym is a legal output history of O on G sym , and the output history associated with E is a legal history of B.

Taking F 0 to be the family of strongly connected graphs (in and out) degree bounded by 2d, F becomes the family of weakly connected graphs with (in and out) degree bounded by d. The previous theorem yields the following corollary: Corollary 1. The protocol A 2d can be transformed in a protocol A d which solves ELE using Ω? over the family of weakly connected graphs with (in and out) degree bounded by d.

B Is Ω? the Weakest for Solving SSLE?

Theorem C For any non-simple family of graphs F, there is no self-stabilizing population protocol A implementing Ω? over F using the behaviour ELE (i.e., there is no composition B = Beh(A) • ELE ⊆ Ω?).

Proof. We prove the result by contradiction using a classical partitioning argument.

Assume such a protocol A and consider a graph G from a given non-simple family F, such that there are two disjoint subgraphs of G, G 1 and G 2 that are also in F.

Every execution E of A has an input trace (T, T in ), where T is an output trace of ELE and T in represents the input trace of Ω?. Given a schedule S on G, (S, T out ) ∈ B(S, T, T in ) such that T out is an output trace of A (corresponding to the one of Ω?) induced by S.

By the denition of ELE, each T eventually permanently assigns 1 to a unique agent λ and 0 to every other; we denote by β this assignment. W.l.o.g., assume that λ ∈ G 1 . We choose the trace T in to be the constant trace αα . . . where α assigns 1 to some agent µ ∈ G 2 , and 0 to every other.

By the assumption on A, the output trace T out has a sux equal to the constant trace assigning 1 to every agent. Thus, for every couple (C, γ) in S E , γ = (β, α) and the output associated to C assigns 1 to every agent. If we restrict (C, γ) to the graph G 1 , we obtain a conguration and input assignment (C 1 , γ 1 ). The agent λ is still the unique agent to be assigned 1 by β 1 , and α 1 assigns 0 to every agents in G 1 . Since the protocol must be self-stabilizing, and since G 1 ∈ F, there is a sequence of actions, involving all the agents of G 1 and having the input assignment γ 1 during the sequence. This leads to a conguration C 1 that outputs 0 at at least one agent in G 1 . This involves that there is a sequence of execution (C, γ)(C 1 , γ)(C 2 , γ) . . . (C , γ) such that C outputs 1 at the agents of G 2 and 0 at some agent in G 1 . The global fairness ensures that C occurs in S E ; hence a contradiction. Now, we prove that RingDetector is a self-stabilizing implementation of Ω? using ELE. We use the same notations S E and IRC E as in the previous section. In addition, the input trace T = α 0 α 1 . . . of the execution E is assumed to provide a unique master, i.e., there exists a unique agent λ in E such that α i (λ).master = 1 for all i. By the denition of ELE and RingDetector, such an input trace exists in an innite sux of every E of RingDetector. For the correctness proof, we focus only on such suxes, for every execution.

Lemma F In any conguration C ∈ IRC E , there is exactly one token (white or black) in C, i.e., there exists a unique agent x such that C(x).token = ⊥.

Proof. Consider a conguration C ∈ IRC E . We rst prove that C contains at least one token. On the contrary, assume that, for every agent x, C(x).token = ⊥. The following scenario will produce a token. First, let the master λ interacting as a responder to produce a white probe at λ. Then, move (counter-clockwise) all the other probes, if any, to the master. Then move the white probe at λ so as to visit all the agents and return to λ again. Since there are no tokens in the graph, the white probe will not turn black. Then, the white probe arriving at λ will make λ produce a token. This scenario does not depend on the possibly present leaders. Hence, we have shown that there exists a conguration C with at least one token such that C * -→ C , whatever the input trace is during this sequence. By global fairness, we know that C belongs to IRC E . But, the rules of the protocol are such that, once there is at least one token in the graph, there is always at least one token in the graph in any subsequent conguration. Thus C cannot occur innitely often; hence a contradiction. Hence C has at least one token.

Assume now that C has at least two tokens. Since two meeting tokens merge into one token, there is a conguration C with exactly one token such that C * -→ C , whatever the input trace is. By global fairness, C belongs to IRC E . Since C also occurs innitely often in the execution, and since the only way to create a token is by having the master receive a white probe, this means that the master receives innitely many white probes during S E . But once there is a token in the graph, since the tokens move clockwise and the probes counter-clockwise, any probe arriving at the master must be black; hence a contradiction. Therefore, C has exactly one token.

Thanks to the previous lemma, we know that during S E a unique token circulates clockwise. We dene a round to be a segment of S E that begins with the token loaded at the master, and ends up right before the token returns to the master.

Lemma G Consider a round R in S E . We denote by (C 0 , α 0 ) . . . (C r , α r ) the corresponding sequence of congurations and input assignments. Case (a) If there are no leaders during R, i.e., for every 0 ≤ i ≤ r, and every agent x, we have α i (x).leader = 0, then after the last action of the round, all the agents have their ags cleared (set to zero). Case (b) If there are no leaders during R, and if all the agents have their ags cleared at the beginning of the round, then after the last action of the round, the master outputs 0 and all the agents have their ags cleared. Case (c) If there is at least one leader in each assignment during R, i.e., for every 0 ≤ i ≤ r, there is some agent x i such that α i (x i ).leader = 1, then after the last action of the round, the master outputs 1.

Proof. Case (a). Assume there are no leaders in the round. Since the token moves clockwise from the master to the master, and since a token clears any ag it encounters, after the last action in the round, the token must have cleared all the possible raised ags in the ring.

Case (b). Assume that there are no leaders in the round, and that all the ags are clear at the beginning. During the rst action, the master holds the token and colors it in white (the master holds no leader). Since there are no leaders in the round, in every conguration within the round, all the ags are cleared. Hence, when moving clockwise from the master to the master, the token meets no raised ags and stays white. At the end of the round, the master receives a white token and outputs 0.

Case (c). Assume that there is a leader in each input assignment. Let µ be an agent that holds a leader in assignment α 0 , i.e., α 0 (µ).leader = 1. During the round, there must be some i, such that µ = v i is the responder and the initiator u i holds the token. If µ holds a leader in assignment α i , then after the transition, the token must have turned black. If µ does not hold a leader in assignment α i , since µ did hold a leader in assignment α 0 , there must be some j < i such that α j (µ).leader = 1 and α j+1 (µ).leader = 0. Now, since the input trace is compatible with the schedule, µ must be the initiator u j or the responder v j in the transition (C j , α j ) → C j+1 . Hence, µ must raise its ag, i.e., we have C j+1 (µ).f lag = 1 (j + 1 ≤ i). Recall that there is a unique token, so the ag cannot be cleared during the remaining actions until i. Hence, at i, the token turns black when the token moves from the initiator u i to the responder v i = µ. In all cases, the master receives a black token at the end of the round, and thus outputs 1.

Theorem D The protocol RingDetector is a self-stabilizing implementation of Ω? using ELE over oriented rings.

Proof. Consider a globally fair execution E and focus on the sux S E . For the sake of simplicity, we assume that there is a unique master from the beginning. By Lemma F, we know that in S E there is a unique token moving clockwise. Without loss of generality, we assume that S E begins with the token being hold by the master. We then write S E = R 1 R 2 . . . where each R i is a round.

Consider rst the case where the input trace T = α 0 α 1 . . . in S E permanently assigns no leaders everywhere, i.e., for all i, for every agent x, α i (x).leader = 0. By Lemma G, we know that at the end of R 1 , all the ags are cleared. Hence, at the end of R 2 , the master outputs 0 and all the ags are cleared. By iteration, at the end of each round R i , i ≥ 2, the master outputs 0. Since the master updates its output only when it receives the token, and since this happens exactly at the end of a round, we know that in the sux R 2 R 3 . . . , the master permanently outputs 0. The fact that the responder always copies the output of the initiator (unless the responder is the master) implies that there is a sux during which all the agents permanently output 0.

Assume now that the input trace is such that there is at least one leader in each input assignment. By Lemma G, at the end of each round R i , the master outputs 1.

The same argument as above shows that there is a sux of execution during which all the agents permanently output 1.

Note that, in the remaining cases of input traces in S E , that is when there are some input assignments with a leader and some other without, nothing has to be proven, because then, the output of Ω? is arbitrary (see denition in Sec. 3.2).

Remark 1. Note that as leaders can appear and then disappear completely, one require a kind of recurring procedure verifying if leaders have reappeared. The permanent master guaranteed by ELE plays the role of an arbiter initiating this recurring procedure by sending the exploring tokens. Tokens look for on ags and switch them o, to be prepared for the next exploration tour. One may think that there is a simpler solution using no probes. That is, a solution, where, e.g., master sends the tokens repeatedly after some bounded number of interactions it participates in, otherwise exploring token may never exist or be created. However, such a solution without probes might be incorrect. To see this, consider an input trace where there is one leader in every input assignment, but this leader moves repeatedly clockwise, jumping" from initiator to responder on the oriented ring. By the denition of Ω?, in this scenario, the master should eventually and permanently output 1. However, it is innitely often possible that there are two tokens (generated by the master)

directly following the leader one after the other, during the whole tour, from the master to the master. In this case, the rst token arriving at the master is black, but the following token is white. This is because the rst token has cleared every ag raised by the leader. The repetition of this scenario causes an oscillation of the master's output between 0 and 1.

  The output function Out : Q → Y is extended from states to congurations and produces an output assignment Out(C) : V → Y dened as Out(C)(v) = Out(C(v)), given a conguration C. The output trace associated to the execution

  there exists an execution of A with schedule S, input trace T X and output trace T Y . A problem and an oracle are simply dened as behaviours. Now, we are ready to dene what it means for a protocol A to implement a behaviour (or solve the problem) B using an oracle O. The population protocol A implements the behaviour B (or solves the problem B) using the behaviour O if there exists a composition B * involving the behaviours O and Beh(A), s.t. B * is a sub-behaviour of B.

Fig. 1 .

 1 Fig. 1. Serial composition Beh(A d ) • Ω? followed by a self-loop composition.

Algorithm 2 :

 2 Protocol RingDetector -initiator x, responder y

	1 (if the master is the responder, it creates	17 if masterx = 1 and probex = 0 then
		a white probe)		tokenx ← f lagx
	2 if mastery = 1 then probey ← 0	18 (move token from x to y)
	3		19 if tokenx = ⊥ then
	4 (raise ags if needed)	20	(the token becomes black when meeting
	5 if leaderx ∨ leadery then		a ag)
		f lagx ← f lagy ← 1	21	if f lagy = 1 then tokeny ← 1
	6		22	(otherwise, keeps the same color or
	7 (move probe from y to x)		merges)
	8 if probey = ⊥ then	23	else if tokeny ∈ {⊥, 0} then
	9	(the probe becomes black when		tokeny ← tokenx
		meeting a token)	24	(the ag is cleared)
	10	if tokenx = ⊥ then probex ← 1	25	f lagy ← 0
	11	otherwise, keeps the same color or	26	tokenx ← ⊥
		merges)	27 end
	12	else if probex ∈ {⊥, 0} then	28 (if the master receives a token, it changes
		probex ← probey		its output and whitens the token)
	13	probey ← ⊥	29 if mastery = 1 and tokeny = ⊥ then
	14 end	30	outy ← tokeny
	15		31
	16 (if the master receives a white probe, it
		loads a token)

This is in contrast to the non-uniform solutions given to SSLE over rings in[START_REF] Angluin | Self-stabilizing population protocols[END_REF] that does not use oracles.

In this paper, we are only interested in comparing oracles as far as self-stabilization is concerned.

Joroy Beauquier, Peva Blanchard, Janna Burman, and Oksana Denysyuk

Appendix

A ELE using Ω? over Weakly Connected Graphs with Bounded Degree

A.1 Solution over strongly connected graphs Consider a strongly connected graph G of degree (in and out degree together) less than or equal to d. For the sake of clarity, in any execution we consider, we assume that the protocol 2HC permanently outputs a correct 2-hop coloring from the beginning (variables c x , for every agent x).

We use the following notations in the sequel. Given an execution E, S E denotes the maximum (innite) sux of E such that each couple (C, α) (C being a conguration, and α an input assignment) in S E occurs innitely often. IRC E denotes the (nite) set of congurations occurring in S E , i.e., the set of congurations that occur innitely often in E.

Lemma A If C ∈ IRC E has a protected leader, then every conguration in IRC E has a protected leader.

Proof. Consider a couple (C, α) that occurs in S E , C being a conguration (in IRC E ) and α an input assignment. The assumption on the protocol 2HC states that α yields a correct 2-hop coloring. Consider a conguration C that follows the occurrence of (C, α) in S E . In particular, (C, α) → C . We note (x, y) be the pair of edges involved (initiator x, responder y).

When a leader is created, it is already protected by itself since it has a shield against every of its out-neighbors. We thus focus on transition rule that do not involve the creation of a leader. Hence, such a transition may kill a leader, or move or create shields and tokens.

Let λ be a protected leader in γ and π be any loop at λ. Let µ be the protector of λ in π. If x and y do not appear in the protected zone in π, then after the