, 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
column) is called ? times by function Daemon ,
column) is called ? times by function Reset(3, column) ,
column) is called ? times by function Reset(2, column) ,
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)
?}:-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 ? ,
, Stabilization, Safety, and Security of Distributed Systems16th International Symposium, pp.106-119, 2014.
Self-stabilizing Systems in Spite of Distributed Control, Commun. ACM, vol.17, issue.11, pp.643-644, 1974. ,
Self-stabilization, 2000. ,
URL : https://hal.archives-ouvertes.fr/inria-00627780
Self-stabilizing Leader Election in Optimal Space under an Arbitrary Scheduler, Theor. Comput. Sci, vol.412, issue.40, pp.5541-5561, 2011. ,
An O(n)-time Self-stabilizing Leader Election Algorithm, J. Parallel Distrib. Comput, vol.71, issue.11, pp.1532-1544, 2011. ,
Self-stabilizing Leader Election in Dynamic Networks, Stabilization, Safety, and Security of Distributed Systems-12th International Symposium (SSS), pp.35-49, 2010. ,
Memory Requirements for Silent Stabilization, Acta Inf, vol.36, issue.6, pp.447-462, 1999. ,
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
Self-Stabilizing Unidirectional Network Algorithms by Power Supply, Chicago J. Theor. Comput. Sci, 1998. ,
Time Optimal Selfstabilizing Synchronization, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pp.652-661, 1993. ,
, Distributed Computing, 21st International Symposium (DISC), pp.92-107, 2007.
Superstabilizing Protocols for Dynamic Distributed Systems, Chicago J. Theor. Comput. Sci, 1997. ,
Distributed Reset, IEEE Trans. Computers, vol.43, issue.9, pp.1026-1038, 1994. ,
Time Optimal Synchronous Self Stabilizing Spanning Tree, pp.91-105, 2013. ,
Uniform Dynamic Self-Stabilizing Leader Election, IEEE Trans. Parallel Distrib. Syst, vol.8, issue.4, pp.424-440, 1997. ,
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
Echo Algorithms: Depth Parallel Operations on General Graphs, IEEE Trans. Software Eng, vol.8, issue.4, pp.391-401, 1982. ,
Distributed Network Protocols, IEEE Transactions on Information Theory, vol.29, issue.1, pp.23-34, 1983. ,
Broadcast Scheduling Algorithms for Radio Networks, Military Communications Conference, 1995. MILCOM'95, vol.2, pp.647-651, 1995. ,