Communication-Efficient Self-Stabilization Using Gossip.

Speaker:
Dmitry Zinenko, M.Sc. Thesis Seminar
Date:
Wednesday, 17.11.2010, 14:00
Place:
Taub 601
Advisor:
Prof. S. Kutten

A self-stabilizing algorithm is a distributed algorithm that converges to a legal solution from any initial configuration. Most self-stabilizing protocols rely on checking every neighbor of every processor continuously to detect inconsitencies. Such protocols have a high communication cost, especially in dense networks. We investigate the potential usefulness of gossip for improving the communication efficiency of self-stabilizing protocols. We present randomized low communication self-stabilizing algorithms for several major tasks, namely, spanning tree construction, distributed reset, and unison. The talk is self contained and requires basic knowledge of probability and distributed algorithms.

Back to the index of events