Self-stabilizing systems have in theory the uniqueand provable ability, to always return to a valid system stateeven in the face of failures. These properties are certainly desirablefor domains like wireless ad-hoc networks with numerousunpredictable faults. Unfortunately, the time in which the systemreturns to a valid state is not predictable and potentially unbound. The failure rate typically depends on physical phenomena andin self-stabilizing systems each node tries to react to failuresin an inherently adaptive fashion by the cyclic observation ofthe states of its neighbors. When state changes are either tooquick or too slow the system might never reach a state that issufficiently stable for a specific task. In this paper, we investigatethe influences of the error rate on the (stability) convergence timeon the basis of topology information acquired in real networkexperiments. This allows us to asses the asymptotic behavior ofrelevant self-stabilizing algorithms in typical wireless networks.
['Stefan Lohs', 'Gerry Siegemund', 'Jorg Nolte', 'Volker Turau']
Influence of Topology-Fluctuations on Self-Stabilizing Algorithms