Name
Abstract | ||
|---|---|---|
This paper considers the self-stabilizing unison problem in uniform distributed systems. The contribution of this paper is threefold. First, we establish that when any self-stabilizing asynchronous unison protocol runs in synchronous systems, it converges to synchronous unison if the size of the clock K is greater than CG, CG being the length of the maximal cycle of the shortest maximal cycle basis if the graph contains cycles, 2 otherwise (tree networks). The second result demonstrates that the asynchronous unison in Boulinier et al. (In PODC ’04: Proceedings of the twenty-third annual ACM symposium on principles of distributed computing, pp. 150–159, 2004) provides a general self-stabilizing synchronous unison for trees which is optimal in memory space, i.e., it works with any K≥3, without any extra state, and stabilizes within 2D rounds, where D is the diameter of the network. This protocol gives a positive answer to the question whether there exists or not a general self-stabilizing synchronous unison for tree networks with a state requirement independent of local or global information of the tree. If K=3, then the stabilization time of this protocol is equal to D only, i.e., it reaches the optimal performance of Herman and Ghosh (Inf. Process. Lett. 54:259–265, 1995). The third result of this paper is a self-stabilizing unison for general synchronous systems. It requires K≥2 only, at least K+D states per process, and its stabilization time is 2D only. This is the best solution for general synchronous systems, both for the state requirement and the stabilization time. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/11577327_2 | Self-Stabilizing Systems |
Keywords | Field | DocType |
Computational complexity,Self-stabilization,Phase synchronization,Unison | Asynchronous communication,Discrete mathematics,Computer science,Cycle basis,Unison,Cycle graph,Phase synchronization,Self-stabilization,Fault tolerance,Computational complexity theory | Journal |
Volume | Issue | ISSN |
51 | 1 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-29814-2 | 14 | 0.62 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Boulinier | 1 | 53 | 3.66 |
| Franck Petit | 2 | 736 | 60.02 |
| Vincent Villain | 3 | 544 | 45.77 |