Dmitry Zinenko, M.Sc. Thesis Seminar
Wednesday, 17.11.2010, 14:00
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.