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*(log*n*)
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.