A Compositional Framework for Designing Self-Stabilizing Distributed Algorithms
Abhishek Dhama · Carl von Ossiezky University of Oldenburg · 2013
The proliferation of numerous computing devices in the various facets of life has remarkably elevated the premium placed on fault tolerance of the algorithms running on such devices. Self-stabilization is a novel method to provide non-masking fault tolerance. A distributed system is said to be self-stabilizing if and only if 1) it reaches a closed set of legal states in finite time, and 2) does not leave this set voluntarily. However, designing and proving convergence of a self-stabilizing system is not easy. We investigate whether the conditions under which component algorithms are self-stabilizing can be transcended while composing them. To that end, this dissertation presents a suite of compositional methods which can be used to compose self-stabilizing algorithms, though component algorithms themselves might be self-stabilizing under mutually incompatible conditions.