Analysis of self-stabilization for infinite-state systems
Hsu‐Chun Yen · 2002
The problem of deciding whether an infinite-state system is self-stabilizing or not is investigated from the decidability viewpoint. We develop a unified strategy through which checking self-stabilization is shown to be decidable for one-counter machines and conflict-free Petri nets. Our strategy relies on the reachability sets being semilinear; as well as on the capability of extracting periodic behaviors of infinite computations, which, in turn, facilitates the expression of self-stabilization by Presburger Arithmetic. As fairness is frequently used as a qualitative measure to capture the notion of a quantitative measure of 'something happens with probability one,' it is of interest to examine the fair version of the self-stabilization problem, i.e., the problem of asking whether all 'fair' infinite computations eventually become self-stabilizing. We propose a potential method through which the problem is shown to be decidable for conflict-free Petri nets.