Self-stabilization by window washing

Abstract

A useful way to design simple and robust protocols is to make them self-stabilizing. We describe a new general technique for self-stabilization called window washing. We apply this technique to generalized sliding window protocols that work on a number of topologies. This results in simple, efficient, and self-stabilizing protocols. As far as we know, both window washing and generalized sliding window protocols are new ideas. Our protocols can be used for data links, reliable broadcast, and flow control. This work supported by a grant from the NSF. Self-Stabilization by Window Washing Adam M. Costello !amc@cs.wustl.edu? http://www.cs.wustl.edu/~amc/ George Varghese !varghese@cs.wustl.edu? http://www.ccrc.wustl.edu/~varghese/ 1. Introduction A protocol is self-stabilizing if, when started from an arbitrary global state, it exhibits "correct " behavior in bounded time. Typical protocols cope with a specified set of failure modes such as packet loss and link failures. A selfstabili...