|M.Sc Student||Kravchik Alex|
|Subject||Time Optimal Synchronous Self Stabilizing Spanning Tree|
|Department||Department of Industrial Engineering and Management||Supervisor||Professor Shay Kutten|
|Full Thesis text|
In this research, we present the first time-optimal self stabilizing algorithm for synchronous distributed spanning tree construction, assuming the standard shared registers size (O(logn) bits, where n stands for the number of processes in the system), or, similarly, standard message size. Previous algorithms with O(diameter) stabilization time complexity assumed that a larger message can be sent through each link in one time unit. Hence, when assuming the standard message size, the time complexity of previous algorithms was not O(diameter). The current algorithm stabilizes in O(diameter) time without having previous knowledge of the network size or diameter. The only assumption we make is that we have some polynomial (possibly very large) given upper bound on the network size. However, the time complexity of the algorithm does not depend on that upper bound. Using our results, most known distributed global tasks, such as distributed reset, can be performed in a relatively easy way and in optimal time. As a building block, we present a new self stabilizing silent phase clock algorithm for synchronous networks (based on a known non-silent algorithm). It is optimal in time too. We believe it may be an interesting contribution by itself.