Self-stabilizing Algorithms

What is a self-stabilizing algorithm?

A self-tabilizing algorithm is a distributed algorithm that has nice property called self-stabilization. Self-stabilization is a property that guarantees, even when a system enters any inconsist configuration, it automatically recovers and stabilizes to a consistent configuration. If the system gets the global configuration immediately, it can easily understand which process is inconsistent. However, in large-scale distributed systems, it is impossible to get the global configuration and so the system must recover based on only local information. It is likely that, even when the global configuration of the system is inconsistent, the local configuration of every process seems consistent. We must develop algorithms that recover the system from such inconsistent global configurations.

A self-stabilizing spanning tree algorithm

As an example, we explain a self-stabilizing spanning tree algorithm. Let us consider a distributed system in Fig. 2. The goal is to construct a spanning tree (i.e., a tree that connects every process) like Fig. 3. Since a spanning tree can connect every process with the minimum number of links, it is used as a backbone of the system in many distributed algorithms. As in Fig. 3, we can define a spanning tree by using a pointer that points to a parent. We assume the root process points to itself.

In self-stabilizing algorithms, the system must reach a consistent configuration from any inconsistent configuration. That is, from a configuration with no spanning tree in Fig. 4, we must construct a spanning tree. How do processes behave to construct a spanning tree? In this configuration, process P1 notices inconsistency because P1 points to P2 and P2 points to P1. Now we assume P1 changes its pointer to P3, and the system reaches a configuration in Fig. 5. Since a spanning tree is not constructed yet, some process must change its states. Which process can move? Process P1 points to P3 and P3 points to another process, and so processes P1 and P3 seem consistent locally. Actually, in this configuration, every process seems consistent locally. This means, though the system does not have a spanning tree, no process can notice this fact locally. To develop self-stabilizing algorithms, some process must detects the fact and changes its state to construct a spanning tree.

How do we realize such a behavior? To tell the truth, it is impossible to detect the inconsistency by using only pointers to parents. So we use an additional variable dist for each process that maintains the distance to the root. Figure 6 shows a consistent configuration, in which the system has a spanning tree and each process maintains a distance to the root correctly. From the definition, it clearly holds that dist of a non-root process is one plus dist of its parent process. What happens in an inconsistent configuration like Fig. 5? Figure 7 shows the same configuration as Fig. 5 but includes values of variables dist. In this configuration, dist of P3 is not one plus dist of P3’s parent. Therefore, P3 can notice the inconsistency and change its state.

Now we show a self-stabilizing spanning tree algorithm.

• The behavior of the root.
  If its pointer does not point to itself, or, dist is not zero,
  the root changes its pointer to itself and sets zero to dist.

• The behavior of a non-root process.
  If its pointer does not point to its neighbor, or,
  dist of itself is not one plus dist of its parent,
  the process changes its pointer to the neighbor with the minimum dist and
  sets one plus dist of its (new) parent to dist of itself.

Simply put each process changes its parent to the neighbor closest to the root. By this algorithm, the system can construct a spanning tree from any inconsistent configuration.