Technical Report MSC-2011-07

Title: Communication-Efficient Self-Stabilization
Authors: Dmitry Zinenko
Supervisors: Shay Kutten
Abstract: In 1974, 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 randomized 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+log n) with high probability, where D is the graph diameter, while still sending one message per node per round.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2011
To the main CS technical reports page

Computer science department, Technion