Communication-Efficient Self-Stabilization Using Gossip.

דמיטרי זיננקו, הרצאה סמינריונית למגיסטר
יום רביעי, 17.11.2010, 14:00
טאוב 601
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.

בחזרה לאינדקס האירועים