Self-stabilization preserving compiler

ABSTRACT

Self-stabilization is an elegant approach for designing fault tolerant systems. A system is considered self-stabilizing if, starting in any state, it converges to the desired behavior. Self-stabilizing algorithms were designed for solving fundamental distributed tasks, such as leader election, token circulation and communication network protocols. The algorithms were expressed using guarded commands or pseudo-code. The realization of these algorithms requires the existence of a (self-stabilizing) infrastructure such as a self-stabilizing microprocessor and a self-stabilizing operating system for their execution. Moreover, the high-level description of the algorithms needs to be converted into machine language of the microprocessor. In this article, we present our design for a self-stabilization preserving compiler. The compiler we designed and implemented transforms programs written in a language similar to the abstract state machine (ASM). The compiler preserves the stabilization property of the high level program.

REFERENCES

• 1: Dean Rosenzweig , Egon Börger , Yuri Gurevich, The bakery algorithm: yet another specification and verification, Specification and validation methods, Oxford University Press, Inc., New York, NY, 1995
• 2: E. Borger , Robert F. Stark, Abstract State Machines: A Method for High-Level System Design and Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 3: Olga Brukman , Shlomi Dolev , Elliot K. Kolodner, Self-Stabilizing Autonomic Recoverer for Eventual Byzantine Software, Proceedings of the IEEE International Conference on Software-Science, Technology & Engineering, p.20, November 04-05, 2003
• 4: Murat Demirbas , Anish Arora, Convergence Refinement, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.589, July 02-05, 2002
• 5: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 6: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 7: Dolev, S. and Haviv, Y. 2004. Self-stabilizing microprocessor analyzing and overcoming soft-errors (extended abstract). In Proceedings of the International Conference on Architecture of Computing Systems (ARCS'04). Lecture Notes in Computer Science, vol. 2981. Springer Verlag, 31--46.
• 8: Dolev, S., Haviv, Y., and Sagiv, M. 2008. Self-stabilization preserving compiler—implementation and examples. Tech. rep. #2008-01, Ben-Gurion University of the Negev, Israel. http://www.cs.bgu.ac.il/~frankel/TechRep/08-01/index.html.
• 9: Shlomi Dolev , Amos Israeli , Shlomo Moran, Self-stabilization of dynamic systems assuming only read/write atomicity, Distributed Computing, v.7 n.1, p.3-16, November 1993 [doi>10.1007/BF02278851]
• 10: Shlomi Dolev , Ronen I. Kat, Self-Stabilizing Distributed File Systems, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems, p.384, October 13-16, 2002
• 11: Shlomi Dolev , Jennifer L. Welch, Self-stabilizing clock synchronization in the presence of Byzantine faults, Journal of the ACM (JACM), v.51 n.5, p.780-799, September 2004 [doi>10.1145/1017460.1017463]
• 12: Shlomi Dolev , Reuven Yagel, Toward Self-Stabilizing Operating Systems, Proceedings of the Database and Expert Systems Applications, 15th International Workshop, p.684-688, August 30-September 03, 2004 [doi>10.1109/DEXA.2004.165]
• 13: Dolev, S. and Yagel, R. 2005. Memory management for self-stabilizing operating systems. In Self-Stabilizing Systems, T. Herman and S. Tixeuil, Eds. Lecture Notes in Computer Science, vol. 3764. Springer, 113--127.
• 14: Fox, A. and Patterson, D. 2003. Self-repairing computers. Scientific American.
• 15: Mohamed G. Gouda , F. Furman Haddix, The alternator, Workshop on Self-stabilizing Systems, p.48-53, June 05, 1999
• 16: M. G. Gouda , R. R. Howell , L. E. Rosier, The instability of self-stabilization, Acta Informatica, v.27 n.9, p.697-724, Sep. 1990
• 17: Yuri Gurevich, Evolving algebras 1993: Lipari guide, Specification and validation methods, Oxford University Press, Inc., New York, NY, 1995
• 18: Coding approaches to fault tolerance in combinational and dynamic systems, Kluwer Academic Publishers, Norwell, MA, 2001
• 19: Ted Herman , Imran Pirwani, A Composite Stabilizing Data Structure, Proceedings of the 5th International Workshop on Self-Stabilizing Systems, p.167-182, October 01-02, 2001
• 20: Jeffrey O. Kephart , David M. Chess, The Vision of Autonomic Computing, Computer, v.36 n.1, p.41-50, January 2003 [doi>10.1109/MC.2003.1160055]
• 21: Lamport, L., Shostak, R., and Pease, M. 1995. The byzantine generals problem. In Advances in Ultra-Dependable Distributed Systems, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press.
• 22: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 23: Lamport, L. 1986. On interprocess communication, part I: Basic formalism. Distrib. Comput. 1, 2, 77--85.
• 24: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 25: McGuire, T. M. and Gouda, M. G. 2005. The Austin Protocol Compiler. Springer-Verlag.
• 26: Mikhail Nesterenko , Anish Arora, Stabilization-Preserving Atomicity Refinement, Proceedings of the 13th International Symposium on Distributed Computing, p.254-268, September 27-29, 1999
• 27: Radia Perlman, Interconnections: bridges and routers, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 28: Plotkin, G. D. 1981. A Structural Approach to Operational Semantics. Tech. rep. DAIMI FN-19, University of Aarhus.
• 29: Premkishore Shivakumar , Michael Kistler , Stephen W. Keckler , Doug Burger , Lorenzo Alvisi, Modeling the Effect of Technology Trends on the Soft Error Rate of Combinational Logic, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.389-398, June 23-26, 2002
• 30: Andrew S. Tanenbaum, Structured computer organization (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

General Terms:
Algorithms, Languages, Reliability

Keywords:
Compilers, abstract state machines, self-stabilization