# Self-stabilizing Algoriths

## 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.

- (DEMO) Self-Stabilizing 1-Maximal Matching Algorithm

## 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.