SELF-STABILIZING ROUTING AND RELATED PROTOCOLS

A self-stabilizing system is a distributed system which can tolerate a ny number and any type of faults in the history. After the last fault occurs the system converges to a legitimate behavior. The self-stabili zation property is very useful for systems in which processors may mal function for a while and then recover. When there is a long enough per iod during which no processor malfunctions the system stabilizes. Dyna mic distributed systems are systems in which communication links and p rocessors may fail and recover during normal operation. Such failures could cause partitioning of the system communication graph. The applic ation of self-stabilizing protocols to dynamic systems is natural. Fol lowing the last topology change each connected component of the system stabilizes independently. We present self-stabilizing dynamic protoco ls for a variety of tasks including: routing, leader election, and top ology update. For systems that support local broadcasts to neighbors i n a single time unit the protocol for each of those tasks stabilizes i n Theta(d) time, where d is the actual diameter of the system. (C) 199 7 Academic Press.