Self-Stabilization

About twenty-five years ago, Edsger Dijkstra asked an important question: would it be possible for a set of machines to stabilize their collective behavior in spite of unpredictable initial conditions and distributed control? Answers to this question spawned the technical research field of self-stabilization. Dijkstra's initial article did not mention how self-stabilizing algorithms could be useful in system design; only later was self-stabilization classified as a technique for fault tolerance. More recent work demonstrates that self-stabilization is the most general method tolerating transient faults and shows how it can be combined with more traditional forms of fault tolerance.

The main challenge associated with self-stabilization is complexity. It is non-trivial to design correct self-stabilizing systems, and this has motivated much research. One direction has been to rely on familiar paradigms of distributed programming, such as mutual exclusion, leader election, logical time, snapshots, wave algorithms, and broadcast --- all of these now have stabilizing counterparts that can be combined for application to system design. Another research direction explores complexity in terms of resource requirements, including memory needed to satisfy particular task requirements, time needed for stabilization, and size requirements on messages. A third research direction attacks complexity by automating system design, and efforts along this line include composition methods, program transformers, program refinement, and systematic proof techniques for self-stabilizing programs. Although considerable progress has been made along all three of these directions, there remain many open questions and we anticipate similar research will continue.

The first Dagstuhl-Seminar, which took place in August of 1998, was a great opportunity for exchange of current ideas and results in the field of self-stabilization. The present of the pioneer researcher of this field Edsger Dijkstra contributed to the atmosphere of the seminar. The current seminar is aimed towards amplifying the successful interaction between the researchers in the self-stabilization field.

New topics within self-stabilization are generating interest in both fundamental and more applied areas. Common assumptions of fairness and atomicity attract basic research on how stabilization impacts these issues. Some investigators are moving beyond questions of self-stabilization as an isolated goal, and now consider providing conditional safety properties during the period of convergence before a system stabilizes. Other conditional properties relate convergence complexity to the scope of transient faults, by showing how self-stabilizing systems can confine repair to greater locality in time (faster repair) and space (fewer processes) for some initial system states. Several members of the community now point out that practical distributed systems already use techniques closely related to stabilization, which argues that variations on definitions and weakenings of stabilization could be rewarding directions of research. There is also more attention on top-down issues of design in stabilizing systems, such as client views of stabilizing services, more detailed analysis of illegitimate behaviors, and selected case studies of standard services like load balancing, and even web servers.

We note that NSF funds are at our disposal for the support of travel expenses (when such a support is needed).