טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentZinenko Dmitry
SubjectCommunication-Efficient Self-Stabilization
DepartmentDepartment of Computer Science
Supervisor Professor Shay Kutten
Full Thesis textFull thesis text - English Version


Abstract

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(n2) 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.