Karine Altisen
email: karine.altisen@univ-grenoble-alpes.fr

Ajoy K Datta
email: ajoy.datta@unlv.edu

Stéphane Devismes
email: stephane.devismes@univ-grenoble-alpes.fr

Anaïs Durand
email: anais.durand@univ-grenoble-alpes.fr

Lawrence L Larmore
email: lawrence.larmore@unlv.edu

Election in unidirectional rings with homonyms

Keywords: Leader Election, Homonyms, Multiplicity, Unidirectional Rings

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

We consider the leader election problem, which consists in distinguishing a unique process of the network. This task is fundamental in distributed systems since it is a basic component in many protocols, e.g., spanning tree construction, broadcasting and convergecasting methods. Leader election is especially helpful to achieve synchronization and self-organization in a network. For example, in a wireless ad-hoc network (WSN), collected data are most of the time aggregated at a leader node, called the sink, which can be a gateway between the WSN and other kind of networks.

Leader election is essential, yet sometimes hard to solve, e.g., in 1980, Angluin [START_REF] Angluin | Local and global properties in networks of processors[END_REF] showed the impossibility of solving deterministic leader election in networks of anonymous processes. This negative result led to two major opposite lines of research. The first approach circumvents the impossibility result by using randomization to break symmetries [START_REF] Xu | Self-stabilizing anonymous leader election in a tree[END_REF]. In the second one, networks are assumed to be equipped with unique process identifiers to eliminate symmetries which allowed the design of deterministic algorithms [START_REF] Lynch | Distributed Algorithms[END_REF]. The notion of homonym processes has been introduced as an intermediate model between the (fully) anonymous and (fully) identified ones. In this model, each process has an identifier, called here label, which may not be unique. Let L be the set of labels present in a system of n processes. Then, |L| = 1 (resp., |L| = n) corresponds to the fully anonymous (resp., fully identified) model. This natural extension is motivated by the fact that assuming every process has unique identifier is sometimes too strong in practice. For example, process identifiers often come from MAC addresses and some of these addresses may be duplicated. As a matter of facts, in systems such as Chord [START_REF] Stoica | Chord: a scalable peer-to-peer lookup protocol for internet applications[END_REF] or Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF], addresses are the result of hash functions that are subject to collisions. Moreover, in many cases, system users may wish to preserve some kind of privacy. However, in fully anonymous systems where no identifiers are used, very few problems (including leader election) are deterministically solvable [START_REF] Angluin | Local and global properties in networks of processors[END_REF]6,[START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF][START_REF] Buhrman | On the importance of having an identity or, is consensus really universal?[END_REF]. Consequently, homonymy is an alternative solution to implement trustworthy level of privacy using, for example, group or ring signatures [START_REF] Chaum | Group signatures[END_REF][START_REF] Rivest | How to leak a secret[END_REF], where signatures are labels and each process of a group share the same signature to anonymously sign messages on behalf of the group. Notice that homonymy using group or ring signatures already have many applications, e.g., in e-voting [START_REF] Pan | Re-note: An e-voting scheme based on ring signature and clash attack protection[END_REF], e-cash [12], and blockchains [13].

Finally, ring topologies, studied here, are the most natural candidates among classical topologies for proof of concept before considering arbitrary ones since they are sparsely connected. Moreover, paying attention to ring networks makes sense from a practical point of view as some real world systems are based on a ring topology, e.g., the token ring standard for local area networks. Ring topologies are also used in P2P systems [START_REF] Shaker | Self-stabilizing structured ring topology p2p systems[END_REF][START_REF] Forestiero | Description of the self-chord P2P application[END_REF]. For example, Self-Chord [START_REF] Forestiero | Description of the self-chord P2P application[END_REF] decouples object keys from peer IDs and sorts keys along a ring. Related Work. Several recent works [START_REF] Yamashita | Electing a leader when processor identity numbers are not distinct (extended abstract)[END_REF][START_REF] Flocchini | Sorting and election in anonymous asynchronous rings[END_REF][START_REF] Dobrev | Leader election in rings with nonunique labels[END_REF][START_REF] Chalopin | Election in partially anonymous networks with arbitrary knowledge in message passing systems[END_REF][START_REF] Delporte-Gallet | Leader election in rings with homonyms[END_REF][START_REF] Dereniowski | Topology recognition and leader election in colored networks[END_REF] studied the leader election problem in networks with homonym processes. Yamashita and Kameda study in [START_REF] Yamashita | Electing a leader when processor identity numbers are not distinct (extended abstract)[END_REF] the feasibility of leader election in networks of arbitrary topology containing homonym processes. They propose a process-terminating (i.e., every process eventually halts) leader election assuming that processes know the size of the network. In [START_REF] Chalopin | Election in partially anonymous networks with arbitrary knowledge in message passing systems[END_REF], Chalopin et al. characterize families of (labeled) graphs which admit a process-terminating election algorithm using the notion of quasi-coverings.

In [START_REF] Flocchini | Sorting and election in anonymous asynchronous rings[END_REF], Flocchini et al. study the weak leader election problem in bidirectional ring networks of homonym processes. In this problem, one or two processes are chosen as leaders. In this latter case, the two elected processes must be neighbors. Under the assumption that processes know a priori the number of processes, n, they show that the process-terminating weak leader election is possible if and only if the labeling of the ring is asymmetric, i.e., there is no non-trivial rotational symmetry (i.e., non multiple of n) of the labels resulting in the same labeling. They also propose two process-terminating weak leader election algorithms for asymmetric labeled rings of n processes, assuming that n is prime and that there are only two different labels, 0 and 1. The first algorithm assumes a common sense of direction, i.e., every process is able to distinguish between its clockwise and counterclockwise neighbors. The second algorithm is a generalization of the first one, where the common sense of direction is removed. No time complexity is given for the second algorithm.

In [START_REF] Delporte-Gallet | Leader election in rings with homonyms[END_REF], Delporte et al. consider the leader election problem in bidirectional ring networks of homonym processes. They propose a necessary and sufficient condition on the number of distinct labels needed to solve the leader election problem. More precisely, they prove that there exists a solution to message-terminating (i.e., processes do not halt but only a finite number of messages are exchanged) leader election problem in bidirectional rings if and only if the number of labels is strictly greater than the greatest proper divisor of n. Assuming that condition, they give two algorithms. The first one is message-terminating and does not assume any extra knowledge. On the contrary, the second algorithm is process-terminating but assumes the knowledge of n. They show that their second algorithm is asymptotically optimal in messages (O(n log n)). In [START_REF] Dobrev | Leader election in rings with nonunique labels[END_REF], Dobrev and Pelc study a generalization of the process-terminating leader election problem in both unidirectional and bidirectional networks of homonym processes. They assume that processes know a priori a lower bound m and an upper bound M on the (unknown) number of processes, n. They propose algorithms that decide whether the election is possible and perform it, if so. They propose two synchronous algorithms, one for bidirectional and one for unidirectional rings, and both use O(M ) time and O(n log n) messages. They also propose an asynchronous algorithm for bidirectional rings using O(nM ) messages and prove its optimality. No time complexity is given.

In [START_REF] Dereniowski | Topology recognition and leader election in colored networks[END_REF], Dereniowski and Pelc study a generalization of the process-terminating leader election in arbitrary networks of homonym processes where processes know a priori an upper bound k on the multiplicity of a given label that exists in the network, i.e., each process knows that is the label of at least one but at most k processes. They propose a synchronous algorithm that, under these hypotheses, decides whether the election is possible and achieves it, if so. They show that this algorithm is asymptotically optimal in time (O(kD + D log(n/D)), where D is the diameter of the network).

Contributions. We explore the design and complexity of the (deterministic) process-terminating leader election in unidirectional rings with homonym processes which, contrary to [START_REF] Flocchini | Sorting and election in anonymous asynchronous rings[END_REF][START_REF] Dobrev | Leader election in rings with nonunique labels[END_REF][START_REF] Delporte-Gallet | Leader election in rings with homonyms[END_REF], know neither the number of processes n nor any bound on it. Since we only consider unidirectional rings, results of Delporte et al. [START_REF] Delporte-Gallet | Leader election in rings with homonyms[END_REF] do not apply -the common sense of direction may help processes to solve the leader election problem.

We consider five classes of unidirectional labeled rings: U * , K k , A, U * ∩ K k , and A ∩ K k . U * is the class of all rings in which at least one label is unique. K k is the class of all rings where no label occurs more than k times, so k is an upper bound on the multiplicity of the labels. Finally, A is the class of all asymmetric labeled rings, i.e., all labeled rings that have no non-trivial rotational symmetry. By definition,

U * ∩ K k ⊂ U * ⊂ A and A ∩ K k ⊂ A.
We first establish that the time complexity of any process-terminating leader election algorithm for U * ∩ K k (with k ≥ 2) is Ω(k n) times units. We then show that any messageterminating leader election algorithm for U * ∩K k (with k ≥ 2) requires to exchange Ω(kn+n 2 ) bits. By definition, these two lower bounds also hold for A ∩ K k . Using our lower bound on the time complexity, we derive a simple impossibility result on the process-terminating leader election in U * , and so in A. Finally, using a direct extension of the impossibility results of Angluin [START_REF] Angluin | Local and global properties in networks of processors[END_REF], we know that the message-terminating leader election is impossible in K k for any k ≥ 2.

Hence, we focus on the process-terminating leader election in U * ∩ K k and A ∩ K k by proposing three algorithms for these classes. The first algorithm, U k , solves the processterminating leader election algorithm in U * ∩ K k . U k is asymptotically optimal in time, as its time complexity is O(k n) time units. Its message complexity is O(n 2 + kn). Finally, U k is asymptotically optimal in space, as it requires O(log k + b) bits per process, where b is the number of bits required to store a label.

Then, we propose two process-terminating leader election algorithms, A k and B k , for the more general class A ∩ K k . Those two algorithms show a trade-off between time and space. A k is asymptotically optimal in time (O(k n)), but it requires O(knb) bits per process and O(kn 2 ) messages are exchanged during an execution. On the contrary, B k requires only O(log k + b) bits per process (which is asymptotically optimal), but its time and message complexities are both O(k 2 n 2 ).

Finally, notice that our assumptions on the initial knowledge of processes are not comparable in general with those made in [START_REF] Dobrev | Leader election in rings with nonunique labels[END_REF][START_REF] Delporte-Gallet | Leader election in rings with homonyms[END_REF]. As a matter of fact, Dobrev and Pelc [START_REF] Dobrev | Leader election in rings with nonunique labels[END_REF] explain that there are simple cases where the knowledge of some lower bound m and upper bound M on n does not permit their (process-terminating) leader election algorithm to succeed. They illustrate this statement with an example where the initial knowledge of processes is m = 3 and M = 6. In this case, the 3-node ring with labels 1,2,2 matches those bounds. Now, for this ring their algorithm decides the input is ambiguous and so does not elect a leader because nodes are unable to distinguish whether they are in the 3-node ring with labels 1,2,2 (which is asymmetric), or in a 6-node ring with label 1,2,2,1,2,2 (which is symmetric). We have not such an ambiguity in our settings. Indeed, in our settings (i.e., assuming the knowledge of k and a common orientation), our process-terminating algorithms elect a leader in the 3-node ring with labels 1,2,2 since it (in particular) belongs to U * ∩ K k . Similarly, the assumptions made in [START_REF] Delporte-Gallet | Leader election in rings with homonyms[END_REF] (i.e., the knowledge of n and the fact that the number of labels is strictly greater than the greatest proper divisor of n) exclude the 6-node ring with label 1,2,2,2,2,2. Indeed, in this labeled ring, the number of labels is 2 and the greatest proper divisor of 6 is 3. Now, in our settings, our algorithms are able to elect a leader in this labeled ring since it belongs (in particular) to U * ∩ K k .

Roadmap. Section 2 is dedicated to model and definitions. Lower bounds and impossibility results are presented in Sections 3 and 4. Algorithms U k , A k , and B k are proposed in Sections 5, 6, and 7, respectively, together with their correctness and complexity analysis. We conclude in Section 8 with some perspectives.

Extension of two conference papers. This journal paper is an extension of two preliminary versions, respectively published in the proceedings of SSS'2016 [START_REF] Altisen | Leader election in rings with bounded multiplicity[END_REF] and IPDPS'2017 [START_REF] Altisen | Leader election in asymmetric labeled unidirectional rings[END_REF]. Compared to those two conference papers, this journal paper contains significantly new material. Indeed, the lower bounds on the exchanged bit complexity in Section 3 (i.e., Theorem 1 and its associated corollary, Corollary 3) are totally new. Then, concerning impossibility results, Theorem 2 (Section 4) is also new. Concerning now the algorithmic part, Algorithm U k (Section 5) was originally presented in [START_REF] Altisen | Leader election in rings with bounded multiplicity[END_REF], yet without any proof of correctness or complexity analysis. We have filled all these important blanks in the present paper. Furthermore, it is worth noting that the time and space complexity bounds we prove here are very precise. Finally, we have refined both the correctness proof and complexity analysis of Algorithm B k initially proposed in [START_REF] Altisen | Leader election in asymmetric labeled unidirectional rings[END_REF]. In particular, we have revised the time complexity analysis of Algorithm B k to obtain tighter bounds.

Preliminaries

Ring Networks. We assume unidirectional rings of n ≥ 2 processes, p 0 , . . . , p n-1 , operating in asynchronous message-passing model, where links are FIFO and reliable. p i can only receive messages from its left neighbor, p i-1 , and can only send messages to its right neighbor, p i+1 . Subscripts are modulo n. The state of a process is a vector of the values of its variables. The state of a link (p i , p i+1 ), noted S (p i ,p i+1 ) , is the ordered list of messages it contains. A configuration is a vector of states, one for each link and each process of the ring. Let γ be a configuration. The state of process p in γ is denoted by γ(p). The value of the variable x of p in γ is denoted by γ(p).x. Processes communicate using the functions send and rcv. Since every link (p i , p i+1 ) is reliable, calls to send by p i and rcv by p i+1 are the only way to modify S (p i ,p i+1 ) . When p i executes send m, the message m is added at the tail of S (p i ,p i+1 ) . Let now explain how a call of p i+1 to rcv works. Each message is of the form x 1 , . . . , x k , where x 1 , . . . , x k is a list of values, each of a given datatype. We say that a value x conforms to y if y is a value and x = y, or y is a variable and has the same datatype as x. A message in S (p i ,p i+1 ) remains in this list until p i+1 receives it by calling the function rcv (no message loss). The received messages are processed FIFO. So, the function rcv is message-blocking: A call to rcv v 1 , . . . , v z by p i+1 returns True if and only if the head message x 1 , . . . , x z of S (p i ,p i+1 ) satisfies ∀j ∈ {1, . . . , z}, x j conforms to v j . When a call to rcv v 1 , . . . , v z by p i+1 returns True, the head of S (p i ,p i+1 ) , x 1 , . . . , x z , is removed from S (p i ,p i+1 ) (each message is received exactly once) and ∀j ∈ {1, . . . , z}, v j is assigned to x j if v j is a variable. Otherwise, rcv does not modify S (p i ,p i+1 ) .

A distributed algorithm is a collection of n local algorithms, one per process. We assume that processes have no knowledge about n, and each process p has a label, p.id; labels may not be distinct. For any label in the ring R, let mlty( ), the multiplicity of in R, be the number of processes in R whose id is . Comparisons (order and equality) are the only operations permitted on labels. We denote by b the number of bits required to store any label. In our distributed algorithms, all local algorithms are identical, except maybe for the labels. In particular, every execution begins at a so-called initial configuration, where each process is at a designated initial state and all links are empty. The local algorithm of each process p is given as a list of actions of the form guard → statement . A guard is a predicate involving the variables of p and calls to rcv. An action is enabled if its guard is True. A process p is enabled if at least one of its action is enabled. A statement contains assignments of p's variables and/or calls to the function send. The statement of an action can be executed by p only if the action is enabled at p. We assume that the actions are atomically executed, i.e., the evaluation of the guard and the execution of the corresponding statement, if executed, are done in one atomic step. We enforce the local algorithm of each process p to contain at most one action triggerable without the reception of any message. This action should be executed by p first in all executions.

Processes are fairly activated, i.e., if a process is continuously enabled, then it eventually executes one of its enabled actions. Let → be the binary relation over configurations such that γ → γ if and only if γ can be obtained from γ by the atomic execution of one or more enabled processes in γ; γ → γ is called a step. An execution is a maximal sequence of configurations Γ = γ 0 . . . γ i . . . such that (1) γ 0 is the initial configuration, (2) ∀i > 0, γ i-1 → γ i , and (3) processes are fairly activated in Γ. Maximal means that Γ is either infinite, or ends in a socalled terminal configuration where no process is enabled. Time complexity [START_REF] Tel | Introduction to Distributed Algorithms[END_REF] is evaluated in time units, assuming that message transmission time is at most one time unit, and the process execution time is zero. Roughly speaking, time complexity measures the execution time of the algorithm according to the slowest messages: the execution is normalized in such a way that the longest message delay (i.e., the transmission of the message followed by its processing at the receiving process) becomes one unit of time.

Leader Election. We consider two definitions of the problem of leader election in the messagepassing model: the message-terminating and the process-terminating leader election [START_REF] Tel | Introduction to Distributed Algorithms[END_REF]. Informally, in a process-terminating solution, every process eventually halts, whereas, in a message-terminating solution, processes do not halt but only a finite number of messages is exchanged.

Definition 1 (Message-terminating Leader Election). An algorithm Alg solves the messageterminating leader election problem in a ring network R if every execution e of Alg on R satisfies the following conditions:

1. e is finite. Ring Networks Classes. An algorithm Alg solves the message-terminating (resp. processterminating) leader election for the class of ring networks C if it solves the message-terminating (resp. process-terminating) leader election for every ring network R ∈ C. In particular, Alg cannot be given any specific information about the network (such as its cardinality or the actual multiplicity of labels) unless that information holds for all ring networks of C. Indeed, Alg must work for every R ∈ C without any change whatsoever in its code.

A ring network R of n processes is said to be symmetric if a non-trivial rotation of the labels results in the same labeling, i.e., there is some integer 0 < d < n such that, for all i ≥ 0, p i and p i+d have the same label. Otherwise, R is said to be asymmetric.

We mainly consider the three following classes of ring networks.

• A is the class of all asymmetric unidirectional ring networks.

• U * is the class of all unidirectional ring networks in which at least one process has a unique label. By definition, U * ⊂ A. • K k , with k ≥ 1 a given integer, is the class of all unidirectional ring networks where no more than k processes have the same label: k is an upper bound on the multiplicity of labels in R ∈ K k . Notice that K 1 ⊂ U * and K 1 ⊂ K 2 . . .

Lower Bounds

We first establish a lower bound that depends on k on the execution time of any processterminating leader election algorithm in U * ∩ K k (with k ≥ 2). Even though, it has been written independently, it appears that the proof of the technical result below is essentially an adaptation of the proof of the "Quasi-Lifting corollary" [START_REF] Chalopin | Election in partially anonymous networks with arbitrary knowledge in message passing systems[END_REF] to our context. Lemma 1. Let k ≥ 2 and Alg be an algorithm that solves the process-terminating leader election for U * ∩ K k . ∀R ∈ K 1 , the synchronous execution of Alg in R lasts at least 1 + (k -2) n time units, where n is the number of processes.

Proof. Let k ≥ 2 and Alg be a process-terminating leader election algorithm for U * ∩ K k . Let R n ∈ K 1 be a ring of n processes, noted p 0 , . . . , p n-1 with distinct labels 0 , . . . , n-1 respectively, see Figure 1a. Since K 1 ⊆ U * ∩K k , Alg is correct for R n and so, the synchronous execution e = (γ i ) i≥0 of Alg on R n is finite and a process is elected. Let T be the execution time of e: within T time units in e, p L .isLeader becomes True for some 0 ≤ L ≤ n -1, i.e., p L is the leader in the terminal configuration γ T of e. We now build the ring R n,k ∈ U * ∩ K k of kn + 1 processes, q 0 , . . . , q kn , with labels consisting of the sequence 0 , . . . , n-1 repeated k times, followed by a single label X / ∈ { 0 , . . . , n-1 }, see Figure 1b. Let e = (γ i ) i≥0 be the synchronous execution of Alg on R n,k . Since R n,k ∈ U * ∩ K k , Alg is correct on R n,k so e is finite and there is no configuration along e such that two processes declare themselves leader. By construction, after t ≥ 0 time units, only the processes q i , with i ∈ {0, . . . , t -1}, can have received information from process q kn of label X, see the gray zone on Figure 1b. In gray, the processes of R n,k that can have received information from q kn of label X within t ≥ 0 time units.

0 1 n-1 p 0 p 1 p n-1 (a) Ring R n 0 1 t-1 n-1 0 1 n-1 X q 0 q 1 q t-1 q n-1 q n q n+1 q 2n-1 q kn (b) Ring R n,k
Hence, we have the following property on e : ( * ) For every j ∈ {0, ..., kn -1}, for every t ≥ 0, if t ≤ j, then the state of q j in γ t is identical to the state of p j mod n in γ t .

Assume, by contradiction, that T ≤ (k -2)n. Let j 1 = (k -2)n+L and j 2 = (k -1)n+L. Since L ∈ {0, ..., n -1}, we have j 1 , j 2 ∈ {0, ..., kn -1}, hence T ≤ j 1 < j 2 . Moreover, j 1 mod n = j 2 mod n = L. So, by ( * ) the states of q j 1 and q j 2 in γ T are identical to the state of p L in γ T : in particular, γ T (q j 1 ).isLeader = γ T (q j 2 ).isLeader = True. This contradicts the fact that Alg is a process-terminating leader election algorithm for R n,k . (Bullet 5 of the specification is violated in γ T , see p. 6.) Hence, the execution time T of the synchronous execution of Alg in R n is greater than (k -2)n.

Since K 1 ⊆ U * ∩ K k , follows: Corollary 1. Let k ≥ 2.
The time complexity of any algorithm that solves the processterminating leader election for U * ∩ K k is Ω(k n) time units, where n is the number of processes.

Furthermore, by definition U * ⊆ A, and so:

Corollary 2. Let k ≥ 2.
The time complexity of any algorithm that solves the processterminating leader election for A∩K k is Ω(k n) time units, where n is the number of processes.

The algorithm proposed by Peterson [START_REF] Peterson | An o(n log n) unidirectional algorithm for the circular extrema problem[END_REF] to solve leader election in identified ring networks has message complexity O(n log n) and each message contains Θ(b) bits, i.e., the amount of exchanged information is O(b n log n). As commonly done in the literature, we can assume that b = Θ(log n) in identified networks, so O(b n log n) = O(n log 2 n). Then, as the algorithm of Peterson applies for U * ∩ K 1 , we might expect that there exists a leader election algorithm for class U * ∩ K k whose required amount of exchanged information is O(k n log 2 n). Theorem 1 shows that, when k is fixed, the minimum amount of exchanged bits needed to solve leader election in the worst case is greater than what we might expect when n is large. q 8 q 7 q 6 q 5 q 4 q 3 q 2 q 1 q 12 q 11 q 10

(b) R J q 8 q 7 q 6 q 5 q 4 q 3 q 2 q 1 q 12 q 11 q 10 Theorem 1. Let k ≥ 2. For any message-terminating leader election algorithm Alg for U * ∩ K k , there exists executions of Alg during which Ω(kn + n 2 ) bits are exchanged, where n is the number of processes.

Proof. Let k ≥ 2. Let Alg be a message-terminating leader election algorithm for U * ∩ K k . Let m ≥ 2 and let n = 2m. Let 1 , . . . , n be distinct labels. Let L be the set of nonempty proper subsequences of ( m+1 , . . . , n ), i.e., the subsequences of ( m+1 , . . . , n ) whose length is at least one but at most m -1. For any I ∈ L, R I is the ring network containing m + |I| processes, denoted p 1 , p 2 , . . . , p m , p m+1 , . . . , p m+|I| , whose label sequence is Λ I = 1 , 2 , . . . , m , I. More precisely, in R I , for every i ∈ {1, . . . , m}, p i .id = i and for every j ∈ {1, . . . , |I|}, p m+j .id = I[j] (the j th element of I). The ring network R I for m = 7 and I = 8 , 10 , 11 , 13 , 14 is illustrated on Figure 2a.

Let R = {R I : I ∈ L}. Notice that |R| = 2 m -2 (since the empty sequence and { m+1 , . . . , n } are not in L). Furthermore, every label in R I is unique so R I ∈ U * ∩ K k . Hence, Alg is correct for every R I ∈ R. For every I, J ∈ L, let R I#J be the ring network containing 2m+|I|+|J| processes whose label sequence is Λ I Λ J . R I#J can be obtained from R I and R J as follows (we denote by q 1 , . . . , q m+|J| the processes of R J to avoid confusion). For some p ∈ {1, . . . , m -1}, we obtain R p I#J when we join R I and R J by removing edges (p p , p p+1 ) and (q p , q p+1 ) and replacing them by edges (p p , q p+1 ) and (q p , p p+1 ). Figure 3 shows the ring network R p I#J for p = 3, I = 8 , 10 , 11 , 13 , 14 , and J = 8 , 10 , 12 , 13 , 14 obtained by joining R I (see Figure 2a) and R J (see Figure 2b).

Claim 1: For every p ∈ {1, . . . , m -1}, if I = J, then R p I#J ∈ U * ∩ K k . Proof of Claim 1: No label appears more than twice in R p I#J so R p I#J ∈ K k .
Then, without loss of generality, assume |I| ≤ |J|. So, there is some j ∈ J\I and j is a unique label in R p I#J . Hence, R p I#J ∈ U * . For every I ∈ L, let e I be the synchronous execution of Alg on R I . For each p ∈ {1, . . . , m}, let σ I,p be the stream (sequence) of bits sent by p p to p p+1 during e I . Claim 2: For any I, J ∈ I and any p ∈ {1, . . . , m -1}, if σ I,p = σ J,p , then I = J. Proof of Claim 2: Let I, J ∈ I and p ∈ {1, . . . , m -1}. Assume that σ I,p = σ J,p . Let R p I#J the ring network obtained by joining R I and R J at the edges (p p , p p+1 ) and (q p , q p+1 ). Let e p I#J be the synchronous execution of Alg on R p I#J . First, we show by induction on the steps of e p I#J that ∀x ≥ 1, every process p i , i ∈ {1, . . . , m + |I|} (respectively, q j , j ∈ {1, . . . , m + |J|}) sends the same bits during the x th step of e p I#J than in the x th step of e I (respectively, e J ). Base Case: Alg is a deterministic algorithm and every process p i (respectively, q j ) has the same initial state (in particular, the same label) in e p I#J than in e I (respectively, e J ). Hence every process p i (respectively, q j ) sends the same bits during the first step of e p I#J than during the first step of e I (respectively, e J ). Induction Step: Assume that every process p i , i ∈ {1, . . . , m + |I|} (respectively, q j , j ∈ {1, . . . , m + |J|}) sends the same bits during the x th step of e p I#J than in the x th step of e I (respectively, e J ), x ≥ 1. Consider the (x + 1) th step of e p I#J . Every process p i , i ∈ {1, . . . , p} ∪ {p + 2, m + |I|}, (respectively, q j , j ∈ {1, . . . , p} ∪ {p + 2, . . . , m + |J|}) has the same predecessor in R p I#J than in R I (respectively, R J ). By induction hypothesis, this predecessor sends the same bits during the x th step of e p I#J than during the x th step of e I (respectively, e J ). Now, the only processes that do not have the same predecessor in R p I#J than in R I or R J are p p+1 and q p+1 . By induction hypothesis, their predecessor, respectively q p and p p , send the same bits during the x th step of respectively e p I#J than during the x th step of respectively e J and e I . Furthermore, σ I,p = σ J,p so they send the exact same bits. Hence, every process receives the same bits and so send the same bits (since the algorithm is deterministic) during the (x + 1) th step of e p I#J than during the (x + 1) th step of e I or e J . Hence, the processes cannot distinguish e p I#J and e I or e J . So both the process that declares itself leader in e I and the one that declares itself leader in e J also declares itself leader in e p I#J . Now, assume by contradiction that I = J. By Claim 1, R p I#J ∈ U * ∩ K k . Since two processes declare themselves leader in e p I#J , we have a contradiction with the correctness of Alg for class U * ∩ K k .

The rest of the proof is based on a counting argument, i.e., there are not enough bit streams to distinguish the rings of R, unless those streams have length Ω(n 2 ). Let a = m-2. Recall that a set of cardinality m has 2 m subsets including 2 m -2 non-empty proper subsets.

The number of bit streams of length at most a is:

a l=1 2 l = 2 a+1 -1 = 2 m-1 -1 < 2 m -2 Let p ∈ {1, . . . , m -1}. Let L p = {I ∈ L : |σ I,p | ≤ a}.
By Claim 2, L p has cardinality less than 2 m -2, so there exists some I ∈ L that is not a member of L p , for any p ∈ {1, . . . , m -1}. Hence, Ω(m a) = Ω(n 2 ) bits are exchanged during the synchronous execution of Alg on R I . Now, at least one message must be exchanged at each step, so, by Corollary 1, there exists executions of Alg where Ω(kn + n 2 ) bits are exchanged.

Since U * ∩ K k ⊆ A ∩ K k , follows: Corollary 3. Let k ≥ 2.
For any message-terminating leader election algorithm Alg for A ∩ K k , there exists executions of Alg during which Ω(kn + n 2 ) bits are exchanged, where n is the number of processes.

Impossibility Results

Class K k . Below, we extend the impossibility results of Angluin [START_REF] Angluin | Local and global properties in networks of processors[END_REF] to K k . Theorem 2. There is no algorithm that solves message-terminating leader election in a symmetric ring of at least 2 processes.

Proof. Let R be a symmetric ring of n ≥ 2 processes. Let 0 < d < n such that, for all i ≥ 0, p i and p i+d have the same label. Assume by contradiction that Alg is a message-terminating leader election algorithm for R. Let e = (γ j ) j≥0 be the synchronous execution of Alg on R. At every step of e, each p i , i ≥ 0, makes exactly the same actions as p i+d , and thus, every configuration of e is symmetric; i.e., for all 1 ≤ i ≤ n and for all configurations γ j , j ≥ 0, of e, all variables of p i and p i+d have the same value. Eventually, a terminal configuration γ T is reached. Let p be the elected leader in γ T ; thus γ T (p ).isLeader = True. But γ T (p +d ).isLeader also, which contradicts the uniqueness of the leader in a solution, since p +d = p . Class K k , k ≥ 2, contains symmetric rings of at least two processes, e.g., see Figure 4. Hence, we have: Theorem 3. For any k ≥ 2, there is no algorithm that solves message-terminating leader election for K k .

Classes U * and A. Using Lemma 1, we can easily derive the following two impossibility results.

Theorem 4. There is no algorithm that solves the process-terminating leader election for U * . (a) Ring in K 3 . Proof. Suppose Alg is an algorithm for U * . Let R n be a ring network of K 1 with n processes. Let e be the synchronous execution of Alg on R n : as K 1 ⊆ U * , Alg is correct for R n and, consequently, e is finite. Let T be the number of steps of e. We can fix some k

≥ 2 such that 1 + (k -2) n > T . Since (U * ∩ K k ) ⊆ U * , Alg is correct for U * ∩ K k . By Lemma 1, T ≥ 1 + (k -2)n, a contradiction.
Since by definition U * ⊆ A, Theorem 4 implies the following corollary.

Corollary 4. There is no algorithm that solves the process-terminating leader election for A.

Algorithm U k

In this section, we present Algorithm U k which solves the process-terminating leader election for the class U * ∩ K k , with fixed k ≥ 1 (see Algorithm 1).

Variables of U k

U k elects the process of minimum unique label to be the leader, namely the process L such that L.id = min {p.id : p ∈ V ∧ mlty(p.id) = 1}. In U k , each process p has the following variables.

1. p.id, (constant) input of unspecified label type, the label of p.

:: ¬p.init ∧ p.active ∧ rcv x, c ∧ x = p.id → send x, c ∧ (p.count = 0 ∨ c > p.count) A3 :: ¬p.init ∧ p.active ∧ rcv x, c ∧ x > p.id → send x, c ∧ c = p.count ∧ c ≥ 1 A4 :: ¬p.init ∧ p.active ∧ rcv x, c ∧ x = p.id → p.count ← c + 1 ∧ c = p.count ∧ c ≤ k -1 send x, c + 1 (Deactivation) A5 :: ¬p.init ∧ p.active ∧ rcv x, c ∧ x = p.id → p.active ← False ∧ c < p.count send x, c A6 :: ¬p.init ∧ p.active ∧ rcv x, c ∧ x < p.id → p.active ← False ∧ c = p.count ∧ c ≥ 1 send x, c (Passive Processes) A7 :: ¬p.init ∧ ¬p.active ∧ rcv x, c ∧ x = p.id ∧ c ≤ k → send x, c A8 :: ¬p.init ∧ ¬p.active ∧ rcv x, c ∧ x = p.id → (nothing) (Termination) A9 :: ¬p.init ∧ p.active ∧ rcv x, k ∧ x = p.id → p.isLeader ← True ∧ p.count = k p.leader ← p.id p.done ← True p.count ← k + 1 send x, k + 1 A10 :: ¬p.init ∧ ¬p.active ∧ rcv x, k + 1 → p.leader ← x p.done ← True send x, k + 1 (halt) A11 :: ¬p.init ∧ p.active ∧ rcv x, k + 1 ∧ x = p.id → (halt) ∧ p.count = k + 1
7. p.done, Boolean, initially False, follows the problem specification: eventually, p.done = True for all p. p.done means that p knows a leader has been elected; once true, it will never become false.

Messages of U k

U k uses only one kind of message. Each message is the forwarding of a token which is generated at the initialization of the algorithm, and is of the form x, c , where x is the label of the originating process, and c is a counter, an integer in the range 0 . . . k + 1, initially zero.

Overview of U k

The explanation below is illustrated by the example in Figure 5. The fundamental idea of U k is that a process becomes passive, i.e., is no more candidate for the election, if it receives a token that proves its label is not unique or is not the smallest unique label.

Counter Increments. Initially, every process initiates a token with its own label and counter zero (see (a)). No tokens are initiated afterwards. Each token moves around the ring clockwise -every time it is forwarded, its counter and the local counter of the processes are incremented if the forwarding process has the same label as the token (e.g., Step (a) →(b)). Thus, if the message x, c is in a channel, that token was initiated by a process whose label is x, and has been forwarded c times by processes whose labels are also x. The token could also have been forwarded any number of times by processes with labels which are not x. Thus, the counter in a token is a rough estimate of the frequency of its label in the ring.

A1 C B B A B p 0 p 1 p 2 p 3 p 4 0 0 0 0 0 C, 0 B, 0 B, 0 A, 0 B, 0 (a) A2 A4 C B B A B p 0 p 1 p 2 p 3 p 4 0 0 1 0 0 B, 0 C, 0 B, 1 B, 0 A, 0 (b) A2 A5 A4 C B B A B p 0 p 1 p 2 p 3 p 4 0 1 1 0 1 A, 0 B, 1 C, 0 B, 1 B, 1 (c) A7 A4 C B B A B p 0 p 1 p 2 p 3 p 4 1 1 1 1 2 C, 1 A, 1 (d) A7 C B B A B p 0 p 1 p 2 p 3 p 4 1 1 1 1 2 A, 1 C, 1 (e) A7 C B B A B p 0 p 1 p 2 p 3 p 4 1 1 1 3 2 A, 3 (f ) A9 C B B A B p 0 p 1 p 2 p 3 p 4 1 1 1 4 2 A, 4 (g) A10 C B B A B A p 0 p 1 p 2 p 3 p 4 1 1 1 4 2 A, 4 (h) A10 A11 C A B A B A A B A p 0 p 1 p 2 p 3 p 4 1 1 1 4 2 A, 4 (i)
Non-unique Label Elimination. If an active process p receives a message tagged with a label different from p.id whose counter is (strictly) less than p.count, this proves the label of p is not unique since the counter p.count grows faster than the one of another label. In this case, p executes A5-action and becomes passive (e.g., Step (b) →(c)). Since the counter in the token initiated by L is never incremented, except by L itself, L cannot become passive using this rule. Moreover, every process whose label is not unique becomes passive during the first two ring traversals of the token initiated by L.

Non-lowest Unique Label Elimination. Similarly, if an active process p has a unique label but not the smallest one, it will become passive executing A6-action when p receives a message with the same non-zero counter but a label lower than p.id (e.g., Step (d) →(e)). This happens at the latest when the process receives the message L.id, 1 , i.e., before the second time L receives its own token. So, after the token of L has made two traversals of the ring, every process but L is passive. Moreover, the token initiated by L is the only surviving token because all other tokens have vanished using A8-action.

Termination Detection. The execution continues until the leader L has seen its own label return to it k + 1 times (i.e., until L receives L.id, k since the counter inside its token is initialized to zero), otherwise L cannot be sure that what it has seen is not part of a larger ring instead of several rounds of a small ring. Then, L designates itself as leader by A9-action (see Step (f) →(g)) and its token does a last traversal of the ring to inform the other processes of its election (e.g., Step (g) →(h)). The execution ends when L receives its token after k + 2 traversals (see (i)).

Correctness and Complexity Analysis

To prove the correctness of U k (Theorem 5), we first prove some results on the counters inside the tokens (Lemma 2). Then, Lemmas 3-7 prove properties on the different phases of U k . Finally, Theorem 6 gives a complexity analysis of U k .

In the following proofs, we write #hop(m) for the number of hops, made so far by the token associated to the message m. Notice that #hop(m) is always of the form an + b where a ≥ 0 is the number of complete traversals realized by the token and 0 ≤ b < n is the (clockwise) hop-distance from the initiator of the token to its last tokenholder. Lemma 2. Let γ → γ be a step. Suppose a message x, c such that #hop( x, c ) = an + b in γ with a ≥ 0 and 0 ≤ b < n is sent in γ → γ . Then:

1. c ≥ a, 2. if x is a unique label, then c = a, and 3. if x is a not a unique label and a ≥ 1, then c > a.

Proof. Let p be the process which originated the token currently carried by the message m.

The token has made a complete traversals of the ring, and has visited p a times, hence its counter has been incremented at least a times. This proves 1. If p is the only process with label x, then the counter has not otherwise been incremented, and we have 2. Suppose x is not a unique label, and a ≥ 1. There are at least two processes with label x. The token has made at least a full traversals, and thus has been sent by processes of label x at least 2a times. Starting at zero, c has been incremented at least 2a times, hence c ≥ 2a > a, and we have 3.

For the next lemma, we recall that a process can become passive only by executing A5 or A6-action. Lemma 3. L never becomes passive.

Proof. By contradiction, assume L becomes passive during some step γ → γ . Then L executes A5 or A6-action, receiving the message x, c for some x = L.id. Since the label of L is unique, the token it initiated is still circulating in the ring in γ (it cannot be discarded except by L if it is passive). Moreover, since x = L.id, #hop( x, c ) is not a multiple of n in γ. Let #hop( x, c ) = an + b in γ, where a ≥ 0 and 1 ≤ b < n. Since the links are FIFO, the token initiated by L has made a full circuits during the prefix of execution leading to γ, and γ(L).count = a. We now consider two cases.

• Case 1: x is a unique label. By Lemma 2.2, c = a = L.count. Thus, L cannot execute A5-action, and since L.id < x, L cannot execute A6-action either, a contradiction. • Case 2: x is not unique. (Recall that L.count = a in γ.) If a = 0, then L is not enabled to execute either action. If a ≥ 1, then c > a by Lemma 2.3, contradiction.

We define an L-tour as follows. Let e = (γ i ) i≥0 be an execution of U k . The first L-tour of e is the minimum prefix γ 0 . . . γ j of e such that L receives (and treats) a message tagged with its own label (for the first time) in step γ j-1 → γ j . If γ j is not a terminal configuration, then the second L-tour is the first L-tour of the execution suffix e = (γ i ) i≥j starting in γ j , and so forth. From Lemma 3, the code of the algorithm, and the fact that the label of L is unique, we have: Corollary 5. Any execution contains exactly k + 2 complete L-tours. Lemma 4. For any process p, if p = L and p.id is a unique label, then p becomes passive within the first two L-tours.

Proof. Let x = L.id. By definition of L, x < p.id. Let d = L, p . Suppose by contradiction that p does not become passive during the first two L-tours (which are defined, Corollary 5). The token t initiated by L is received by p during the first (resp. second) L-tour while #hop(t) = d (resp. #hop(t) = n + d). p receives the token it initiates exactly once before receiving the token t = x, c (initiated by L) during the second L-tour, say in step γ → γ . So, as p.id is unique, we have p.count = 1 in γ. Now, c = 1 in γ (Lemma 2.1). Thus, p becomes passive by executing A6-action in γ → γ , contradiction. Lemma 5. If z is a non-unique label, then all processes of label z become passive within the first two L-tours.

Proof. Let m ≥ 2 be the multiplicity of z, and let P[z] = {x 1 , x 2 , . . . x m } be the sequence of processes of label z in clockwise order from L. Claim 1: Any process x i with i = 1 receives the token initiated by x i-1 of the form z, 0 during the first L-tour before receiving L.id, 0 .

Proof of Claim 1: L is not between x i-1 and x i , and no process between x i-1 and x i can stop the message z, 0 initiated by x i-1 . So, x i will receive z, 0 before receiving L.id, 0 during the first L-tour.

Claim 2: x 1 receives z, 0 and then z, 1 during the first two L-tours, both of them before receiving L.id, 1 .

Proof of Claim 2:

No process between x m and x 1 can stop the message z, 0 initiated by x m . Then, by Claim 1, x m receives a message z, 0 , while satisfying x m .count = 0. So, x m sends z, 1 after z, 0 , but before receiving L.id, 0 . Again, no process between x m and x 1 can stop that message. So, x 1 receives z, 0 and z, 1 before receiving L.id, 1 , i.e., during the first two L-tours.

Claim 3: Every process x i with i = 1 receives z, 1 during the first two L-tours before receiving L.id, 1 .

Proof of Claim 3:

The first time x i-1 receives z, 0 is before x i-1 receives L.id, 1 in the first two L-tours, by Claims 1 and 2. In that step, x i-1 sends z, 1 . No process between x i-1 and x i can stop that message. So, x i receives z, 1 during the first two L-tours before receiving L.id, 1 .

By Claims 2 and 3, each x i receives the message z, 1 during the first two L-tours before receiving L.id, 1 . Consider the first time x i receives such a message. Then, x i .count = 1. Either x i is already passive and we are done, or x i .count is set to 2. Hence, when receiving L.id, 1 during the first two L-tours, x i executes A5-action and we are done. Lemma 6. For any process p, if p = L, then p never executes A9-action.

Proof. Assume, by the contradiction, that some process p = L eventually executes A9action. Let x = p.id. Then, p successively receives x, 0 , . . . , x, k so that p.active ∧ p.count = k holds when p receives x, k . Notice also that p also receives L.id, 0 and L.id, 1 , by Lemma 3.

First, p does not receive L.id, 0 after x, k , because otherwise p received at least k + 1 messages tagged with label x during the first L-tour, which is impossible since the multiplicity of x is at most k and the links are FIFO.

Assume now that p receives L.id, 0 before x, k but after x, 0 . Then, p is deactivated by A5-action when it receives L.id, 0 because p.count > 0 and so before receiving x, k , a contradiction.

So, p receives L.id, 0 before x, 0 . Similarly, p does not receive L.id, 1 after x, k , because otherwise p received at least k + 1 messages tagged with label x during the first L-tour. Then, p does not receive L.id, 1 before x, 0 because otherwise p does not receive any message tagged with x during the first L-tour, now it receives at least x, 0 during the first L-tour from either its first predecessor with same label, or itself (if x is unique in the ring).

If p receives L.id, 1 before x, 1 , then x is unique in the ring and when p receives L.id, 1 , p is deactivated by A6-action, and so before receiving x, k , a contradiction.

Finally, if k > 1 and if p receives L.id, 1 after x, 1 but before x, k , then p is deactivated by A5-action when it receives L.id, 1 , because 1 < p.count ≤ k. Hence, again, p is deactivated before receiving x, k , a contradiction. Lemma 7. In any execution of U k :

1. For every process p = L, p.active becomes False within the first two L-tours. 2. For every process p = L, p never executes A9-action.

3. L executes A9-action after exactly k + 1 L-tours. In this action L.leader ← L, L.isLeader ← True, and L.done ← True. 4. For every process p = L is a process, p executes A10-action during the (k+2) nd L-tour.

In this action p.leader ← L and p.done ← True. 5. L executes A11-action after exactly k + 2 L-tours, and that is the last action of the execution.

Proof. Part 1 follows from Lemmas 4 and 5. Part 2 is Lemma 6. Parts 3-5 follow from Corollary 5: The token initialized by L circles the ring k + 2 times, each time incrementing L.count once. At the end of the (k + 1) st traversal, L executes A9-action, electing itself to be the leader. The message L.id, k + 1 then circles the ring, informing all other processes that L has been elected. Those latter processes halt after forwarding this message. When that final message reaches L, the execution is over.

Theorem 5 below follows immediately from Lemma 7.

Theorem 5. U k solves the process-terminating leader election for U * ∩ K k , for every given k ≥ 1.

Theorem 6. U k has time complexity at most (k + 2)n, message complexity at most 3n 2 + (k -1)n, and requires log(k + 1) + 2b + 4 bits in each process.

Proof. Time complexity follows from Lemma 7.5. Space complexity follows from the definition of U k . Consider now the message complexity of U k . All tokens, except the one initiated by L, vanish during the three first L-tours, by Lemma 7.1. Consequently, only the token initiated by L circulates during the k -1 last L-tours. Hence, we have a message complexity of 3n 2 +(k -1)n (at most 3n 2 for messages transmitted during the 3 first L-tours, and exactly (k -1)n, with k ≤ n, for the unique token circulating during the k -1 last L-tours).

Algorithm A k

We now give a solution, Algorithm A k , to the process-terminating leader election for the class A ∩ K k , with fixed k ≥ 1. A k is based on the following observation. Consider a ring R of A∩K k with n processes. As R is asymmetric, any two processes in R can be distinguished by examining all labels. So, using the lexicographical order, a process can be elected as the leader by examining all labels. Initially, any process p of R does not know the labels of R, except its own. But, if each process broadcasts its own label clockwise, then any process can learn the labels of all other processes from messages it receives from its left neighbor. In the following, we show that, after examining finitely many labels, a process can decide that it learned (at least) all labels of R and so can determine whether it is the leader.

Variables of A k

Each process p has six variables. 1. As defined in the specification, p has the constant p.id, the variables p.leader (of label type), as well as p.done and p.isLeader (Booleans, initially False). 2. Process p also has a Boolean variable p.init, initially True. 3. Finally, p uses the variable p.string, a sequence of labels initially empty.

Messages of A k

There are two kinds of messages: x , where x is of label type, and Finish .

Overview of A k

Sequences of Labels. Given any process p of R, we define LSeq(p), to be the infinite sequence of labels of processes, starting at p and continuing counterclockwise forever:

LSeq(p i ) = p i .id, p i-1 .id, p i-2 .id . . . , where subscripts are modulo n.

For example, if the ring has three processes where p 0 .id = p 1 .id = A and p 2 .id = B, then LSeq(p 0 ) = ABAABA . . . For any sequence of labels σ, we define σ |t as the prefix of σ of length t, and σ[i], for all i ≥ 1, as the i th element (starting from the left) of σ.

If σ is an infinite sequence (resp. a finite sequence of length λ), we say that

π = σ |m is a repeating prefix of σ if σ[i] = π[1 + (i -1) mod m] for all i ≥ 1 (resp. for all 1 ≤ i ≤ λ).
Informally, if σ is infinite, then σ is the concatenation πππ . . . of infinitely many copies of π, otherwise σ is the truncation at length λ of the infinite sequence πππ . . .

Let srp(σ) be the repeating prefix of σ of minimum length. As R is asymmetric, we have: Lemma 8. Let p be a process and let m ∈ {2n, . . . , ∞}. The length of srp(LSeq(p) |m ) is n.

Proof. Let s be the smallest length of any repeating prefix of σ. LSeq(p) |n is a repeating prefix of σ and thus s is defined, and s ≤ n. If s < n, then the rotation by s is a non-trivial rotational symmetry of R, contradicting the hypothesis that R is asymmetric.

The next lemma shows that any process p can fully determine R, i.e., p can determine n, as well as the labeling of R, from any prefix of LSeq(p), provided that prefix contains at least 2k + 1 copies of any label. Lemma 9. Let p be a process, m > 0 and be a label. If LSeq(p) |m contains at least 2k + 1 copies of , then R is fully determined by LSeq(p) |m .

Proof. We note π = LSeq(p) |m and assume that it contains at least 2k + 1 copies of . First, m > 2n. Indeed, there are at most k copies of in any subsequence of LSeq(p) of length no more than n, by definition of K k . So, at most 2k copies of in any subsequence of length no more than 2n. Then, by Lemma 8, srp(π) = LSeq(p) |n . Hence, one can compute srp(π): its length provides n and its contents is exactly the counterclockwise sequence of labels in R, starting from p.

True Leader. We define the true leader of R as the process L such that LSeq(L) |n is a Lyndon word [START_REF] Lyndon | On burnside's problem[END_REF], i.e., a non-empty string that is strictly smaller in lexicographic order than all of its rotations. In the following, we note LW (σ) the rotation of the sequence σ which is a Lyndon word. In Algorithm A k (see Algorithm 2), the true leader will be elected. Precisely, in A k , a process p uses the variable p.string to save a prefix of LSeq(p) at any step: p.string is initially empty and consists of all the labels that p has learnt during the execution of A k so far. Lemma 9 shows how p can determine the label of the true leader. Indeed, if p.string contains at least 2k + 1 copies of some label, srp(p.string) = LSeq(p) |n . If srp(p.string) = LW (srp(p.string)), then p is the true leader. Otherwise, the label of the true leader is the first label of LW (srp(p.string)), i.e., LW (srp(p.string)) [START_REF] Angluin | Local and global properties in networks of processors[END_REF].

In A k , we use the function Leader(σ) which returns True if the sequence σ contains at least 2k + 1 copies of some label and srp(σ) = LW (srp(σ)), False otherwise.

Phases of A k . A k consists of two phases, which we call the string growth phase and the finishing phase.

During the string growth phase, each process p builds a prefix of LSeq(p) in p.string. First, p initiates a token containing its label, and also initializes p.string to p.id (A1-action). The token moves around the ring repeatedly until the end of the string growth phase. When p receives a label, p executes A2-action to append it to its string, and sends it to its right neighbor. Thus, each process keeps growing p.string.

Eventually, L receives a label x such that L.string • x is long enough for L to determine that it is the leader, see Lemma 9 and the definition of function Leader. In this case, L executes A3-action: L appends L.string with x, ends the string growth phase, initiates the finishing phase by electing itself as leader, and sends the message Finish to its right neighbor. The message Finish traverses the ring, informing all processes that the election is over. As each process p receives the message (A4-action), it knows that a leader has been elected, can determine its label, LW (srp(p.string)) [START_REF] Angluin | Local and global properties in networks of processors[END_REF], and then halts. Meanwhile, L consumes every token (A5-action). When Finish returns to L, it executes A6-action to halt, concluding the execution of A k .

Correctness and Complexity Analysis

Theorem 7. A k solves the process-terminating leader election for A ∩ K k , for every given k ≥ 1.

Proof. Let M = max {mlty( ) : is a label in R} and m = (2k + 1)/M n. After receiving at most m messages containing labels (the messages cannot be discarded before the election of a leader, A5-action), by Lemma 9, every process will know R completely. Hence, by definition, L can determine that it is the true leader. As soon as L realizes that it is the leader, it will execute A3-action, sending the message Finish around the ring.

Every process but L will receive the message Finish and execute A4-action, which will be its final action. Finally L executes A6-action, ending the execution. So A k solves the process-terminating leader election for A ∩ K k . Theorem 8. A k has time complexity at most (2k + 2)n, has message complexity at most (2k + 1)n 2 + n, and requires at most (2k + 1)nb + 2b + 3 bits in each process.

Proof. Let M = max {mlty( ) : is a label in R} and m = (2k + 1)/M n. After at most m time units, L can determine that it is the true leader and send a message Finish . In n additional time units, Finish traverses the whole ring and comes back to L to conclude the execution. In the worst case, there are no duplicate labels, i.e., M = 1. Hence, the time complexity of A k is at most (2k + 2)n time units.

When the execution halts, all sent messages have been received. So, the number of message sendings is equal to the number of message receptions. Each token initiated at the beginning of the growing phase circulates in the ring until being consumed by L after it realizes that it is the true leader. Similarly, Finish traverses the ring once and stopped at L. Hence, each process receives at most as many messages as L. L receives 2k + 1 messages with the same label x to detect that it is the true leader (A3-action). When L becomes leader, the received token x is consumed and L has received messages containing other labels (at most n -1 different labels) at most 2k times each. Then, L receives and consumes all other tokens (at most n -1) before receiving Finish . Overall, L receives at most (2k + 1)n + 1 messages and so, the message complexity is at most (2k + 1)n 2 + n.

From the previous discussion, the length of L.string is bounded by 2kn + 1. If p = L, then p.string continues to grow after L executes A3-action until p executes A4-action by receiving the message Finish . Now, the FIFO property ensures that p.string is appended at most n -1 times more than L.string due to the remaining tokens. Thus the length of p.string is always less than (2k + 1)n. So, the space complexity is at most (2k + 1)nb + 2b + 3 bits per process.

Algorithm B k

We now give another solution, Algorithm B k , to the process-terminating leader election for the class A∩K k , with fixed k ≥ 1. The space complexity of B k is smaller than that of A k , but its time complexity is greater. The state diagram and the actions of B k are respectively given in Figure 6 and Algorithm 3.

Messages of B k

B k executes by phases. Three kinds of message are exchanged to manage these phases: the token x is used during the computation of a phase, Phase_Shift, x is used to notify that a phase is over, and Finish, x is used during the ending phase, where x is of label type. Intuitively, we say that a process is in its i th phase, with i ≥ 1, if it received i -1 messages Phase_Shift, _ .

Overview of B k

Let k ≥ 1 and R ∈ A ∩ K k . Like A k , B k elects the true leader of R, namely, the process L ∈ R such that LSeq(L) |n is a Lyndon word, i.e., LSeq(L) |n is minimum among the sequences LSeq(q) |n of all processes q ∈ R, where sequences are compared using lexicographical ordering.

During the execution, the processes that are (still) competing to be the leader are the active ones. Initially, the set of active processes contains all processes: Act 0 = {p 0 , ..., p n-1 }. An execution consists of phases where processes are deactivated, i.e., become passive. At the end of a given phase i ≥ 1, the set of active processes is given by: 7. During phase i ≥ 1, a process q is removed from Act i , when LSeq(q)[i] > LSeq(L)[i]; more precisely, when q realizes that some process p

Act i = p ∈ R : LSeq(p) |i = LSeq(L) |i see Figure
∈ Act i-1 satisfies LSeq(p)[i] < LSeq(q)[i]. When i ≥ n, Act i is reduced to {L}, since R is asymmetric. Using k, B k is able
to detect that at least n phases have been done, and so to terminate.

Phase Computation. The goal of the i th phase is to compute Act i , given Act i-1 , namely to deactivate each active process p such that LSeq(p)[i] > LSeq(L) [i]. To that purpose, p assigns p.guest in such way that p.guest = LSeq(p)[i] during phase i. (How p.guest is maintained in each phase will be explained later.)

During phase i ≥ 1, the value p.guest of every active process p circulates among active processes: at the beginning of the phase, every active process sends its current guest to its right neighbor (A1-action for the first phase, A6-action for other phases). Since passive processes are no more candidate, they simply forward the token (A7-action). When an active process p receives a label x greater than p.guest, it discards this value (A2-action), since x > p.guest ≥ LSeq(L) [i]. Conversely, when p is active and receives a label x lower than p.guest, it turns to be passive, executing A4-action; nevertheless, it forwards x. A process p, which is (still) active, can end the computation of its phase i once it has considered the guest value of every other process that are active all along phase i (i.e., processes in Act i-1 that did not become passive during phase i). Such a process p detects the end of the current phase when it has seen its current guest value (i.e., p.guest) k+1 times.

To that goal, we use the counter variable p.inner, which is initialized to 1 at the beginning of each phase (p.inner is initialized to 1 and reset at each A6-action) and incremented each time p receives the value p.guest while being active (A3-action) (once a process is passive the variable inner is meaningless). So, the current phase ends for an active process p when it receives p.guest while p.inner was already equal to k (A5-action).

Phase Switching. We now explain how p.guest is maintained at each phase. Initially, p.guest is set to p.id and phase 1 starts for p (A1-action). Next, the value of p.guest for every p is updated when switching to the next phase.

First, note that it is mandatory that every (active and passive) process updates its guest variable when entering a new phase, i.e., after detecting the end of the previous phase, so that the labels that circulate during the computation of the phase actually represent LSeq(p)[i] for process p ∈ Act i-1 . Now, FIFO links allow to enforce a barrier synchronization as follows.

At the end of phase i ≥ 1, Act i is computed, and every still active process p has the same label prefix of length i, LSeq(p) |i , hence the same value for p.guest = LSeq(p) [i]. They are all able to detect the end of phase i. So, they switch their state from Compute to Shift and signal the end of the phase by sending a token Phase_Shift, p.guest (A5-action).

Tokens Phase_Shift, _ circulate in the ring, through passive processes (A8-action) until reaching another (or possibly the same) active process: when a process p (being passive or active) receives Phase_Shift, x :

1. it switches from phase i to i + 1 by adopting x as new guest value, and 2. if p is passive, it sends Phase_Shift, y where y was its previous guest value; otherwise, the shifting process is done and so p switches p.state from Shift to Compute or Win and starts a new phase (A6-action or A9-action). As a result, all guest values have eventually shifted by one process on the right for the next phase.

Due to FIFO links and the fact that active processes switch to state Shift between two successive phases, phases cannot overlap, i.e., when a label x is considered in phase i by any active process in state Compute, x is the guest of some process q which is active in phase i, such that LSeq(q)[i] = x.

Number of Phases.

Phase switching stops for an active process p once p.guest has shifted k + 1 times to its own label p.id. Indeed, when p.guest is shifted to p.id for the (k + 1) th times, it is guaranteed that the number of phases executed by the algorithm is greater or equal to n, because p.guest = LSeq(p)[i] in phase i and there is no more than k processes with the label p.id. In this case, p is the true leader and every other process q is passive.

To detect this, we use at each process p the counter p.outer. It is initialized to 1 and incremented by each active process p at each phase switching when the new guest value is equal to p.id (A6-action). When p.outer reaches the value k + 1 (or equivalently when p receives Phase_Shift, p.id while p.outer = k, see A9-action), p declares itself as the leader and initiates the final phase: it sends a token Finish, p.id ; each other process successively receives the token (A10-action), saves the label in the token in its leader variable, forwards the token, and then halts. Once the token reaches p again (A11-action), it also halts.

Correctness and Complexity Analysis

Throughout this section, we consider an arbitrary ring R of A ∩ K k , with fixed k ≥ 1. To prove the correctness of B k (Theorem 9), we first establish that its phases are well-defined (see Lemma 10), e.g., they do not overlap. Then, Lemmas 11-16 prove the invariant of the algorithm, by induction on the phase number. Finally, Theorem 10 gives a complexity analysis of B k . (All the proofs below are easier to follow using the state diagram of Figure 6.) A process p is in Phase i ≥ 0 if it shifts i times the value of its variable p.guest: the shift precisely occurs when p executes the assignment of p.guest. Such shifts occur in A1action, A6-action, A9-action, or A8-action. Notice that the three later actions are executed upon the reception of some token Phase_Shift, _ . As we will see below, a barrier synchronization is achieved between each phase using these tokens.

Lemma 10. Let i ≥ 1. A message received in Phase i has been sent in Phase i. Conversely, if a message has been sent in Phase i, it can only be received in Phase i.

Proof. First, we prove some preliminary results. Claim 1: Between two shifts at p.guest, each process p has sent and received at least one message.

Proof of Claim 1: A process p can only update p.guest by executing A1, A6, A8, or A9action. Furthermore, A1-action is always executed first and only once. Assume p updates p.guest in γ i → γ i+1 and later in γ j → γ j+1 . So, p executes A6, A8, or A9-action in γ j → γ j+1 . Now, if p executes A8-action, it receives a message Phase_Shift, _ and sends Phase_Shift, p.guest before updating p.guest during γ j → γ j+1 . If p executes A6 or A9-action, it receives a message Phase_Shift, _ in step γ j → γ j+1 before updating p.guest. Moreover, in that case, the previous action p has executed is necessarily A5-action, so p sent a message Phase_Shift, p.guest between γ i+1 and γ j .

Assume now, by the contradiction, that some process q receives in Phase j ≥ 0 a message m sent by its predecessor p in Phase i ≥ 0 such that i = j. Without loss of generality, assume m is the first message subject to that condition. Claim 2: i ≥ 1 and j ≥ 1 Proof of Claim 2: p cannot send messages before executing A1-action, i.e., before setting p.guest to p.id and starting its first phase. So, i ≥ 1. Similarly, q cannot receive any message before executing A1-action, so j ≥ 1. Now, since m is the first problematic message, by Claim 1 and owing the fact that the links are FIFO, we can deduce that j = i -1 or j = i + 1. Let consider the two cases.

• If j = i + 1, then q updates its guest once more than p. Let consider the last time q updates its guest before receiving m, i.e., the last time q executes A1, A6, A8, or A9-action to switch from its (j -1) th to its j th phase (i.e., to switch from its i th to its j th phase). By Claim 2, i ≥ 1, so j ≥ 2, and so, it does no execute A1-action to switch from its (j -1) th to its j th phase, since A1 is always executed first and only once. Now, if q executes A6, A8, or A9-action, it receives a message m of the form Phase_Shift, _ in Phase j -1. Since m is the first problematic message, m was sent by p in Phase j -1. Either p executes A8-action and switches to Phase j, or p executes A5-action to send m . Now, in this latter case, p necessarily executes A6-action to send the next message after m , and p switches to Phase j before sending that message. In both cases, p switches to Phase j before sending m, a contradiction. • If j = i -1, then p updates its guest once more than q. Let consider the last time p updates its guest before sending m, i.e., the last time p executes A1, A6, A8, or A9-action to switch from its (i -1) th to its i th phase. Let consider each cases:

-If p executes A1-action, then i = 1 since A1 is always executed first and only once. Now, by Claim 2, j ≥ 1, a contradiction. -If p executes A6 or A9-action, it necessarily executes A5-action beforehand and so sends a message m = Phase_Shift, _ to q in Phase i -1. Since m is the first problematic message, q receives m in Phase i -1 executing A6, A8, or A9-action. Either action makes q switching from Phase i -1 to Phase i before receiving m, a contradiction. -If p executes A8-action, it sends a message m = Phase_Shift, _ before switching to phase i. Again, since m is the first problematic message, q receives m in Phase i-1 executing A6, A8, or A9-action. Either action makes q switching from Phase i -1 to Phase i before receiving m, a contradiction. with x = p.id = LSeq(p) [j]. Furthermore, we have that p.outer = k at Phase j. Hence p.id was observed k + 1 times since the beginning of the execution: p.guest shifted k times to the value p.id and the value x in the received message is also p.id. By Lemma 12, the sequence of values of p.guest is equal to LSeq(p) |j-1 . Adding x = LSeq(p)[j] at the end of the sequence, we obtain LSeq(p) |j . Hence, j = min{x : LSeq(p) |x contains p.id (k + 1) times} and n < j (this implies that j ≥ 2, hence j -1 ≥ 1). As p executes A9-action in Phase j, it is active during its whole j th phase and hence exits its phase j -1 using A6-action. By Condition 3 in HI i and since j -1 < i, p ∈ Act j-1 . By definition of Act j-1 , since j > n, Act j-1 = {L}, hence p = L. As a consequence, j = X, a contradiction.

In the following, we show that processes cannot deadlock (Lemma 15).

Lemma 14. While a process is in state Compute (resp. Shift), the next message it has to consider cannot be of the form Phase_Shift, _ (resp. x ).

Proof. Assume by the contradiction that some process p is in state Compute (resp. Shift), but receives an unexpected message Phase_Shift, _ (resp. x ) meanwhile. We only examine the first case, the other case being similar. The unexpected corresponding token may have been transmitted through passive processes to p, but was first initiated by some active process q (A5-action). Since A5-action was enabled at process q, q received k messages q.guest during one and the same phase. By the multiplicity, for at least one of those messages, the corresponding token m was initiated by q using A1 or A6-action. So, m has traversed the entire ring using A3-A5, and A7-actions. Lemma 10 ensures that this traversal occurs during one and the same phase. As a consequence, q.guest ≤ r.guest for every process r that were active when receiving m (none of the aforementioned actions provoke a phase shifting). In particular, q.guest ≤ p.guest.

As q executed A5-action, k messages q.guest were sent by q (one action, either A1 or A6-action, and k -1 A3-actions) during the traversal of m, and so during the same phase again. Hence, p has also received q.guest k times during the same phase. Thus, p.guest ≤ q.guest since p is still active, and so p.guest = q.guest. Now, counters inner of p and q counted accordingly during this phase: p.inner should be greater than or equal to k. Hence p should have executed A5-action before receiving the unexpected message, a contradiction. Lemma 15. For every i ∈ {1, . . . , X -1}, if HI i holds, then ∀p ∈ R, p is not deadlocked before Phase i + 1.

Proof. Let i ∈ {1, . . . , X -1} such that HI i holds. Let p be any process. If p is in state Init or Passive in Phase i, then it cannot deadlock since the states Init and Passive are not blocking by definition of the algorithm. From Lemma 13 since HI i holds, p cannot take state Win before Phase i + 1. Hence, it cannot take state Halt by A11-action. As no A9-action is executed during Phase i, no message Finish, _ circulates in the ring during this phase (Lemma 10): A10-action cannot be enabled, hence p cannot take state Halt by A10-action as well. If p is in state Compute (resp. Shift), it cannot receive any message Phase_Shift, _ (resp. x ) by Lemma 14. Moreover, it cannot have received any message Finish, _ since no such message was sent during this phase (see Lemma 13 which applies as HI i holds). As a conclusion, there is no way for p to deadlock during Phase i. Lemma 16. For every i ∈ {1, . . . , X -1}, if HI i holds, then ∀p ∈ R, ∀j < i+1, p eventually exits Phase j and, p ∈ Act j if and only if p exits its phase j by A6 or A9-action.

Proof. Let i ∈ {1, . . . , X -1} such that HI i holds. Claim 1: ∀p, if p ∈ Act i-1 (resp. / ∈ Act i-1 ), p initiates (resp. does not initiate) a token LSeq(p)[i] (resp. any token) at the beginning of Phase i. Proof of Claim 1: If i = 1, every process p is in Act 0 and starts its phase 1, i.e., its execution, by executing A1-action and sending its label p.id = LSeq(p) [START_REF] Angluin | Local and global properties in networks of processors[END_REF]. Otherwise (i > 1), by Lemma 13, no process can execute A9-action before Phase i + 1. So by HI i , every process p ∈ Act i-1 exits Phase i -1, and so starts Phase i, by executing A6-action and sending its label p.guest = LSeq(p)[i] (Lemma 12). By HI i , if p is not in Act i-1 , p cannot exit Phase i -1 by executing A6-action and so it cannot initiate a token p.id at the beginning of Phase i.

Claim 2: Any process p receives LSeq(L)[i] k times during its phase i. Proof of Claim 2: Consider a token m = LSeq(L)[i] that circulates the ring (at least one is circulating since L ∈ Act i-1 initiates one at the beginning of Phase i, see Claim 1). m is always received in Phase i (see Lemma 10) all along its ring traversal. From HI i and Lemma 15, no process is deadlocked before its phase i + 1. Hence, when m reaches a process in state Passive, it is forwarded (A7-action) and when m reaches a process q in state Compute (with q.guest = LSeq(q)[i] ≥ LSeq(L)[i], by Lemma 12 and definition of L), it is also forwarded unless A5-action is enabled at q. Eventually, A5-action occurs at every process q (at least one, e.g., L) such that LSeq(q)[i] = LSeq(L)[i], since q.inner is initialized to 1 at the beginning of the phase (A1 or A6-action) and incremented if q receives LSeq(q)[i]. Hence, q has received k messages LSeq(L)[i] during the phase.

As a consequence, between any two processes q and q in Act i-1 (in state Compute in Phase i, see HI i ) such that LSeq(q)[i] = LSeq(q )[i] = LSeq(L)[i], k tokens LSeq(L)[i] circulates during phase i; any process between q and q has forwarded them (and so received them).

By HI i , the lemma holds for all j < i. Let now consider the case j = i. If p ∈ Act i , then LSeq(p) |i = LSeq(L) |i and in particular, LSeq(p)[i] = LSeq(L) [i]. As Act i ⊆ Act i-1 , p is active at the end of Phase i -1 and as no A9-action can take place before Phase i + 1 (Lemma 13), p is in state Compute during the computation of Phase i. Since p.guest = LSeq(L)[i] ≤ LSeq(q)[i] for any q ∈ Act i-1 (Lemma 12, definition of L), and as any token x that circulates during the Phase is initiated by some process q ∈ Act i-1 with x = LSeq(q)[i] (HI i and Claim 1), p never executes A4-action during Phase i. Furthermore, p receives k times p.guest during the phase (Claim 2), hence it executes A5-action followed by A6 or A9-action to exit Phase i.

Conclusion and Perspectives

We have studied the leader election problem in unidirectional ring networks with homonym processes. Our results are summarized in Table 1. Our process-terminating algorithm for U * ∩ K k (with k ≥ 1) is asymptotically optimal in both time and memory requirements. We have also proposed two process-terminating algorithms, A k and B k , for the more general class A ∩ K k (with k ≥ 1). A k is asymptotically optimal in time (O(kn)), but requires an important memory requirement (O(knb) bits per process). In contrast, B k is asymptotically optimal in terms of memory requirement (O(log k + b)), but has a higher time complexity (O(k 2 n 2 )).

Short-term Perspectives

Finding the best trade-off process-terminating algorithm for the class A ∩ K k is a direct extension of our work. Furthermore, the amount of bits exchanged in an execution of U k (O((kn + n 2 )b) bits, where b is the number of bits required to store a label) is very close to the lower bound we have proven (Ω(kn + n 2 ) bits). (N.b., it is typically assumed that b = O(log n).) On the contrary, the number of bits exchanged in an execution of A k or B k (respectively O(n 2 (2k + 1)b) and O(k 2 n 2 b)) is greater. Whether or not it is possible to reduce the amount of exchanged information without degrading the other performances of the algorithms is worth investigating.

Long-term Perspectives

An interesting long-term perspective of our work would be to investigate fault-tolerant leader election in homonymous systems. Crash Failures. In the context of crash failures, leader election in fully-identified rings have already been investigated in [START_REF] Biswas | A novel leader election algorithm based on resources for ring networks[END_REF]: after a crash, the topology is re-organized as a ring where the node with the highest calculated priority is elected. Notice that this paper also considers the join of new nodes. Then, to the best of our knowledge, in homonymous crash-prone systems, only the consensus problem has been studied in fully-connected networks; see [START_REF] Delporte-Gallet | Uniform consensus with homonyms and omission failures[END_REF]. However, consensus is easier to solve than leader election in message passing since leader election requires a perfect failure detector, while consensus can be achieved with an unreliable one [START_REF] Park | About the relationship between election problem and failure detector in asynchronous distributed systems[END_REF]. Hence, finding the weakest assumptions under which leader election is solvable in homonymous crash-prone systems is very challenging.

Byzantine Failures. If we address now Byzantine failures (which model malicious process behaviors) in the context of homonymous message passing systems, only results about the consensus problem (also called Byzantine agreement in that context) are available [START_REF] Delporte-Gallet | Tran-The, Byzantine agreement with homonyms[END_REF][START_REF] Delporte-Gallet | Byzantine agreement with homonyms in synchronous systems[END_REF]. Again, consensus is easier to solve than leader election in these settings. Indeed, a perfect Byzantine detector is necessary to solve leader election, while consensus can be performed using an unreliable one [START_REF] Kihlstrom | Byzantine fault detectors for solving consensus[END_REF]. Again, this makes very attractive the problem achieving leader election in homonymous Byzantine-prone systems under weak assumptions.

Rational Processes. Finally, the basic aim of Byzantine processes is to make the election fail, e.g., by electing two processes. Another interesting approach is to consider a coalition of so-called rational processes that try to influence the result of the election, e.g., to elect one member of their group. The problem of election that withstands such collusions has been introduced and investigated as the fair leader election problem in a recent paper [START_REF] Yifrach | Fair leader election for rational agents in asynchronous rings and networks[END_REF]. In particular, authors propose a randomized solution for ring networks which assumes that the processes know the whole set of identifiers. Weakening such an assumption while additionally considering homonymous processes is also a very challenging perspective of our work.

Figure 1 :

 1 Figure1: Illustration of the proof of Lemma 1. In gray, the processes of R n,k that can have received information from q kn of label X within t ≥ 0 time units.

8

 8

Figure 2 :

 2 Figure 2: Ring networks R I and R J where m = 7, I = 8 , 10 , 11 , 13 , 14 , and J = 8 , 10 , 12 , 13 , 14 used in the proof of Theorem 1.

Figure 3 :

 3 Figure 3: Ring network R p I#J where m = 7, p = 3, I = 8 , 10 , 11 , 13 , 14 , and J = 8 , 10 , 12 , 13 , 14 used in the proof of Theorem 1.

  Ring in K 4 .

Figure 4 :

 4 Figure 4: Examples of symmetric ring networks in K k .

Figure 5 :

 5 Figure 5: Example of execution of U k where k = 3. The counter of a process is in the white bubble next to the corresponding node. Gray nodes are passive. p.isLeader = True if there is a star next to the node. The black bubble contains the elected label, p.leader.

3 (a) 1

 31 st phase.

3 (b) 2

 32 nd phase.

3 (c) 3

 33 rd phase.

3 (d) 4

 34 th phase.

Figure 7 :

 7 Figure 7: Extracts from an example of execution of B k where k = 3, showing the active (in white) and passive (in gray) processes at the beginning of each phase. The guest of a process is in the white bubble next to the corresponding node.

  Boolean variable p.done, initially False, such that p.done is eventually True for all p, indicating that p knows that the leader has been elected. More precisely, once p.done becomes True, it will never become False again, .isLeader is equal to True for a unique process , and p.leader is permanently set to .id.6. Every process p eventually halts, i.e., locally decides its termination, after p.done becomes True.

	2. Each process p has a Boolean variable p.isLeader such that, in the terminal configura-
	tion of e, .isLeader is True for a unique process (i.e., the leader).
	3. Every process p has a variable p.leader such that, in the terminal configuration, p.leader =
	.id, where satisfies .isLeader.
	Definition 2 (Process-terminating Leader Election). An algorithm Alg solves the process-
	terminating leader election problem in a ring network R if it solves the message-terminating
	leader election in R and if every execution e of Alg on R satisfies the following additional
	conditions:
	4. For every process p, p.isLeader is initially False and never switched from True to
	False: each decision of being the leader is irrevocable. Consequently, there should be
	at most one leader in each configuration.
	5. Every process p has a

  Initially, all processes are active, and when U k is done, the leader is the only active process. A passive process never becomes active. 4. p.count, an integer in the range 0 . . . k + 1. Initially, p.count = 0. p.count will give to p a rough estimate of the frequency of its label in the ring. 5. p.leader, of label type. When U k is done, p.leader = L.id. 6. p.isLeader, Boolean, initially False, follows the problem specification: eventually,

2. p.init, Boolean, initially True. 3. p.active, Boolean, which indicates that p is active. If ¬p.active, we say p is passive. L.isLeader becomes True and remains True, while, for all p = L, p.isLeader remains False for the entire execution. Algorithm 1: Actions of Process p in Algorithm U k . A1 :: p.init → p.init ← False send p.id, 0 A2

  Algorithm 2: Actions of Process p in Algorithm A k . A1 :: p.init → p.string ← p.id p.init ← False send p.id A2 :: ¬p.init ∧ rcv x ∧ ¬Leader(p.string • x) → p.string ← p.string • x send x A3 :: ¬p.init ∧ rcv x ∧ Leader(p.string • x)

		→ p.string ← p.string • x
	∧ ¬p.isLeader	p.isLeader ← True
		p.leader ← p.id
		p.done ← True
		send Finish
	A4 :: ¬p.init ∧ rcv Finish ∧ ¬p.isLeader	→ p.leader ← LW (srp(p.string))[1]
		p.done ← True
		send Finish
		(halt)
	A5 :: ¬p.init ∧ rcv x ∧ p.isLeader	→ (nothing)
	A6 :: ¬p.init ∧ rcv Finish ∧ p.isLeader	→ (halt)

  Algorithm 3: Actions of Process p in Algorithm B k . Each process p has seven variables. 1. As defined in the specification, p has the constant p.id, the variables p.leader (of label type), as well as p.done and p.isLeader (Booleans, initially False). 2. Process p also maintains a variable p.state ∈ {Init, Compute, Shift, Passive, Win, Halt}, initially equals to Init. If p.state = Passive, then p is said to be passive, otherwise p is said to be active. Notice also that Halt is the terminal state for every process. 3. Finally, p has two counters p.inner and p.outer of range 1 . . . k, both initially equal to 1.

	A1	:: p.state = Init		Init	→ p.state ← Compute Shift A6
				A1		p.guest ← p.id send p.guest A9
	(Computation During a Phase) A2 :: p.state = Compute ∧ rcv x ∧ x > p.guest → (nothing) A3 :: p.state = Compute ∧ rcv x ∧ x = p.guest → p.inner + + p.isLeader A2, A3 Compute Win A5
	A4	∧ p.inner < k :: p.state = Compute ∧ rcv x ∧ x < p.guest → p.state ← Passive send x A4 A11
	(Phase Switching)	A7, A8	Passive	A10	send x Halt p.done
	A5	:: p.state = Compute ∧ rcv x ∧ x = p.guest → p.state ← Shift
	A6	∧ p.inner = k :: p.state = Shift ∧ rcv Phase_Shift, x Figure 6: State diagram of B k . send Phase_Shift, p.guest → p.state ← Compute
		∧ (x = p.id ∨ p.outer < k)		if p.id = x then p.outer + +
						p.guest ← x
						p.inner ← 1
						send p.guest
	(Passive Processes)

A7 :: p.state = Passive ∧ rcv x → send x A8 :: p.state = Passive ∧ rcv Phase_Shift, x → send Phase_Shift, p.guest p.guest ← x (Ending Phase) A9 :: p.state = Shift ∧ rcv Phase_Shift, x → p.state ← Win ∧ x = p.id ∧ p.outer = k p.isLeader ← True p.leader ← p.id p.guest ← p.id send Finish, p.id A10 :: p.state = Passive ∧ rcv Finish, x → p.state ← Halt p.leader ← x p.done ← True send Finish, x (halt) A11 :: p.state = Win ∧ rcv Finish, x → p.state ← Halt p.done ← True (halt) 7.1. Variables of B k

Table 1 :

 1 (k + 1) 2 n 2 ≤ 2k 2 n 2 + (3k + 1)n 2 + (1 -2k)n 2 log k + 3b + 5 Summary of the results.

	Class			Impossibility results
	K k		Message-terminating leader election impossible
	U *		Process-terminating leader election impossible
	A		Process-terminating leader election impossible
	Class Time (process-terminating)	Bits exchanged (message-terminating)
	U * ∩ K k	Ω(kn)	Ω(kn + n 2 )
	A ∩ K k	Ω(kn)	Ω(kn + n 2 )
	Class Algorithm	Time	Messages	Memory
	U * ∩ K k	U k	≤ (k + 2)n	≤ 3n 2 + (k -1)n	log(k + 1) + 2b + 4
	A ∩ K k	A k B k	≤ (2k + 2)n ≤	≤ (2k + 1)n 2 + n	2(k + 1)nb + 2b + 3

This work has been partially supported by the anr projects Descartes (ANR-16-CE40-0023) and Estate (ANR-16-CE25-0009).

Conversely, if p /

∈ Act i , it may be or not in Act i-1 . If p / ∈ Act i-1 , then from HI i , p exits Phase i -1 by A8-action; it remains in state Passive all along Phase i and can only exit Phase i by A8-action. Otherwise, p ∈ Act i-1 , i.e., LSeq(p) |i-1 = LSeq(L) |i-1 but LSeq(p)[i] > LSeq(L) [i]. p executes A4-action at least when receiving the first occurrence of LSeq(L)[i] (Claim 2) and takes state Passive. Once p is passive, it remains so and can only exit Phase i using A8-action.

Finally, at least L eventually executes A5-action: the phase switching occurs (started by L or another process) causing all processes to exit Phase i.

This ends the proof of Lemma 11.

Theorem 9. B k solves the process-terminating leader election for A ∩ K k .

Proof. By Lemma 11 and definition of X, Phase X eventually starts and L is the only process that exits Phase X executing A6 or A9-action. Now, by Lemma 11 and Corollary 6, ∀i ∈ {1, . . . , X}, L.guest = LSeq(L)[i] during Phase i. Hence, when L begins its X th phase, it is the (k + 1) th time that it sets L.guest to L.id. Since L.outer is initialized to 1 and incremented when L enters a new phase with L.guest = L.id, L enters its phase X by A9action. So, L sends a token Finish, L.id . L also sets L.isLeader and L.leader to True and L.id, resp. Every other process p receives the token in Phase X (Lemma 10) while being in state Passive, since p exits its (X -1) th phase executing A8-action (Lemma 11). So, p saves L.id in its variable leader, then transmits the token to its right neighbor, and finally halts (A10-action). Eventually L receives the token and halts (A11-action).

Theorem 10. B k has time complexity at most (k + 1) 2 n 2 , message complexity at most 2k 2 n 2 + (3k + 1)n 2 + (1 -2k)n, and requires 2 log k + 3b + 5 bits per process.

Proof. A phase ends when an active process sees its guest k + 1 times. This requires (k + 1)n time units. There is exactly X phases and X ≤ (k + 1)n. Thus, the time complexity of B k is at most (k + 1) 2 n 2 .

During the first phase, every process starts by sending its id. Since a phase involves at most (k + 1)n actions per process, each process forwards labels at most (k + 1)n times. Finally, to end the first phase, every process sends and receives Phase_Shift, _ . Hence, at most (k + 1)n 2 + n messages are sent during the first phase. Moreover, only processes that have the same label as L (at most k) are still active after the first phase.

For every phase i > 1, let d = mlty(min{p.guest : p ∈ Act i-1 }). When phase i starts, every active process (at most k) sends its new guest. When the first message ends its first traversal (kn messages), every process that becomes passive in the phase is already passive. Then, the variables inner of the remaining active processes increment of d each tour of ring by a message. So the remaining messages (at most d) do at most k d traversals (n hops): at most kn messages. Overall, the phase requires at most 2kn messages exchanged. As there is at most (k + 1)n -1 phases after the first one, overall there are at most 2k 2 n 2 + (3k + 1)n 2 + (1 -2k)n messages exchanged.

Finally, for every process p, p.inner and p.outer are initialized to 1 and they are never incremented over than k. Hence, every process requires 2 log k + 3b + 5 bits.