, Notice that every process of line top(layer) chooses the process p (top(layer)?1,column) as parent. In Reset(layer, column), all the processes on column column from the one on line top(layer + 1) to the one on line bottom(layer + 1) execute Action R (except for layer 1 where all the processes of line 8 also execute Action R). Then, Reset(layer ? 1, i) and Build(layer?1, i+1) are called for each column i = 1,. .. , ??1. Finally, Reset(layer?1, ?) is executed. We count how many times processes p (8,.) executes Action R: ? Each process p (8,.) executes once Action

?. Reset, column) is called ? times by function Daemon

?. Reset, column) is called ? times by function Reset(3, column)

?. Reset, column) is called ? times by function Reset(2, column)

. Hence, Action R is executed ? 4 times by the processes of line 8. Now, ? = n/8. Hence we can conclude: Theorem 12. For every ? ? 2, there exists a network of n = 8 × ? processes in which there exists a possible execution

, we can build E ? , a graph for which there exists an execution in ?(n ? ) steps. The construction is based on the same principle as in Subsection 5.2, by adding a layer. If E ??1 has L? processes p (i,j) (1 ? i ? L, 1 ? j ? ?), then E ? has L = 2L lines of ? processes q (i ,j ) (1 ? i ? L , 1 ? j ? ?). The construction principle is as follows: 1. We increase the level and the ID of the L? processes of E ??1 as follows, Generalization to an Example in ?(n ? ) Steps We note E 4 the graph built for the example in ?(n 4 ) steps and shown in Figure 12a. Then, starting from E ??1 (? ? 5)

.. .. {1 and .. .. {1, ?}:-q (i,j) .id = (i ? 1)? + j-q (i,j), At the top of E ??1 , we add L lines of ? processes. These new processes satisfy: ? ?i ?

K. Altisen, A. Cournier, S. Devismes, A. Durand, and F. Petit, Stabilization, Safety, and Security of Distributed Systems16th International Symposium, pp.106-119, 2014.

E. W. Dijkstra, Self-stabilizing Systems in Spite of Distributed Control, Commun. ACM, vol.17, issue.11, pp.643-644, 1974.

S. Dolev, Self-stabilization, 2000.
URL : https://hal.archives-ouvertes.fr/inria-00627780

A. K. Datta, L. L. Larmore, and P. Vemula, Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler, Theor. Comput. Sci, vol.412, issue.40, pp.5541-5561, 2011.

A. K. Datta, L. L. Larmore, and P. Vemula, An O(n)-time Self-stabilizing Leader Election Algorithm, J. Parallel Distrib. Comput, vol.71, issue.11, pp.1532-1544, 2011.

A. K. Datta, L. L. Larmore, and H. Piniganti, Self-stabilizing Leader Election in Dynamic Networks, Stabilization, Safety, and Security of Distributed Systems-12th International Symposium (SSS), pp.35-49, 2010.

S. Dolev, M. G. Gouda, and M. Schneider, Memory Requirements for Silent Stabilization, Acta Inf, vol.36, issue.6, pp.447-462, 1999.

L. Blin and S. Tixeuil, Brief Announcement: Deterministic Self-stabilizing Leader Election with O(log log n)-bits, pp.125-127, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00930090

Y. Afek and A. Bremler-barr, Self-Stabilizing Unidirectional Network Algorithms by Power Supply, Chicago J. Theor. Comput. Sci, 1998.

B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-shamir, and G. Varghese, Time Optimal Selfstabilizing Synchronization, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pp.652-661, 1993.

J. Burman and S. Kutten, Distributed Computing, 21st International Symposium (DISC), pp.92-107, 2007.

S. Dolev and T. Herman, Superstabilizing Protocols for Dynamic Distributed Systems, Chicago J. Theor. Comput. Sci, 1997.

A. Arora and M. G. Gouda, Distributed Reset, IEEE Trans. Computers, vol.43, issue.9, pp.1026-1038, 1994.

A. Kravchik and S. Kutten, Time Optimal Synchronous Self Stabilizing Spanning Tree, pp.91-105, 2013.

S. Dolev, A. Israeli, and S. Moran, Uniform Dynamic Self-Stabilizing Leader Election, IEEE Trans. Parallel Distrib. Syst, vol.8, issue.4, pp.424-440, 1997.

L. Blin, A. Cournier, and V. Villain, An improved snap-stabilizing PIF algorithm, Self-Stabilizing Systems, 6th International Symposium, vol.2704, pp.199-214, 2003.
URL : https://hal.archives-ouvertes.fr/hal-01310823

E. J. Chang, Echo Algorithms: Depth Parallel Operations on General Graphs, IEEE Trans. Software Eng, vol.8, issue.4, pp.391-401, 1982.

A. Segall, Distributed Network Protocols, IEEE Transactions on Information Theory, vol.29, issue.1, pp.23-34, 1983.

M. L. Huson and A. Sen, Broadcast Scheduling Algorithms for Radio Networks, Military Communications Conference, 1995. MILCOM'95, vol.2, pp.647-651, 1995.