A calculus of superimpositions for distributed systems

ABSTRACT

A superimposition is a program module that can augment an underlying distributed program with added functionality, while cutting across usual language modularity constructs like processes, packages, or objects. Two ways of combining superimpositions to create new superimpositions are presented. In sequential combinations a new superimposition is obtained that is equivalent to first applying one, and then applying the second to the result. In merging combinations, it is as if each component superimposition is applied independently to a basic program, without mutual influences.In both cases the applicability conditions and the result assertions of the component superimpositions are compared and used to determine whether the combination is possible. If so, they are then combined along with the code of the components to obtain both the specification and the code of the resultant superimposition, without considering any specific basic program. By using combinations of superimpositions from libraries, fewer components need be constructed manually, and programming techniques for independent issues can be codified. Among the examples we consider are versions of dining philosopher algorithms (exemplifying different scheduling techniques), a superimposition to make a program with a fixed number of processes able to handle process addition and deletion, and snapshot algorithms.

REFERENCES

• 1: R. J. R. Back and K. Sere. Superposition refinement of reactive systems. Formal Aspects of Computing, 8(3):324-346, 1996.
• 2: Valmir C. Barbosa , Eli Gafni, Concurrency in heavily loaded neighborhood-constrained systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.562-584, Oct. 1989 [doi>10.1145/69558.69560]
• 3: L. Bougé , N. Francez, A compositional approach to superimposition, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.240-249, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73581]
• 4: K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 5: E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.2, p.244-263, April 1986 [doi>10.1145/5397.5399]
• 6: Edmund M. Clarke, Jr. , Orna Grumberg , Doron A. Peled, Model checking, MIT Press, Cambridge, MA, 2000
• 7: N. Francez and I. Forman. Interacting Processes. Addison-Wesley, 1996.
• 8: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 9: H.-M. Järvinen , R. Kurki-Suonio , M. Sakkinen , K. Systä, Object-oriented specification of reactive systems, Proceedings of the 12th international conference on Software engineering, p.63-71, March 26-30, 1990, Nice, France
• 10: Shmuel Katz, A superimposition control construct for distributed systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.337-356, April 1993 [doi>10.1145/169701.169682]
• 11: Shmuel Katz , Joseph Gil, Aspects and Superimpositions, Proceedings of the Workshop on Object-Oriented Technology, p.308-309, June 14-18, 1999
• 12: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 13: G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In Proceedings ECOOP'97, LNCS 1241, pages 220-242, Jun 1997.
• 14: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques

General Terms:
Design, Languages