page 1  (18 pages)
2to next section

A Timestamp Based Transformation of

Self-Stabilizing Programs for Distributed

Computing Environments

Masaaki Mizuno1? and Hirotsugu Kakugawa2??

1 Dept. of Comp. and Info. Sci. Kansas State University, Manhattan, KS 66506 2 Dept. of Elect. Engineering, Hiroshima University, Higashi-Hiroshima, Japan

Abstract. There are several models for which self-stabilizing (SS) programs have been developed. The distributed model accurately reflects a real distributed computing environment; therefore, programs developed for the model should run directly on a distributed system. However, many SS programs have been developed for the serial model which has the strongest assumptions, because it is much easier to develop and verify a program for the model than one for other models. This paper presents a transformation method that converts a program designed for the serial model to a program for the distributed model. An SS concurrency control protocol is incorporated in a transformed program to guarantee that if the original program is SS, the transformed program is also SS and performs exactly like the original program. We have implemented transformed versions of several serial model SS algorithms and tested them with various initial configurations.

1 Introduction

A distributed system consists of a set of processes and communication links that connect the processes. The processes cooperate with each other by communicating through the links. Dijkstra introduced the notion of self-stabilization in the context of distributed systems [4]. A system is defined to be self-stabilizing (SS) with respect to a set of legitimate states if regardless of its initial state, the system is guaranteed to arrive at a legitimate state in a finite number of steps and will never leave legitimate states after that. Thus, an SS system need not be initialized and is able to recover from transient failures by itself.

An SS system consists of two components: a program and a run-time support system. A run-time system provides a program with an execution environment and services. Many SS programs have been developed with various assumptions on their execution environments. These assumptions include the semantics of concurrency and communication primitives that the run-time support systems

? This work was supported in part by the National Science Foundation under Grant CCR-9201645
?? This work was supported in part by the Telecommunication Advancement Foundation.