טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentKravchik Alex
SubjectTime Optimal Synchronous Self Stabilizing Spanning Tree
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Shay Kutten
Full Thesis textFull thesis text - English Version


Abstract

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.