Self-stabilization (Q2782251)

This book considers algorithms operating on (possibly distributed) communication networks. A set of processors which can communicate between each other is such that delivery is asynchronous and associated queues have to be added to the model, leading to a configuration with states of processors and associated queues. Computational steps are applied to the configuration. The analogy to the equilibrium point of a dynamical system is the set of ``safe configurations'' with respect to a legal task, meaning that an algorithm applied to the configuration corresponds to a legal execution. An algorithm will be self-stabilizing for a legal task if every fair execution of the algorithm reaches a safe configuration with respect to the legal task. Self-stabilization is motivated by the occurrence of errors and crashes as a way to recover from them.NEWLINENEWLINENEWLINEThe issue of algorithm conversion between different contexts is analysed (between shared memory and message passing or between a centralized and decentralized configuration for instance). The problem of converting nonstabilizing algorithms to self-stabilizing ones is studied. More conservative situations are analyzed, like when a processor fights against other processors so that they cannot reach their goal. In some cases the nefarious influence cannot be eliminated, but if it occurs in a transitory way then things look better. Locality is an important aspect for a good self-stabilizing algorithm: if a limited number of faults occurs, the repair mechanism should not be global. A chapter focuses on computation for Turing machines.