R. Root and R. Rootdb, They are enabled at any node v with Root(v, ? 0 ) = true (see leader v = 1 in the guard of R Root ) Executing Inc(v) (see Formula (24)) or StartdB(v) (see Formula (49)) maintains leader v = 1. Thanks to Remarks 2 and 4, we obtain the fact that Er T (v, ? 1 ) (see Formula (52)) remains false, These rules are detailed in Subsections 4.3.4 So, starting in a configuration in ? 0 ? ? TEF , after execution of command Inc(v), predicate Er T (v, ? 1 ) remains false

R. Passive, This rule is detailed in Subsection 4.3.3. Remark 5: Executing command Pass(v) (see Formula (14)) deletes the hyper-nodes variables of v. As a consequence, the following predicates become false: Er Add (v, ? 1 )(see Formula (36), Er PL (v, ? 1 )(see Formula (43)), and Er HC (v, ? 1 ) (see Formula (48))

R. Hypbroad, This rule is detailed in Subsection 4.4.2. Command Pipe(v) (see Formula (42)) modifies variables PL v and HC v

F. Moreover and . Every-node-v-=-l-*, we have par v = ?, and the structure induced by the pointers par v , for all v = L * forms a spanning tree rooted at L * . Regarding time complexity, our algorithm takes O(n log n) rounds to detect an impostor leader, O(n) rounds to clean the system after the detection of an error, and O(n log 2 n) rounds to elect the leader. Therefore, in total, Algorithm CLE performs O

?. Db-v, 1. {0, A. , ?. {+, ?. Ok et al., and those that use O(log log n) bits. Variables of the first type are: par v ? {?, 0, 1}, Proof. Algorithm CLE has two types of variables 2}. Variables of the second type are: B v ? log n} × {0, 1}, and Elec v ? {1, ..., log n} × {1, ..., log n} × {0, p.1

. Hence, CLE uses O(log log n) bits of memory per node

. Finally, it is known that one cannot do the same using only O(1) bits of memory per node

]. J. Adamek, M. Nesterenko, and S. Tixeuil, Using abstract simulation for performance evaluation of stabilizing algorithms: The case of propagation of information with feedback, SSS 2012, 2012.

Y. Afek and A. Bremler-barr, Self-stabilizing unidirectional network algorithms by power supply, Chicago J. Theor. Comput. Sci, 1998.

S. Aggarwal and S. Kutten, Time optimal self-stabilizing spanning tree algorithms, Foundations of Software Technology and Theoretical Computer Science, 13th Conference, pp.400-410, 1993.
DOI : 10.1007/3-540-57529-4_72
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.5742

A. Arora and M. G. Gouda, Distributed reset, IEEE Transactions on Computers, vol.43, issue.9, pp.1026-1038, 1994.
DOI : 10.1109/12.312126

M. Arumugam and S. S. Kulkarni, ProSe - A Programming Tool for Rapid Prototyping of Sensor Networks, 2007 2nd IEEE Workshop on Networking Technologies for Software Define Radio Networks, pp.158-173, 2009.
DOI : 10.1109/SDRN.2007.4348975

B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-shamir, and G. Varghese, A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock, IEEE Transactions on Dependable and Secure Computing, vol.4, issue.3, pp.180-190, 2007.
DOI : 10.1109/TDSC.2007.1007

B. Awerbuch and R. Ostrovsky, Memory-efficient and self-stabilizing network reset, PODC, pp.254-263, 1994.
DOI : 10.1145/197917.198104
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.5947

J. Beauquier, M. Gradinariu, and C. Johnen, Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings, Distributed Computing, pp.75-93, 2007.
DOI : 10.1007/s00446-007-0034-0
URL : https://hal.archives-ouvertes.fr/hal-00334311

J. Beauquier, A. Kumar-datta, and S. Tixeuil, Self-stabilizing census with cut-through constraint, Proceedings 19th IEEE International Conference on Distributed Computing Systems, pp.70-77, 1999.
DOI : 10.1109/SLFSTB.1999.777489

J. Beauquier, M. Gradinariu, and C. Johnen, Memory space requirements for self-stabilizing leader election protocols, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing , PODC '99, pp.199-208, 1999.
DOI : 10.1145/301308.301358
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.142.1278

L. Blin and S. Tixeuil, Brief announcement, Proceedings of the 2013 ACM symposium on Principles of distributed computing, PODC '13, pp.125-127, 2013.
DOI : 10.1145/2484239.2484289
URL : https://hal.archives-ouvertes.fr/hal-00741982

L. Blin and S. Tixeuil, Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative, Proceedings of the 27th International Conference on Distributed Computing (DISC 2013), Lecture Notes in Computer Science (LNCS), pp.76-90, 2013.
DOI : 10.1007/s00446-017-0294-2
URL : https://hal.archives-ouvertes.fr/hal-01486763

L. Blin, F. Boubekeur, and S. Dubois, A Self-Stabilizing Memory Efficient Algorithm for the Minimum Diameter Spanning Tree under an Omnipotent Daemon, 2015 IEEE International Parallel and Distributed Processing Symposium, pp.1056-1074, 2015.
DOI : 10.1109/IPDPS.2015.44
URL : https://hal.archives-ouvertes.fr/hal-01201859

Y. Choi and M. G. Gouda, A state-based model of sensor protocols, Theoretical Computer Science, vol.458, pp.61-75, 2012.
DOI : 10.1016/j.tcs.2012.08.013

A. R. Dalton, W. P. Mccartney, K. Ghosh-dastidar, J. O. Hallstrom, N. Sridhar et al., DESAL alpha: An Implementation of the Dynamic Embedded Sensor-Actuator Language, 2008 Proceedings of 17th International Conference on Computer Communications and Networks, pp.541-547, 2008.
DOI : 10.1109/ICCCN.2008.ECP.108

A. Kumar-datta, L. L. Larmore, and P. Vemula, Self-stabilizing leader election in optimal space under an arbitrary scheduler, TCS, issue.40, pp.4125541-5561, 2011.

S. Devismes, T. Masuzawa, and S. Tixeuil, Communication Efficiency in Self-Stabilizing Silent Protocols, 2009 29th IEEE International Conference on Distributed Computing Systems, pp.474-481, 2009.
DOI : 10.1109/ICDCS.2009.24
URL : https://hal.archives-ouvertes.fr/inria-00340805

E. W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, vol.17, issue.11, pp.643-644, 1974.
DOI : 10.1145/361179.361202

S. Dolev, Self Stabilization, Journal of Aerospace Computing, Information, and Communication, vol.1, issue.6, 2000.
DOI : 10.2514/1.10141
URL : https://hal.archives-ouvertes.fr/inria-00627780

S. Dolev, M. G. Gouda, and M. Schneider, Memory requirements for silent stabilization, Acta Informatica, vol.36, issue.6, pp.447-462, 1999.
DOI : 10.1007/s002360050180
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.388.6681

S. Dolev and T. Herman, SuperStabilizing protocols for dynamic distributed systems, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing , PODC '95, 1997.
DOI : 10.1145/224964.224993
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.5949

S. Dolev, A. Israeli, and S. Moran, Resource Bounds for Self-Stabilizing Message-Driven Protocols, SIAM Journal on Computing, vol.26, issue.1, pp.273-290, 1997.
DOI : 10.1137/S0097539792235074
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.9936

S. Dolev, A. Israeli, and S. Moran, Uniform dynamic self-stabilizing leader election, Distributed Algorithms, 5th International Workshop, WDAG '91 Proceedings, pp.167-180, 1991.
DOI : 10.1007/BFb0022445
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.124.7453

S. Dubois and S. Tixeuil, A taxonomy of daemons in self-stabilization, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00628390

F. E. Fich and C. Johnen, A Space Optimal, Deterministic, Self-stabilizing, Leader Election Algorithm for Unidirectional Rings, DISC, pp.224-239, 2001.
DOI : 10.1007/3-540-45414-4_16

M. G. Gouda, J. A. Cobb, and C. Huang, Fault Masking in Tri-redundant Systems, In SSS LNCS, pp.304-313, 2006.
DOI : 10.1007/978-3-540-49823-0_21

T. Herman and S. V. Pemmaraju, Error-detecting codes and fault-containing self-stabilization, Information Processing Letters, vol.73, issue.1-2, pp.41-46, 2000.
DOI : 10.1016/S0020-0190(99)00164-7

J. Hoepman, Self-Stabilizing Ring Orientation Using Constant Space, Information and Computation, vol.144, issue.1, pp.18-39, 1998.
DOI : 10.1006/inco.1998.2707
URL : http://doi.org/10.1006/inco.1998.2707

A. Israeli and M. Jalfon, Uniform Self-Stabilizing Ring Orientation, Information and Computation, vol.104, issue.2, pp.175-196, 1993.
DOI : 10.1006/inco.1993.1029
URL : http://doi.org/10.1006/inco.1993.1029

G. Itkis and L. A. Levin, Fast and lean self-stabilizing asynchronous protocols, Proceedings 35th Annual Symposium on Foundations of Computer Science, pp.226-239, 1994.
DOI : 10.1109/SFCS.1994.365691
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6271

G. Itkis, C. Lin, and J. Simon, Deterministic, constant space, self-stabilizing leader election on uniform rings, WDAG, pp.288-302, 1995.
DOI : 10.1007/BFb0022154
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.8763

A. Korman, S. Kutten, and T. Masuzawa, Fast and compact self stabilizing verification, computation, and fault detection of an mst, Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC 2011, pp.311-320, 2011.
URL : https://hal.archives-ouvertes.fr/hal-01240211

T. Masuzawa and S. Tixeuil, On bootstrapping topology knowledge in anonymous networks, ACM Transactions on Autonomous and Adaptive Systems, vol.4, issue.1, 2009.
DOI : 10.1145/1462187.1462195
URL : https://hal.archives-ouvertes.fr/hal-01151766

A. J. Mayer, Y. Ofek, R. Ostrovsky, and M. Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , STOC '92, pp.667-678, 1992.
DOI : 10.1145/129712.129777
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.9197