Adaptivity through distributed convergence
Ted Herman · 1992
An adaptive program is one that changes its behavior in response to its environment. For the case of a distributed program in a distributed environment, selection of appropriate behavior for the program's current environment is a problem of distributed control. The dissertation explores a particular definition of program adaptivity. Based on that definition, the dissertation develops some logic for reasoning about adaptive properties of a program. Accompanying the logic, program composition operators are proposed for the construction of adaptive programs. Case studies demonstrate how the composition operators can be applied to construct distributed adaptive programs for mutual exclusion, routing in a communication network, and graph biconnectivity. The definition of adaptivity is related to the concept of self-stabilization: a self-stabilizing program converges to legitimate behavior from any point in its state-space, including illegitimate states; an adaptive program converges from any point in its state-space to appropriate behavior, where the definition of appropriate behavior depends on the state of the program's environment. This strongly convergent notion of adaptivity means that a distributed adaptive program correctly adapts in spite of an asynchronously changing environment and that the mechanism of adaptivity does not depend on initialization phases or timing protocols; the definition of adaptivity separates the concern of distributed control from the concern of synchronizing environmental change with program computation.