Paper Info
Title
Self-stabilization—beyond the token ring circulation (brief announcement)
Abstract
There is a diffused feeling that the self-stabilization concept, as defined by Dijkstra in 1974, is extremely deep in pointing out the features of a fault tolerant distributed system, but is also too restrictive in the definition of what is self-stabilizing.My primary purpose is to explain why Dijkstra's definition needs to be extended: the reader understands that the task is extremely delicate, since there is a unanimous appreciation of the original definition of self-stabilization, and its modification should exhibit extremely strong motivations. Secondarily, we show how it can be modified to widen its applicability.First I restate the original definition using Chandy and Misra's Unity. This step is mechanical, so to keep the result as independent as possible from any subjective understanding of the self-stabilization concept:DEFINITION 1 (SELF-STABILIZING SYSTEM). Given a (flat) Unity program P with guards &Pgr; and a predicate l, P is self-stabilizing to l if and only if: the initially section of P is empty, unconditionall is stable, stability∀p ∈ &Pgr;, {l ∧ p} ≠ 0, minimal statements∀x, y ∈ {l}, x ↦ y, minimal statestrue ↦ l.finite convergence The label attached to each predicate may help intuition. The next theorem, whose proof is in the full paper that can be requested by e.mail, limits the set of problems that can be treated with self-stabilization:THEOREM 1. A predicate l satisfies stability and minimal states if and only ifonly one state satisfies l and the execution of any statement leaves that state unaltered orthere are n 1 states that satisfy l and an indexing l} = {s0,…,sn - 1} exists such that si ensures s(i+1) mod n.A corollary says that, if there is more than one legitimate state, then units are arranged in a ring, and are enabled to move according to that arrangement. That limits the applicability of the self-stabilization concept to the range of token circulation problems, and concludes the first step.Next I want to modify the Definition 1 in order to extend the number of problems that can be treated using the self-stabilization concept. Coherently with a conservative approach, the impact of the modification should be minimal.I opt to redefine the Minimal States predicate so that it operates set-wise: to this purpose I split l, the set of legitimate states, in a family of subsets L, and for any pair in L I want that “there exists a sequence of moves transferring the system from the one into the other”. The sets in L can be defined either by enumeration, or by a characteristic property. The new formulation of the Minimal States is: DEFINITION 2 (MINIMAL STATES (SET-WISE)). A family L = {l1, …, lk}, with ∪L = l exists such that ∀(la, lb) ∈ L2, la ↦ lbThe last step consists in proving that the new definition widens the applicability of the self-stabilization concept. In Figure 1 I give a simple clock synchronization problem that can be treated with self-stabilization only when this concept is extended with the set-wise minimal states.The problem cannot be treated using Definition 1: the proof is by contradiction, using the only if part of the Theorem, if I want to exploit the presence of redundant paths. The partition I need to apply the set-wise extension is: L = {ticki, tacki | i ∈ [0, 2n - 1]} where ticki = {s | A = 2i - 1 ∧ A = C + 1 ∧ (∀k : Bk = A ∨ Bk = C)} tacki = {s | A = 2i - 1 ∧ A = C - 1 ∧ (∀k : Bk = A ∨ Bk = C)} and the problem is solved by the following self-stabilizing algorithm (the proof is available):A: if (B==B2) and (B2==B3) if even(B1) A=B1+1; else A=B1; C: if (B1==B2) and (B2==B3) if even(B1) C=B1; else C=B1+1;Bk: if A!=(C-1) Bk=A; else Bk=C;
Year
DOI
Venue
2000
10.1145/343477.362068
PODC
Keywords
Field
DocType
original definition,legitimate state,minimal states,token ring circulation,family l,self-stabilization concept,indexing l,brief announcement,minimal state,subsets l,minimal statement,predicate l,concurrency,clock synchronization,indexation,satisfiability
Discrete mathematics,Family of sets,Existential quantification,Self-stabilization,Characteristic property,If and only if,Predicate (grammar),Partition (number theory),Corollary,Mathematics,Distributed computing
Conference
ISBN
Citations 
PageRank 
1-58113-183-6
0
0.34
References 
Authors
1
1
Name
Order
Citations
PageRank
Augusto Ciuffoletti113917.40