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.
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bernstein, P.A, Hadzilacos, V., and Goodman, N. Concurrency Control and Recovery in Database Systems. Addison-Wesley Publishing Co., 1987.
Burns J.E. and Pachl J.. Uniform self-stabilizing rings. ACM Transactions on Programming Languages and Systems, 11(2):330–344, April 1989.
Chen N.S., Yu F.P., and Huang S.T.. A self-stabilizing algorithm for constructing spanning trees. Inf. Process. Lett., 39:147–151, 1991.
Dijkstra E.W.. Self-stabilizing systems in spite of distributed control. Communications of the ACM, 17(11):643–644, November 1974.
Dolev S., Israeli A., and Moran S.. Self stabilization of dynamic systems assuming only read/write atomicity. Distributed Computing, 7:3–16, 1993.
Huang S.T., Wuu L.C., and Tsai M.S. Distributed execution model for selfstabilizing systems. In Proceedings of the 14th International Conference on Distributed Computing Systems, pages 432–439. IEEE, 1994.
Katz S. and Perry K.J.. Self-stabilizing extensions for message passing systems. Distributed Computing, 7:17–26, 1993.
Lamport L. Time, clocks and ordering of events in distributed systems. Communications of the ACM, 21(7):558–564, 1978.
Mizuno M. A Distributed/Parallel Algorithm Development System. Kansas State University, 1994.
Schneider M.. Self-stabilization. ACM Computing Surveys, 25(1):45–67, March 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mizuno, M., Kakugawa, H. (1996). A timestamp based transformation of self-stabilizing programs for distributed computing environments. In: Babaoğlu, Ö., Marzullo, K. (eds) Distributed Algorithms. WDAG 1996. Lecture Notes in Computer Science, vol 1151. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61769-8_20
Download citation
DOI: https://doi.org/10.1007/3-540-61769-8_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61769-3
Online ISBN: 978-3-540-70679-3
eBook Packages: Springer Book Archive