{'fraction_non_alphanumeric': 0.046511627906976744, 'fraction_numerical': 0.006522252390508795, 'mean_word_length': 3.9709528350326413, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Compact Deterministic Self-Stabilizing Leader Election: The Exponential Advantage of Being Talkative

This paper focuses on compact deterministic self-stabilizing solutions for the leader election problem. When the protocol is required to be \emph{silent} (i.e., when communication content remains fixed from some point in time during any execution), there exists a lower bound of Omega(\log n) bits of memory per node participating to the leader election (where n denotes the number of nodes in the system). This lower bound holds even in rings. We present a new deterministic (non-silent) self-stabilizing protocol for n-node rings that uses only O(\log\log n) memory bits per node, and stabilizes in O(n\log^2 n) rounds. Our protocol has several attractive features that make it suitable for practical purposes. First, the communication model fits with the model used by existing compilers for real networks. Second, the size of the ring (or any upper bound on this size) needs not to be known by any node. Third, the node identifiers can be of various sizes. Finally, no synchrony assumption, besides a weakly fair scheduler, is assumed. Therefore, our result shows that, perhaps surprisingly, trading silence for exponential improvement in term of memory space does not come at a high cost regarding stabilization time or minimal assumptions.


Introduction
This paper is targeting the issue of designing efficient self-stabilization algorithm for the leader election problem. Self-stabilization [15,16,32] is a general paradigm to provide forward recovery capabilities to distributed systems and networks. Intuitively, a protocol is self-stabilizing if it is able to recover from any transient failure, without external intervention. Leader election is one of the fundamental building blocks of distributed computing, as it enables to distinguish a single node in the system, and thus to perform specific actions using that node. Leader election is especially important in the context of self-stabilization as many protocols for various problems assume that a single leader exists in the system, even when faults occur. Hence, a self-stabilizing leader election mechanism enables to run such protocols in networks where no leader is a priori given, by using simple composition techniques [16].
Most of the literature in self-stabilization is dedicated to improving efficiency after failures occur, including minimizing the stabilization time, i.e., the maximum amount of time one has to wait before recovering from a failure. While stabilization time is meaningful to evaluate the efficiency of an algorithm in the presence of failures, it does not necessarily capture the overhead of self-stabilization when there are no faults [1], or after stabilization. Another important criterion to evaluate this overhead is the memory space used by each node. This criterion is motivated by two practical reasons, that we detail below.
First, self-stabilizing protocols require that some communications carry on forever (in order to be able to detect distributed inconsistencies due to transient failures [7,14]). Therefore, minimizing the memory space used by each node enables to minimize the amount of information that is exchanged between nodes. Indeed, protocols are typically written in the state model, where the state of each node is read by each of its neighbors. (The use of the state model is motivated by the fact that all existing stabilization-preserving compilers [4,11,12,31] are precisely designed for this model).
Second, minimizing memory space enables to significantly reduce the cost of redundancy when mixing self-stabilization and replication, in order to increase the probability of masking or containing transient faults [22,23]. For instance, duplicating every bit three times at each node permits to withstand one randomly flipped bit. More generally, decreasing the memory space allows the designer to duplicate this memory many times, in order to tolerate many random bit-flips.
A foundational result regarding memory space in the context of self-stabilization is due to Dolev et al. [17], which states that, n-node networks, Ω(log n) bits of memory are required for solving global tasks such as leader election. Importantly, this bound holds even for the ring.
A key component of this lower bound is that the protocol is assumed to be silent. (Recall that a protocol is silent if each of its executions reaches a point in time beyond which the registers containing the information available at each node do not change). The lower bound can be extended to non-silent protocols, but only for protocols with restricted capabilities. For instance, it holds in anonymous (and uniform) unidirectional rings, even of prime size [8,21]. As a matter of fact, most deterministic self-stabilizing leader election protocols [2,3,5,13,18] use at least Ω(log n) bits of memory per node. Indeed, either these protocols directly compare node identifiers (and thus communicate node identifiers to neighbors), or they compute some variant of a hop-count distance to the elected node (and this distance can be as large as Ω(n) to be accurate).
A few previous work [26,27,30] managed to break the Ω(log n) bits lower bound for the memory space of self-stabilizing leader election algorithms. Nevertheless, the corresponding algorithms exhibit shortcomings that hinder their relevance to practical applications. For instance, the algorithm by Mayer et al. [30], by Itkis and Levin [26], and by Awerbuch and Ostrovstky [6] use a constant number of bits per node only. However, these algorithms guarantee probabilistic self-stabilization only (in the Las Vegas sense). In particular, the stabilization time is only expected to be polynomial in the size of the network. Moreover, these algorithms are designed for a communication model that is more powerful than the classical state model used in this paper. (The state model is the model used in most available compilers for actual networks [4,11,12,31]). More specifically, Mayer et al. [30] use the message passing model, and Awerbuch and Ostrovsky [6] use the link-register model, where communications between neighboring nodes are carried out through dedicated registers. Finally, Itkis and Levin [26] use the state model augmented with reciprocal pointer to neighbors. In this model, not only a node u is able to distinguish a particular neighbor v (which can be done using local labeling), but also this distinguished neighbor v is aware that it has been selected by u. Implementing this mutual interaction between neighbors typically requires distance-two coloring, link coloring, or two-hops communication. All these techniques are impacting the memory space requirement significantly [29]. It is also important to note that the communication models in [6,26,30] allow nodes to send different information to different neighbors, while this capability is beyond the power of the classical state model. The ability to send different messages to different neighbors is a strong assumption in the context of self-stabilization. It anables to construct a "path of information" that is consistent between nodes. This path is typically used to distribute the storage of information along a path, in order to reduce the information stored at each node. However, this assumption prevents the user from taking advantage of the existing compilers. So implementing the protocols in [6,26,30] to actual networks requires to rewrite all the codes from scratch.
To our knowledge, the only deterministic self-stabilizing leader election protocol using sublogarithmic memory space in the classical state model is due to Itkis et al. [27]. Their elegant algorithm uses only a constant number of bits per node, and stabilizes in O(n 2 ) time in n-node rings. However, the algorithm relies on several restricting assumptions. First, the algorithm works properly only if the size of the ring is prime. Second, it assumes that, at any time, a single node is scheduled for execution, that is, it assumes a central scheduler [20]. Such a scheduler is far less practical than the classical distributed scheduler, which allows any set of processes to be scheduled concurrently for execution. Third, the algorithm in [27] assumes that the ring is oriented. That is, every node is supposed to possess a consistent notion of left and right. This orientation permits to mimic the behavior of reciprocal pointer to neighbors mentioned above. Extending the algorithm by Itkis et al. [27] to more practical settings, i.e., to non-oriented rings of arbitrary size, to the use of a distributed scheduler, etc, is not trivial if one wants to preserve a sub-logarithmic memory space at each node. For example, the existing transformers enabling to enhance protocols designed for the central scheduler in order to operate under the distributed scheduler require Θ(log n) memory at each node [20]. Similarly, self-stabilizing ringorientation protocols exist, but those preserving sub-logarithmic memory space either works only in rings of odd size for deterministic guarantees [24], or just provide probabilistic guarantees [25]. Moreover, in both cases, the stabilization time is O(n 2 ), which is quite large.
To summarize, all existing self-stabilizing leader election algorithm designed in a practical communication model, and for rings of arbitrary size, without a priori orientation, use Ω(log n) bits of memory per node. Breaking this bound, without introducing any kind of restriction on the settings, requires, beside being non-silent, a completely new approach.

Our results
In this paper, we present a deterministic (non-silent) self-stabilizing leader election algorithm that operates under the distributed scheduler in non-anonymous undirected rings of arbitrary size. Our algorithm is non-silent to circumvent the lower bound Ω(log n) bits of memory per node in [17]. It uses only O(log log n) bits of memory per node, and stabilizes in O(n log 2 n) time.
Unlike the algorithms in [6,26,30], our algorithm is deterministic, and designed to run under the classical state-sharing communication model (a.k.a. state model), which allows it to be implemented by using actual compilers [4,11,12,31]. Unlike [27], the size of the ring is arbitrary, the ring is not assumed to be oriented, and the scheduler is distributed. Moreover the stabilization time of our algorithm is significantly smaller than the one in [27]. Similarly to [6,26,28,30], our algorithm uses a technique to distribute the information among nearby nodes along a sub-path of the ring. However, our algorithm does not rely on powerful communication models such as the ones used in [6,26,30]. Those powerful communication models make easy the construction and management of such sub-paths. The use of the classical state-sharing model makes the construction and management of the sub-paths much more difficult.
Besides the use of a sub-logarithmic memory space, and beside a quasi-linear stabilization time, our algorithm possesses several attractive features. First, the size (or any upper bound for this size) need not to be known by any node. Second, the node identifiers (or identities) can be of various sizes (to model, e.g., Internet networks running different versions of IP). Third, no synchrony assumption besides weak fairness is assumed (a node that is continuously enabled for execution is eventually scheduled for execution).
At a high level, our algorithm is essentially based on two techniques. One consists in electing the leader by comparing the identities of the nodes, bitwise, which requires special care, especially when the node identities can be of various sizes. The second technique consists in maintaining and merging trees based on a parenthood relation, and verifying the absence of cycles in the 1-factor induced by this parenthood relation. This verification is performed using small memory space by grouping the nodes in hyper-nodes of appropriate size. Each hypernode handles an integer encoding a distance to a root. The bits of this distance are distributed among the nodes of the hyper-nodes to preserve a small memory per node. Difficulties arise when one needs to perform arithmetic operations on these distributed bits, especially in the context where nodes are unaware of the size of the ring. The precise design of our algorithm requires overcoming many other difficulties due to the need of maintaining correct information in an environment subject to arbitrary faults.
In addition, we took care of designing our algorithm to be ready for implementation, i.e., we do not only describe a conceptual protocol, but also produce a concrete self-stabilizing leader election protocol. This article provides a high level description of our algorithm, a detailed description of the protocol, and a complete proof of correctness. 1 To sum up, our result shows that, perhaps surprisingly, trading silence for exponential improvement in term of memory space does not come at a high cost regarding stabilization time, neither it does regarding minimal assumptions about the communication framework. 1 Moreover, the reader is invited to consult www-npa.lip6.fr/˜blin/Election/ where a video of the dynamic execution of the protocol is presented. This video is the result of a complete implementation of the protocol. The video execution is using a randomized distributed scheduler. The initial configuration is illegitimate, and the video displays the protocol operation towards a legitimate configuration.

Model and definitions 2.1 Program syntax and semantics
A distributed system consists of n processors that form a communication graph. The processors are represented by the nodes of this graph, and the edges represent pairs of processors that can communicate directly with each other. Such processors are said to be neighbors. This classical model is called state-sharing communication model. The distance between two processors is the length (i.e., number of edges) of the shortest path between them in the communication graph. Each processor contains variables, and rules. A variable ranges over a fixed domain of values. A rule is of the form label : guard −→ command .
A guard is a boolean predicate over processor variables. A command is a set of variableassignments. A command of processor p can only update its own variables. On the other hand, p can read the variables of its neighbors. An assignment of values to all variables in the system is called a configuration. A rule whose guard is true in some system configuration is said to be enabled in this configuration. The rule is disabled otherwise. An atomic execution of a subset of enabled rules results in a transition of the system from one configuration to another. This transition is called a step. A run of a distributed system is a sequence of transitions.

Schedulers
A scheduler, also called daemon, is a restriction on the runs to be considered. The schedulers differ among them by different execution semantics, and by different fairness in the activation of the processors [20]. With respect to execution semantics, we consider the least restrictive scheduler, called the distributed scheduler. In the run of a distributed scheduler, a step can contain the execution of an arbitrary subset of enabled rules of correct processors. With respect to fairness, we use the least restrictive scheduler, called weakly fair scheduler. In every run of the weakly fair scheduler, a rule of a correct processor is executed infinitely often if it is enabled in all but finitely many configurations of the run. That is, the rule has to be executed only if it is continuously enabled. A round is the smallest portion of an execution where every process has the opportunity to execute at least one action.

Predicates and specifications
A predicate is a boolean function over network configurations. A configuration conforms to some predicate R, if R evaluates to true in this configuration. The configuration violates the predicate otherwise. Predicate R is closed in a certain protocol P , if every configuration of a run of P conforms to R, provided that the protocol starts from a configuration conforming to R. Note that if a protocol configuration conforms to R, and the configuration resulting from the execution of any step of P also conforms to R, then R is closed in P .
A specification for a processor p defines a set of configuration sequences. These sequences are formed by variables of some subset of processors in the system. This subset always includes p itself. A problem specification, or problem for short, defines specifications for each processor of the system. A problem specification in the presence of faults defines specifications for correct processors only. Program P solves problem S under a certain scheduler if every run of P satisfies the specifications defined by S. A closed predicate I is an invariant of program P with respect to problem S if every run of P that starts in a state conforming to I satisfies S. Given two predicates l 1 and l 2 for program P with respect to problem S, l 2 is an attractor for l 1 if every run that starts from a configuration that conforms to l 1 contains a configuration that conforms to l 2 . Such a relationship is denoted by l 1 l 2 .
A program P is self-stabilizing [15] to specification S if every run of P that starts in an arbitrary configuration contains a configuration conforming to an invariant of P with respect to problem S. That is, this invariant is an attractor of predicate true.

Leader election specification
Consider a system of processors where each processor has a boolean variable leader. We use the classical definition of leader election, which specifies that, in every protocol run, there is a suffix where a single processor p has leader p = true, and every other processor q = p satisfies leader q = f alse.

A compact leader-election protocol for rings
In this section, we describe our self-stabilizing algorithm for leader election in arbitrary nnode rings. The algorithm is later proved to use O(log log n) bits of memory per node, and to stabilize in quasi-linear time, whenever the identities of the nodes are between 1 and n c , for some c ≥ 1. For the sake of simplicity, we assume that the identifiers are in [1, n]. Nevertheless, the algorithm works without assuming any particular range for the identifiers. We first provide a general overview of the algorithm, followed by a more detailed description in Section 3.2. All predicates and commands are postponed in section 3.3.

Overview of the algorithm
As many existing deterministic self-stabilizing leader election algorithms, our algorithm aims at electing the node with maximum identity among all nodes, and, simultaneously, at constructing a spanning tree rooted at the elected node. The main constraint imposed by our wish to use sub-logarithmic memory is that we cannot exchange or even locally use complete identifiers, as their size Ω(log n) bits does not fit in a sub-logarithmic size memory. As a matter of fact, we assume that every node can access the bits of its identifier, but only a constant number of them can be simultaneously stored and/or communicated to neighbors at any given time.
Our algorithm makes sure that every node stores the current position of a particular bit of the identifier, referred to as a bit-position in the sequel.

Selection of the leader
Our algorithm operates in phases. At each phase, each node that is a candidate leader v reveals some bit-position, different from the ones at the previous phases, to its neighbors. More precisely, let Id v be the identity of node v, and assume that Id v = k i=0 b i 2 i . Let I = i ∈ {0, ..., k}, b i = 0 be the set of all non-zero bit-positions in the binary representation of Id v . Let us rewrite I = {p 1 , ..., p j } with 0 ≤ p 1 < p 2 < ... < p j ≤ k. Then, during Phase i, i = 1, . . . , j, node v reveals p j−i+1 to its neighbors, which potentially propagate it to their neighbors, and possibly to the whole network in subsequent phases. During Phase i, for j + 1 ≤ i ≤ log n + 1, node v either becomes passive (that is, stops acting as a candidate leader) or remains a candidate leader. If, at the beginning of the execution of the algorithm, all nodes are candidate leaders, then during each phase, some candidate leaders are eliminated, until exactly one candidate leader remains, which becomes the actual leader. More precisely, let p max (i) be the most significant bit-position revealed at Phase i among all nodes. Then, among all candidate leaders still competing for becoming leader, only those whose bit-position revealed at Phase i is equal to p max (i) carry on the electing process. The other ones become passive.
If all identities are in [1, n], then the communicated bit-positions are less than log n , and thus can be represented with O(log log n) bits. The difficulty is to implement this simple "compact" leader election mechanism in a self-stabilizing manner. In particular, the nodes may not have same number of bits encoding their identifiers, the ring may not start from a configuration where every node is a candidate leader, and the distributed scheduler may lead nodes to operate at various paces.
An additional problem in self-stabilizing leader election is the potential presence of impostor leaders. If one can store the identity of the leader at each node, then detecting an impostor is easy. Under our memory constraints, nodes cannot store the identity of the leader, nor read entirely their own identifier. So, detecting impostor leaders becomes non trivial, notably when an impostor has an identity whose most significant bit is equal to the most significant bit of the leader. To overcome this problem, the selection of the leader must run perpetually, leading our algorithm to be non-silent.

Spanning tree construction
Our approach to make the above scheme self-stabilizing is to merge the leader election process with a tree construction process. Every candidate leader is the root of a tree. Whenever a candidate leader becomes passive, its tree is merged to another tree, until there remains only one tree. The main obstacle in self-stabilizing tree-construction is to handle an arbitrary initial configuration. This is particularly difficult if the initial configuration yields a cycle rather than a spanning forest. In this case, when the leader election subroutine, and the tree construction subroutine are conjointly used, the presence of the cycle implies that, while every node is expecting to point to a neighbor leading to a leader, there are no leaders in the network. Such a configuration is called fake leader. In order to break cycles that can be present in the initial configuration, we use an improved variant of the classical distance calculation [19]. In the classical approach, every node u maintains an integer variable d u that stores the distance from u to the root of its tree. If v denotes the parent of u, then typically d v = d u − 1, and if d v ≥ d u , then u deletes its pointer to v. If the topology of the network is a ring, then detecting the presence of an initial spanning cycle, instead of a spanning forest, may involve distance variables as large as n, inducing Ω(log n) bits of memory.
In order to use exponentially less memory, our algorithm uses the distance technique but modulo log n. More specifically, each node v maintains three variables. The first variable is an integer denoted by d v ∈ {0, ..., log n }, called the "distance" of node v. Only candidate leaders v can have d v = 0. Each node v maintains d v = 1 + (min{d u , d u } mod log n ) where u and u are the neighbors of v in the ring. Note that nodes are not aware of n. Thus they do not actually use the value log n as above, but a potentially erroneous estimation of it.
The second variable is p v , denoting the parent of node v. This parent is its neighbor w such that d v = 1 + (d w mod log n ). By itself, this technique is not sufficient to detect the presence of a cycle, because the number of nodes can be a multiple of log n . Therefore, we also introduce the notion of hyper-node, defined as follows: The parent of a hyper-node X = {x 1 , x 2 , · · · , x log n } is a hyper-node Y = {y 1 , y 2 , · · · , y log n } such that p x 1 = y log n . By definition, there are at most n/ log n hyper-nodes. If n is not divisible by log n , then some nodes can be elements of an incomplete hyper-node. There can be several incomplete hyper-nodes, but if the parent of a (complete) hyper-node is an incomplete hyper-node, then an error is detected. Incomplete hyper-nodes must be leaves: there cannot be incomplete hyper-nodes in a cycle.
The key to our protocol is that hyper-nodes can maintain larger distance information than simple nodes, by distributing the information among the nodes of a hyper-node. More precisely, we assume that each node v maintains a bit of information, stored in variable dB v . Let X = {x 1 , x 2 , · · · , x log n } be a hyper-node, the set dB X = {dB x 1 , dB x 2 , · · · , dB x log n } can be considered as the binary representation of an integer on log n bits, i.e., between 0 and 2 log n − 1. Now, it is possible to use the same distance approach as usual, but at the hypernode level. Part of our protocol consists in comparing, for two hyper-nodes X and Y , the distance dB X and the distance dB Y . If Y is the parent of X, then the difference between dB X and dB Y must be one. Otherwise an inconsistency is detected regarding the current spanning forest. The fact that hyper-nodes include log n nodes implies that dealing with distances between hyper-nodes is sufficient to detect the presence of a cycle spanning the n-node ring. This is because 2 log n ≥ n/ log n. (Note that hyper-nodes with k nodes such that 2 k ≥ n/k would do the same).
In essence, the part of our algorithm dedicated to checking the absence of a spanning cycle generated by the parenthood relation boils down to comparing distances between hypernodes. Note that comparing distances between hyper-node involves communication at distance Ω(log n). This is another reason why our algorithm is non-silent.

Notations and preliminaries
Let C n = (V, E) be the n-node ring, where V is the set of nodes, and E the set of edges. A node v has access to an unique identifier, but can only access to this identifier one bit at a time, using the Bit(x, v) function, that returns the position of the xth most significant bit equal to 1 in Id v . This position can be encoded with O(log log n) bits when identifiers are encoded using O(log n) bits, as we assume they are. A node v has access to local port number associated to its adjacent edges. The variable parent of node v, denoted by p v , is actually the port number of the edge connecting v to its parent. In case of n-node rings, p v ∈ {0, 1} for every v. (We do not assume any consistency between the port numbers). In a legitimate configuration, the structure induced by the parenthood relation must be a tree. The presence of more than one tree, or of a cycle, correspond to illegitimate configurations. We denote by N v the set of the neighbors of v in C n , for any node v ∈ V .
The variable distance, denoted by d v at node v, takes values in {−1, 0, 1, ..., log n }. We have d v = −1 if all the variables of v are reset. We have d v = 0 if the node v is a root of some tree induced by the parenthood relation. Such a root is also called candidate leader. Finally, d v ∈ {1, ..., log n } if v is a node of some tree induced by the parenthood relation, different from the root. Such a node is also called passive. Note that we only assume that variable d can hold To detect cycles, we use four variables. First, each node maintains the variable dB introduced in the previous section, for constructing a distributed integer stored on an hyper-node. The second variable, Add v ∈ {+, ok, ∅}, is used for performing additions involving values stored distributively on hyper-nodes. The third variable, PL v (for pipeline), is used to send the result of an addition to the hyper-node children of the hyper-node containing v. Finally, the fourth variable, HC v (for Hyper-node Checking), is dedicated to checking the hyper-node bits. Variables PL v and HC v are either empty, or each composed of a pair of variables ( For constructing the tree rooted at the node with highest identity, we use three additional variables. After convergence, we expect the leader to be the unique node with distance zero, and to be the root of an inward directed spanning tree of the ring, where the arc of the tree is defined by the parenthood relation. To satisfy the leader election specifications, we introduce the variable leader v ∈ {0, 1} whose value is 1 if v is the leader and 0 otherwise. Since we do not assume that the identifiers of every node are encoded on the same number of bits, simply comparing the i-th most significant bit of two nodes is irrelevant. So, we use variable B, which represents the most significant bit-position of all the identities present in the ring. This variable is also locally used at each node v as an estimate of log n . Only the nodes v whose variable B v is equal to the most significant bit of the Id v carry on participating to the election. Finally, the variables Bit-Strong, Phase, Bit-Position and Control are the core of the election process. Let r be the root of the tree including node v. Then, the variable Bit-Strong v stores the position of the most significant bit of Id r , variable Phase v stores the current phase number i, variable Bit-Position stores the bit-position of Id r at phase i, and variable Control v stores a boolean dedicated to the control of the updating of the elections variables.

The Compact Leader Election algorithm CLE
Algorithm CLE is presented in Figure 1. In this figure, a rule of the form where command i is performed when guard 0 ∧ guard i is true. Such a rule is presented in several lines, one for the common guard, guard 0 , and one for each alternative guards, guard i , with their respective command. Figure 1 describes the rules of the algorithm.
CLE is composed of six rules: − The rule R Error , detects at node v the presence of inconsistencies between the content of its variables and the content of its neighboring variables. If v has not reset its variables, or has not restarted, the command Reset(v) is activated, i.e., all the content of all the variables at node v are reset, and the variable d v is set to −1. − The rule R Start , makes sure that, if an inconsistency is detected at some node, then all the nodes of the network reset their variables, and restart. Before restarting, every node v waits until all its neighbors are reset or have restarted. A node v that restarts sets d v = 0, and its election variables Bit- when one of its neighbors has a bit-position larger than its bit-position, at the same phase. − The rule R Root , concerns the candidate leaders, i.e., every node v with d v = 0. Such a node can only execute the rule R Root , resulting in that node performing one of the following two commands. Command StartdB(v) results in v distributing the bit dB to its neighboring hyper-nodes. Command Inc(v) results in node v increasing its phase by 1. This happens when all the nodes between v and others candidate leaders in the current tree are in the same phase, with the same election values Bit-Strong v , Bit-Position v , Control v . − The rule R Update , is dedicated to updating the election variables. − The rule R HyperNd , is dedicated to the hyper-nodes distance verification.

Hyper-nodes distance verification
Let us consider two hyper-nodes X and Y with X the parent of Y . Our technique for verifying the distance between the two hyper-nodes X and Y , is the following (see an example on Figure 2). X initiates the verification. For this purpose, X dedicates two local variables at each of its nodes: Add (to perform the addition) and PL (to broadcast the result of this addition inside X). Similarly, Y uses the variable HC for receiving the result of the addition.
The binary addition starts at the node holding the last bit of X, that is node x k with k = B v . Node x k sets Add x k := +. Then, every node in X, but x k , proceeds as follows. For k < k, if the child x k of x k has Add x k = + and dB x k = 1, then x k assigns + to Add x k . Otherwise, if Add x k = + and dB x k = 0, the binary addition at this point does not generate a carry, and thus x k assigns "ok" to Add x k . Since Add x k = ok, the binary addition is considered finished, and x k 's ancestors (parent, grand-parent, etc.) in the hyper-node assign "ok" to their variable Add. However, if the first bit of X (that is, dB x 1 ) is equal to one, then the algorithm detects an error because the addition would yield to an overflow. The result of the hyper-node binary addition is the following: if a node x k has Add x k = ok, then it means that node y k holds the appropriate bit corresponding to the correct result of the addition if and only if dB The binary addition in X is completed when node x 1 satisfies Add x 1 = + or Add x 1 = ok. In that case, x 1 starts broadcasting the result of the addition. For this purpose, it sets PL x 1 = (1, dB y 1 ) where dB y 1 is obtained from Add x 1 and dB x 1 . Each node x i in X, i > 1, then successively perform the same operation as x 1 . While doing so, node x i sets Add x i = ⊥, in order to enable the next verification. When the child of a node x i publishes (d x i , dB x i ), node x i deletes PL x i , in order to, again, enable the next verification. From i = 1, . . . , k, all variables PL x i in X are deleted. When y i sets HC y i [0] = dy i , node y i can check whether the bit in HC y i [1] corresponds to dB y i . If yes, then the verification carries on. Otherwise y i detects a fault.

Leader election and tree construction
As previously mentioned, our leader election protocol simultaneously performs, together with the election of a leader, the construction a tree rooted at the leader. The leader should be the node whose identifier is maximal among all nodes in the ring. Our assumptions regarding identifiers are very weak. In particular, identifiers may be of various sizes, and the total number n of different identifiers is not known to the nodes. In our algorithm, we use the variable B to estimate (to some extent) the logarithm of the network size, and the variable Bit-Strong v to propagate this estimation in the ring. More precisely, B represents the most significant bitposition among all identities present in the ring, and we consider that all the nodes that do not carry the right value of B in their local variables are not consistent. During the execution of the algorithm, only nodes whose identifiers match the most significant bit-position remain candidate leaders. Moreover, only candidate leaders broadcast bit-position during subsequent phases.
Let us now detail the usage of the variables used for the election. For the sake of simplification, we introduce the variable Elec. The variable Elec is equal to a 4-tuple: This variable is essentially meant to represent the current bit-position of the candidate leaders. Bit-Strong v represents the most significant bit-position among all identifiers, which must be in agreement with variable B v to assess the validity of Elec v . The variables Phase v and Bit-Position v of Elec v are the current phase i, and the corresponding bit-position revealed by a candidate leader during phase i, respectively. The comparison of bits-positions is relevant only if these bits-positions are revealed at the same phase. Hence, we force the system to proceed in phases. If, at phase i, the bit-position ρ v of node v is smaller than the bit-position ρ u of a neighboring node u, then node v becomes passive, and v takes u as parent. It is simple to compare two candidate leaders when these candidate leaders are neighbors. Yet, along with the execution of the algorithm, some nodes become passive, and therefore the remaining candidate leaders can be far away, separated by passive nodes. Each passive node is with a positive distance variable d, and is in a subtree rooted at some candidate leader. Let us now consider one such subtree T v rooted at a candidate leader v. Whenever v increases its phase from i to i + 1, and sets the bit-position related to phase i + 1, all nodes u in T v must update their variable Elec u in order to have the same value as Elec v .
At each phase, trees are merged into larger trees. At the end of phase i, all the nodes in a given tree have the same bit-position, and the leaves of the tree inform their parent that the phase is finished. The local variable Control, called control, is dedicated to this purpose. Each leaf assigns 1 to its control variable, and a bottom-up propagation of this control variable eventually reaches the root. In this way, the root learns that the current phase is finished. If the largest identifiers are encoded using log n bits, each phase results in halving the number of trees, and therefore of candidate leaders. So within at most log n phases, a single leader remains. To avoid electing an impostor leader, the (unique) leader restarts the election at the first phase. This is repeated forever. If an arbitrary initial configuration induces an impostor leader , either has not the most significant bit-position in its identifier or this impostor leader has its most significant bit-position equal to the most significant bit-position of the (real) leader. In the former case, the error is detected by a node with the most significant bit-position. In the latter case, error is detected by at least one node (the true leader), because there exists at least one phase i where the bit-position of the leader is superior to the bit-position of the impostor.
The process of leader election and spanning tree construction is slowed down by the hypernode construction and management. When a node v changes its parents, it also changes its variable dB v , in order not to impact the current construction of the tree. The point is that variable dB v should be handled with extra care to remain coherent with the tree resulting from merging different trees. To handle this, every candidate leader assigns bits for its children into its variable PL. More precisely, if a root v has not children, then v publishes the bit for its future children with variable distance equal to one. If root v has children with distance variable equal to one, then v publishes the bit for the children u with d u = 2, and so on, until the distance variable of v becomes B v . On the other hand, a node cannot change its parent if its future new parent does not publish the bit corresponding to its future distance variable. When the hyper-node adjacent to the root is constructed, the hyper-node verification process takes care of the assignment of the bits to the node inside the hyper-node.

Formal description of our algorithm CLE
In the definitions below, the notation b ≡ P is used to define the boolean b, which is true if and only if the predicate P is true.

Commands
Commands for hyper-node distance verification:

Correctness
In this section, we formally prove the correctness of our Algorithm.
Theorem 1 Algorithm CLE solves the leader election problem in a self-stabilizing manner for the n-node ring, in the state model, with a distributed weakly-fair scheduler. Moreover, if the n node identities are in the range [1, n c ] for some c ≥ 1, then Algorithm CLE uses O(log log n) bits of memory per node, and stabilizes in O(n log 2 n) rounds.
The main difficulty for proving this theorem is to prove that CLE can detect any cycle generated by the parenthood relation in the initial configuration, and can, whenever a cycle is detected, remove this cycle. Let Γ be the set of all possible configurations of the ring, under the set of variables described before in the paper. First, we prove that Algorithm CLE detects the presence of "trivial" errors, that is, inconsistencies between neighbors. Second, we prove that, after correcting all the trivial errors (possibly using a reset), CLE converges and maintains configurations free of trivial errors. The set of configurations free of trivial errors is denoted by Γ TEF where TEF stands for "Trivial Error Free". From now on, we assume only configurations from Γ TEF .
The core of the proof regarding proper cycle detection is based on proving the correctness of the hyper-node distance verification process. This verification process is the most technical part of the algorithm, and proving its correctness is actually the main challenge in the way of establishing Theorem 1. This is achieved by using proofs based on invariance arguments.
Once the correctness of the hyper-node distance verification process has been proved, we establish the convergence of Algorithm CLE from an arbitrary configuration in Γ TEF to a configuration without cycles, and where all hyper-node distances are correct. The set of configurations without cycles is denoted by Γ CF (where CF stands for "Cycle Free"). We prove that a configuration is in Γ CF if and only if all hyper-node distances are correct. Once we can restrict ourselves to configurations in Γ CF , we prove the correctness of our mechanisms detecting and removing impostor leaders. We denote by Γ IEF (where IEF stands for "Impostor leader Error Free") the set of configurations with no impostors. Finally, assuming a configuration in Γ IEF , we prove that the system reaches and maintains a configuration with exactly one leader, equal to the node with maximum identity. Moreover, we prove that the structure induced by the parenthood relation is a tree rooted at the leader, and spanning all nodes. We denote by Γ LE the set of configurations where the unique leader is the node with maximum identity. In other words, we prove that CLE is self-stabilizing for Γ LE .
In the statements of the lemmas below, we define predicates on configurations, these predicates are used as attractors toward a legitimate configuration (i.e., a configuration with unique leader). To establish convergence toward attractors, we use potential functions [32], that is, functions that map configurations to non-negative integers, and that strictly decrease after each algorithm command is executed.
Before starting the proofs, let us first define the Predicate Γ LE (Leader Election) that serves as the definition for legitimate configurations. Let L : Γ → N be the function defined by A configuration γ is legitimate for the leader election specification, i.e., satisfies Γ LE , if and only if L(γ) = 1. That is, Γ LE = {γ ∈ Γ : L(γ) = 1}. Now, for the purpose of the proof, let us define Predicate Γ TEF (Trivial Error Free). Let ψ : Γ × V → N be the function defined by: Let Ψ : Γ → N be the function defined by: Note that all nodes are legitimate with respect to Er T (v) if and only if Ψ(γ) = 0. We define Lemma 1 true Γ TEF in one round.
Proof. The predicate Er T (v) is composed of two types of sub-predicates: the ones independent of the local variables of the neighbors, called independent sub-predicates, and the ones based on comparisons with the local variables of the neighbors, called dependent sub-predicates. (See predicate in 3.3.4). The independent sub-predicates are Root, PassNd, and Er MRoot . All other sub-predicates of Er T are dependents. If an independent sub-predicate is true, then Er T (v) is true, and the execution of any command by a neighbor of v has no influence on the predicate Er T (v), which remains true. (Note that if an independent sub-predicate of v is true, then v may have all its neighbors w with Er T (w) equal to false). Let us now consider dependent subpredicates. Let v a node with a dependent sub-predicate sp(v) = true. Then Er T (v) = true, and there is at least one neighbor u of v such that some local variable(s) of u is not consistent with some variable(s) of v. In this case, since the sub-predicate sp is dependent, we also have sp(u) = true, as, if one variable of v is not consistent with the corresponding variable of u, then the converse is also true. Therefore, sp(u) is true, and thus Er T (u) is true as well. As a consequence, nodes u and v can only apply the command Reset. Now let us consider the neighbor w of v distinct from u, and the neighbor y of u distinct from v. The predicates Er T (w) and Er T (y) may be equal to false, in which case w and y can execute a command different from Reset. Nevertheless, the execution of one command by node w or y, or both, cannot modify the variables of v and u. Therefore, the inconsistency between the local variables of v and u remains until one of them apply the reset command.
Let us denote by X the set of nodes v such that Er T (v) = true (see predicate in 3.3.4) and Er T (y) = f alse for every y ∈ N v . Moreover, let us denote by Y the set of nodes v such that Er T (v) = true and there exists y ∈ N v such that Er T (y) = true. Let γ 0 denote the initial configuration of the system. Since the scheduler is weakly fair, all nodes in X are scheduled for execution at round 1. Moreover all nodes in Y are also scheduled at round 1. According to rule R Error (see algorithm in Figure 1), every node v ∈ X ∪ Y executes Reset(v), and thus Er T (v) becomes false for all these nodes as well as for all their neighbors (indeed, if one neighbor of v is reset, then Er T (v) is false). Therefore, the configuration γ 1 at time 1 satisfies Ψ(γ 1 ) = 0.
Thus, starting from any arbitrary initial configuration γ 0 , the system reaches a configuration γ 1 ∈ Γ TEF in just one round.

Proof.
We prove that, starting from a configuration where Γ TEF holds, algorithm CLE preserves that Er Nd (v), Er Phase , Er Bp , Er Control , and Er Mem all remain false. Let us consider these predicates one by one, starting with Er Nd (v). We show that, for all v ∈ V , algorithm CLE keeps predicate Er Nd (v) to false starting from a configuration where Γ TEF . In configuration Γ TEF , each node v has Er Nd (v) = f alse, that is, each node v must satisfy one of the three predicates Root(v), PassNd(v), and maxElec(v). Moreover, if v satisfies PassNd(v) = true, then v must have a correct distance (see the definition of Er d (v)). We consider the different commands that can be executed by the algorithm.
• If a node v executes the command Reset due to a hyper-node distance error, i.e., Er Hyper (v) = true, or to an election error, i.e., Er Elec (v) = true, then the predicate maxElec(v) becomes true, and, as a consequence, Er Nd (v) remains false. Let node u be a neighbor of v. Predicate Er T (u) remains false because u has at least one neighbor that applied the reset command.
• A reset node v, i.e., a node v such that d v = -1 and maxElec(v) = true, can only execute the command Start(v). When this command has been executed, the predicate Root(v) becomes true, and d v becomes null.
• For the command Inc and StartdB, we note that the predicate Root(v) remains true if d v = 0 since no rule modifies the variables used in Root(v).
• A candidate node v, i.e., a node v such that d v = 0 and Root(v) = true, can only execute the command Passive(v). This command is activated if and only if v has a "better" neighbor u = Best(v). In this case, v adjusts d v with respect to d u . As a consequence, we get Er d (v) = f alse. Moreover, when the command Passive(v) has been executed, the predicate Root(v) becomes false, and the predicate PassNd(v) becomes true. Therefore, Er Nd (v) remains false.
• The predicate PassNd(v) remains true because v executes the commands corresponding to R Passive , R Update , or R HyperNd . We examine each of these different commands.
-The commands corresponding to the rule R HyperNd do not change the variables used by PassNd(v) and Er d (v). Hence Er Nd (v) remains false.
-Note that for any two node u and v where u is a child of v, node u can only execute Update(u) after v has executed Update(v). The command Update(v) keeps the predicate PassNd(v) = true because this command does not change the variables leader v , p v , d v , and B v . Moreover, a node v updates its variables according to the predicate We now move on to predicate Er Phase . We show that, for every v ∈ V , algorithm CLE keeps predicate Er Phase (v) = f alse. An error is detected if and only if the difference between the phases of two nodes is larger than one. As before, we consider the different commands that can be executed, one by one, according to the value of d v .
• Let v be a node with d v = −1 and Phase v = 0. In this case, node v can only execute the command Start, which sets v's phase to zero. In accordance with the rule R Start , each neighbor u of v has either reset (i.e., Phase u = 0) or restarted (i.e., Phase u = 1), which keeps Er Phase (v) = f alse.
• Let v be a node with d v = 0 and Phase v = i, for some i ≥ 0. In this case, node v can only execute the command Passive(v) or the command Inc(v). In the latter case, the phase i of v can only be increased if Phase u = i of i + 1 for every neighbor u of v. Therefore, the command Inc(v) maintains Er Phase (v) = f alse. We now consider command Passive(v). When a v node chooses a neighbor u = Best(v) with B u > B v , the phase of u is equal to 1. Let us consider the subtree T r rooted in r, and containing the node v, with possibly v = r. The node r increases its phase i if and only if all its descendants are in phase i, and the neighbors of the leaves of T r are in phase i or i + 1 (see the predicates Wave B and Up Back ). As a consequence, the difference of phases between u = Best(v) and v is at most one. This keeps Er Phase (v) = f alse. If B u = B v , then node u = Best(v) if its phase is the same as v, and its bit-position is greater than the bit-position of v. Therefore, Er Phase (v) remains false.
• Let v be a passive node with d v > 0 and Phase v = i, for some i ≥ 0. Only two commands can change the phase Phase v : the command Passive(v), and the command Update(v).
The command Passive(v) has already be considered in the previous item. Let us thus now consider the command Update(v), and let r be the root of the subtree T r containing v. When r increases its phase, all nodes in T r have their phase equal to i. Let L r be the set of leaves of T r . All nodes u such that u / ∈ T r with u ∈ N x for some x ∈ L r have their phase equal either to i or to i + 1 (this is ensured by the control variable Control v ). As a consequence, if v moves to phase i + 1, then its parent is at phase i + 1. If v ∈ L r , then its children are at phase i. If v ∈ L r then the neighbors of v not in T r remain at phase i or at phase i + 1. Therefore, Er Phase (v) remains false.
We now move on to predicate Er Bp . We show that, for every v ∈ V , algorithm CLE keeps predicate Er Bp (v) = f alse. The predicate Er Bp (v) is satisfied if and only if d v > 0. A node v that is passive at phase i satisfies Er Bp (v) = f alse if and only if v has not "better" neighbor (i.e., Best(v) = ∅), none of its neighbors are at phase i + 1 (i.e., SupPh(v) = ∅), and at least one of its neighbors is at the same phase i with the same bit position as v. Note that, the commands corresponding to the rule R HyperNd do not change the variables used by the predicate Er Bp (v). As a consequence, Er Bp (v) remains false. The only commands that may change Er Bp are commands Update, and Passive. Let us again consider the subtree T r rooted in r containing v, and let i be the current phase of the nodes in T r . Note that, in this case, Er Bp (v) is false because the parent of v has a same phase as v, and the same bit-position as v. If r increases its phase, then the ancestors of v update their phase top-down. Hence, when the parent u of v updates its phase, the predicate SupPh(v) becomes not empty. If r becomes passive, then ancestors of v have a "better" neighbor, and thus they set their variables according to the variables of their "better" neighbors. When the parent u of v executes the command Passive(u), the predicate Best(v) becomes not empty. Hence, in all cases, Er Bp (v) remains false.
We now turn our attention to predicate Er Control . We prove that, for every v ∈ V , algorithm CLE keeps predicate Er Control (v) to false. The boolean Control v can only be modified by the command Update because of predicate T.Update. Control v is used to control the updates of a subtree. Let us consider T the subtree containing v, and let r be the root of T . The updating process starts at node r, and all the descendants of r set their variables Control = 0 top-down. The process ends at the leaves of the subtree T that launch the acknowledgement Control = 1 propagated bottom-up to the root. Hence, when a node v satisfies Control v = 1, all its descendants also satisfy Control = 1, and, conversely, when a node v satisfies Control v = 0, all its ancestors satisfy Control = 0. Therefore, Er Control (v) is kept to false.
Finally, we consider the predicate Er Mem , and prove that, for every v ∈ V , algorithm CLE keeps predicate Er Mem to false. The predicate Er Mem is satisfied if and only if d v ≥ 0. The commands Inc(v), StartdB(v), and Update(v) do not change the variables Add v and HC v . Thus Er Mem (v) remains false. The command Passive is executed during the construction of the spanning tree, when the hyper-nodes are set. Note that a hyper-node does not start the binary addition before it is properly set. When a node v becomes passive with Best(v) = u, the variables Add v and HC v are set to ⊥. As a consequence, the predicate Er MAdd (v) is false. Assume that v joins a hyper-node or that v is the first node of a hyper-node. In both cases, v has no children. Thus, Er PL (v) and Er HC (v) remain false. A neighbor w of v with p w = v has now Best(w) = v. As a consequence the three predicates Er MAdd (w), Er PL (w) and Er HC (w) remain false. We complete the proof by analyzing all commands corresponding to the rule R HyperNd .
• Let us consider the predicate Er MAdd (v) at some node v. In this predicate, Add v is compared to Add u for every child u of v. Only two commands change We now define Predicate Γ CF (for Cycle Free), which ensures that no cycles induced by the p variable remain in the network. Let λ : Γ × V → N be the function defined by: Where X is an hyper-node, and P X is the hyper-node parent of X (recall that dB X is an integer whose binary representation is dB x 1 , . . . , dB x k where k = B). Let Λ : Γ → N be the function defined by: Let φ : Γ × V → N be the function defined by: Let Φ : Γ → N be the function defined by We define Γ CF = {γ ∈ Γ : Ψ(γ) = Φ(γ) = Λ(γ) = 0 and L(γ) > 0}.

Proof.
Let us consider an initial configuration γ 0 ∈ Γ TEF such that the overlay structure induced by the parent variables p v , v ∈ V , forms a cycle C. The cycle C necessarily contains all nodes, which implies that all nodes have non empty pointers parent. Moreover, since γ 0 ∈ Γ TEF , we get that, for every nodes v, leader v = 0. Thus L(γ 0 ) = 0.
Let us assume, for the purpose of contradiction, that Ξ(γ 0 ) = 0. Let Since Ξ(γ 0 ) = 0, we have X = V . Moreover, since C contains all nodes, we have that p v = ∅ for every v ∈ V , and there is at least one node x ∈ X such that p x / ∈ X. This node x satisfies B x = B p x . In this case, PassNd(x) = f alse and Er Nd (x) = true, which contradicts the fact that γ 0 ∈ Γ TEF . Therefore, Ξ(γ 0 ) = 0. Now, let π : Γ × V → N be the function defined by: Beside, let us define the quadruplet We define Γ Π = {γ ∈ Γ : Π(γ) = 0}.
Recall that γ 0 ∈ Γ TEF , Ξ(γ 0 ) = 0, and L(γ 0 ) = 0. Assume for the purpose of contradiction that Π(γ 0 ) = 0. Let A direct consequence of Π(γ 0 ) = 0 is that X = V and |X| < n. Since the cycle C contains all nodes, we have that, for every v ∈ V , p v = ∅, and there is at least one node x ∈ X such that p x / ∈ X. We denote by y = p x the parent of x, and we consider the variables Bit-Strong x , Phase x , Bit-Position x , and Control x .
If |Phase x − Phase y | > 1 then x or y detects an error (see the predicate Er Phase (v)), and thus γ 0 / ∈ Γ TEF . If |Phase x − Phase y | = 1, then, since y / ∈ X, we have Phase x = Phase y + 1. Thus y cannot be a parent of x (see the predicate Coh p ). Thus γ 0 / ∈ Γ TEF . Therefore, Phase x = Phase y .
We now turn our attention to the variable Bit-Position x . If |X| = 1 then Er Bp (x) = true because, on the one hand, x has no neighbors z such that Phase z = Phase x and Bit-Position z = Bit-Position x , and, on the other hand, x has no neighbors z such that Phase z = Phase x + 1 and z = Best x (see predicate Best). Thus, if |X| = 1 then γ 0 / ∈ Γ TEF . Therefore, |X| > 1. Since Phase x = Phase y we have Bit-Position x = Bit-Position y because otherwise y cannot be a parent of x (see the predicate Coh p ). Therefore Bit-Position x = Bit-Position y .
Finally, we consider Control x , and show Control x = Control y . Assume that Control x = Control y . Then |X| > 1 because otherwise Predicate Er Control (x) would be true, in contradiction with γ 0 ∈ Γ TEF . Moreover, if Control y = 1 and Control x = 0, then Er Control (x) = true and Er Control (y) = true, again contradicting γ 0 ∈ Γ TEF . If Control y = 0 and Control x = 1 then let x ∈ X be a descendent of x whose child x / ∈ X. In this case, Control x = 1 and Control x = 0, hence Predicate Er Control (x ) = true, in contradiction with γ ∈ Γ TEF . Therefore Control x = Control y .
Since Bit-Strong x = Bit-Strong y , Phase x = Phase y , Bit-Position x = Bit-Position y , and Control x = Control y , we obtain that y ∈ X, in contradiction with p x / ∈ X. As a consequence, Π(γ 0 ) = 0, which complete the proof of the claim.
An important consequence of Π(γ 0 ) = 0 is that, for every node v, we have Elec v = MaxElec.
Again, the proof is by contradiction, assuming Φ(γ 0 ) = 0. Since L(γ) = 0, there are no candidates for being the root of the tree. Thus Predicate T.Inc(v) = f alse for every node v, and therefore the command Inc(v) cannot be executed at any node v. As a consequence, all nodes are passive (i.e., ∀v ∈ V : PassNd(v) = true). In addition, since Elec v = MaxElec for every v ∈ V , we also get that the commands Passive(v) and Update(v) cannot be executed at any node v. Since Φ(γ 0 ) = 0, there exists at least one passive node v that detects an error between its distance and the distance of its parent (see predicate Er d (v)). Hence, for that node v, the predicates PassNd(v) and Er Nd (v) are both true, which is a contradiction with γ 0 ∈ Γ TEF . Thus Φ(γ 0 ) = 0.
We are now ready to show that, if the initial configuration γ 0 contains a cycle, then Algorithm CLE detects an error in O(n log n) rounds.
Since Φ(γ 0 ) = 0, we necessarily have that n is a multiple of Max B, and that there are n/Max B hyper-nodes. Since all nodes are passive in γ 0 , the only commands that can be executed by some node(s) are related to the distance verification between hyper-nodes, that is Commands BinAdd(v), Broad(v), Verif (v) and CleanM (v). More specifically, the only nodes that can possibly be activated in γ 0 are the nodes v such that For every hyper-node X = (x 1 , x 2 , . . . , x k ), where k = Max B, since the scheduler is weakly fair, predicate T.Add(x k ) = true, and x k executes the command BinAdd(x k ) at round 1. This yields the execution of the binary addition. The binary addition occurs from x k to x 1 , and every node in each hyper-node X eventually takes value "+" or "ok" once Max B rounds has been performed. Now, if dB x 1 = 1 and Add x 1 = +, then an error is detected since the binary addition overflows beyond the limit of Max B bits (see Er MAdd (v)). Node x 1 starts the verification process that propagates from x 1 to x k . Fix any hyper-node X = (x 1 , x 2 , . . . , x k ), and let us denote by Y the hyper-node child of X in the current configuration at round Max B. Node x 1 computes the values of dB y 1 (see the predicate T.Broad, and the command Broad). This value is broadcast from x 1 to x k (see the predicate T.Broad, and the command Broad). Node y 1 checks whether PL x k [1] = dB y 1 . If it is the case, then the verification process for all other nodes in Y carries on (see the predicate T.Verif and the command Verif ). Otherwise y 1 detects an error (see Er Hyper (v)). Thanks to Predicates T.Add, T.Broad, and T.Verif, and to commands BinAdd, Broad, and Verif every node in Y are eventually checked, after an additional Max B rounds. The total number of rounds for checking hypernodes is the following: there are n/ log n hyper-nodes, each hyper-node performs verification in O( log n ) rounds, so the overall process takes O(n log n) rounds.
To sum-up, if the configuration γ 0 contains a cycle, then at least one hyper-node detects an error in a O(n log n) rounds.
Finally, if L(γ 0 ) = 0 in an arbitrary configuration, then the algorithm CLE detects an error in O(n log n) rounds, and, by Lemma 1, the system reaches a configuration in Γ CF .

Lemma 4 Γ CF is closed.
Proof. Let us consider a configuration γ ∈ Γ CF . We already noticed in the proof of Lemma 2 that Algorithm CLE preserves coherent distances (i.e., Φ(γ) = 0), and does not introduce trivial errors (i.e., Ψ(γ) = 0). Moreover, in the proof of Lemma 3, we have explained that the hyper-node distance verification correctly reports errors, if any. The variable dB is only modified by the command Passive. In the sequel, we use the wording "v joins T r " when a node v executes the command Passive, and the pointer p v of v points to a node in the subtree T r rooted at r.
We denote by X the set of candidate nodes. Let us first consider a node v (in X or not), and a root r ∈ X such that d v ≤ log n , and v joins T r when r increases its phase from i − 1 to i, for some i. Thanks to Predicate T.StartdB, and to command StartdB, node r publishes first the bit for the node at distance 1 from r. In other words, PL r = (1, 0). When any node v at distance 1 joins T r , v sets dB v = PL r [1], and then v informs r about the updating of dB by setting PL v = PL r . At this point, r can publish the bit for nodes at distance 2 (i.e., PL r = (2, 0)), and so on until the distance reaches log n . Now, a node v joins T r only if its candidate parent publishes the bit that corresponds to the binary representation of the distance between v and r. In other words, for any node u, if d u = k with k < log n then Bit-Strong u must be equal to k + 1. This enables to maintain Λ(γ) = 0. When k reaches log n , a hyper-node is created. Then, a binary addition process is carried out, and computes the bit for v when v joins T r . This process maintains Λ(γ) = 0, and, as a direct consequence L(γ) remains greater than 0. To conclude, algorithm CLE keeps Ψ(γ) = 0, Φ(γ) = 0, Λ(γ) = 0, and L(γ) > 0.
We now introduce Predicate Γ IEF (for Impostor Error Free), which ensures that the currently elected leader is not an impostor. Let ρ : Γ × V → N be the function defined by: We show that CLE reaches a legitimate configuration with respect to leader election if and only if P(γ) = 0.
Proof. Let us consider first an initial configuration γ ∈ Γ CF . We have observed in lemma 3 that being in Γ CF implies L(γ) > 0. Let us denote by * the node with maximum identity, and X the set of the candidate nodes. Let us suppose that * ∈ X. Let us denote by the node with the maximum identity in X. In the worst case, all the sub-spanning tree merge in a unique spanning tree rooted at . Thus, let us suppose that γ is a configuration where the network is spanned by an unique tree rooted in . In this case d = 0 and d u > 0 for every node u = .
Let us assume, for the purpose of contradiction, that P(γ) = 0. If the tree is rooted at , then every node must have the same B as . Since is a root, B = Bit(1, Id ). Hence, B = maxFB (because P(γ) = 0). Now, B cannot be larger than maxFB, so there exists v such that B v = maxFB, and PassNd(v) is true. This contradicts γ ∈ Γ TEF , so we can conclude that P(γ) = 0.
Since and * have the same number of bits, there must exist one phase where the bitposition of * is larger than the bit-position of . More formally, there exists i, 1 < i ≤ log n +1, such that, for every j < i, we have Bit(j, Id ) = Bit(j, Id * ), and, for every k ≥ i, we have Bit(k, Id ) < Bit(k, Id * ). Note that i > 1, because, in Γ TEF , predicate PassNd must be true. The worst case with respect to time complexity is for i = log n + 1, and the arbitrary initial configuration starts at phase 2. In this case, only R Root can be activated for , and only the rule R Node for the other nodes (in parallel to the hyper-node distance verification). Node executes the command Inc( ) for log n + 1 − 2 times. After each execution of command Inc, every node executing this command updates the variable Elec in a top-down manner (see Predicate T.Update and command Update). This updating process takes at most n rounds. When all nodes have the same election values, a bottom-up control process is initiated (see Predicate T.Update and command Update). This process takes at most n rounds. After that, increases its phase, and the same process is repeated. At the last phase, Er Elec ( * ) is true, and an error is detected. Therefore, if the system contains a impostor leader, then an error is detected in O(n log n) rounds.
Proof. Let γ ∈ Γ IEF , with L(γ) > 0. Let X be the set of candidate leaders (i.e., for every x ∈ X, Root(x) = true). Let x ∈ X, and let T (x,i) be the subtree rooted at x during phase i. For a node v ∈ T (x,i) , we have that (1) either Bit-Strong v < Bit-Strong x or Bit-Strong v = Bit-Strong x , and (2) Bit(j, Id v ) < Bit(j, Id x ) for every j ≤ i. Moreover, for any two candidates leaders x 1 and x 2 , we have that, at phase i, Bit-Strong x 1 = Bit-Strong x 2 , and Bit(j, Id x 1 ) = Bit(j, Id x 2 ) for evry j ≤ i. Let i be such that T (x 1 ,i) and T (x 2 ,i) have adjacent nodes. Let x 1 ∈ T (x 1 ,i) and x 2 ∈ T (x 2 ,i) be two nodes such that x 1 is adjacent to x 2 . If, at phase i + 1, Bit(i + 1, Id x 1 ) > Bit(i + 1, Id x 2 ), then the nodes of T (x 1 ,i) and T (x 2 ,i) activated by Predicate T.Update executes Update. When node x 1 reaches Elec x 1 at phase i + 1, node x 2 becomes passive (cf. command Passive) and selects node x 1 as its parent. In a bottom-up fashion, every node of T (x 2 ,i) joins the subtree T (x 1 ,i+1) (cf. command Passive), and, eventually, x 2 becomes passive and joins T (x 1 ,i+1) . By this process, for every node v in T (x 1 ,i+1) , we have (1) either Bit-Strong v < Bit-Strong x 1 or Bit-Strong v = Bit-Strong x 1 , and (2) Bit(j, Id v ) < Bit(j, Id x 1 ) for every j ≤ i + 1. This process is repeated until phase log n , where there remains a single leader in the network.
Note that if a node executes Reset, and since the scheduler is weakly fair, at most n rounds later all nodes have executed Reset.

Conclusion
In this paper, we have shown that, in the state model, with a weakly fair distributed scheduler, one can elect a leader in a ring with a (non-silent) self-stabilizing algorithm using only O(log log n) bits of memory per node. It is known that one cannot do the same using only O(1) bits of memory per node (see [8]). An intriguing question is whether one can perform leader election in the same framework as in this paper, using just o(log log n) bits per node, and, if yes, to what extend can the memory requirement for (non silent) leader election being reduced. A natural candidate function for the minimum memory requirement for leader election is O(log * n) bits per node, by applying the techniques in this paper recursively. This however seems to be non trivial, as self-stabilization has to be maintained at every level of the recursion.