Multiphase stabilization

We generalize the concept of stabilization of computing systems. According to this generalization, the actions of a system S are partitioned into n partitions, called phase 1 through phase n. In this case, system S is said to be n-stabilizing to a state predicate Q iff S has state predicates P.0, ..., P.n such that P.0=true, P.n=Q, and the following two conditions hold for every j, 1⩽j⩽n. First, if S starts at a state satisfying P.(j-1) and if the only actions of S that are allowed to be executed are those of phase j or less, then S will reach a state satisfying P.j. Second, the set of states satisfying P.j is closed under any execution of the actions of phase j or less. By choosing n=1, this generalization degenerates to the traditional definition of stabilization. We discuss three advantages of this generalization over the traditional definition. First, this generalization captures many stabilization properties of systems that are traditionally considered nonstabilizing. Second, verifying stabilization when n>1 is usually easier than when n=1. Third, this generalization suggests a new method of fault recovery, called multiphase recovery