M.Sc Student | Zinenko Dmitry |
---|---|

Subject | Communication-Efficient Self-Stabilization |

Department | Department of Computer Science |

Supervisor | Professor Shay Kutten |

Full Thesis text |

In
1973, Dijkstra introduced the notion of *self-stabilization *in the context of
distributed systems. He defined a system as self-stabilizing when “regardless
of its initial state, it is guaranteed to arrive at a legitimate state in a
finite number of steps.” Most self-stabilizing protocols rely on checking every
neighbor of a node continuously to detect failures. Therefore, such protocols
have a high communication cost, especially in dense graphs. Drawing inspiration
from gossip protocols, we investigate the potential effect of randomization on
the communication efficiency of self-stabilizing protocols.

We
study this approach in a complete graph, where the communication overhead seems
to be the highest when one strives for protocols that are also fast. We present
randomized low communication self-stabilizing algorithms for several major
tasks, namely, spanning tree construction, distributed reset, and unison. The
spanning tree algorithm sends a constant number of messages per node every
round, and converges within *O**(log **n**)* rounds with high
probability. The reset and unison algorithms send only one message per node
every round, and also converge within *O**(log **n**)* rounds with high
probability. This results in *O**(**n **log **n**)* messages until
convergence w.h.p. for all three algorithms, while all previously known
self-stabilizing solutions for those problems have the message complexity of *O(n*^{2}*)* in a complete
graph.

Our
reset and unison protocols can also be used (although with a different round
complexity) in more general classes of synchronous networks. For example, in
bounded degree networks their round complexity is *O**(**D**? **n**)* with high probability,
where *D *is the graph diameter, while still sending one message per node per
round.