کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
432640 | 689003 | 2016 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Silent self-stabilizing BFS tree algorithms revisited Silent self-stabilizing BFS tree algorithms revisited](/preview/png/432640.png)
• We show that the bounded-memory version of the Dolev et al’s BFS is round-optimal.
• We show that the stabilization time of the Huang and Chen’s BFS is Omega(n) rounds.
• We show that these two algorithms have exponential stabilization times in steps.
In this paper, we revisit two fundamental results of the self-stabilizing literature about silent BFS spanning tree constructions: the Dolev et al. algorithm and the Huang and Chen’s algorithm. More precisely, we propose in the composite atomicity model three straightforward adaptations inspired from those algorithms. We then present a deep study of these three algorithms. Our results are related to both correctness (convergence and closure, assuming a distributed unfair daemon) and complexity (analysis of the stabilization time in terms of rounds and steps).
Journal: Journal of Parallel and Distributed Computing - Volume 97, November 2016, Pages 11–23