Software architecture styles as graph grammars

ABSTRACT

We present a formalism for the definition of software architectures in terms of graphs. Nodes represent the individual agents and edges define their interconnection. Individual agents can communicate only along the links specified by the architecture. The dynamic evolution of the overall architecture is defined independently by a 'coordinator'. An architecture style is a class of architectures characterised by a graph grammar. The rules of the coordinator are statically checked to ensure that they preserve the constraints imposed by the architecture style.

REFERENCES

• 1: Gregory Abowd , Robert Allen , David Garlan, Using style to understand descriptions of software architecture, ACM SIGSOFT Software Engineering Notes, v.18 n.5, p.9-20, Dec. 1993
• 2: Robert Allen , David Garlan, Formalizing architectural connection, Proceedings of the 16th international conference on Software engineering, p.71-80, May 16-21, 1994, Sorrento, Italy
• 3: Jean-Pierre Banâtre , Daniel Le Métayer, Programming by multiset transformation, Communications of the ACM, v.36 n.1, p.98-111, Jan. 1993 [doi>10.1145/151233.151242]
• 4: Jean-Pierre Bonâtre , Daniel Le Métayer, Gamma and the chemical reaction model: ten years after, Coordination programming: mechanisms, models and semantics, Imperial College Press, London, UK, 1996
• 5: Gérard Berry , Gérard Boudol, The chemical abstract machine, Theoretical Computer Science, v.96 n.1, p.217-248, 6 April 1992
• 6: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• 7: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 8: Pierpaolo Degano , Ugo Montanari, A model for distributed systems based on graph rewriting, Journal of the ACM (JACM), v.34 n.2, p.411-449, April 1987 [doi>10.1145/23005.24038]
• 9: P. Della Vigna and C. Ghezzi, Context-free gmph grammar, Information and Control, Vol. 37, pp. 207- 233, 1978.
• 10: P. Fradet and D. LeM~tayer, Structured Gamma, Irisa Research Report PI-989, March 1996.
• 11: David Garlan , Robert Allen , John Ockerbloom, Exploiting style in architectural design environments, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.175-188, December 06-09, 1994, New Orleans, Louisiana, United States
• 12: David Garlan , Dewayne E. Perry, Introduction to the Special Issue on Software Architecture, IEEE Transactions on Software Engineering, v.21 n.4, p.269-274, April 1995
• 13: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 14: A. A. Holzbacher, A Software Environment for Concurrent Coordinated Programming, Proceedings of the First International Conference on Coordination Languages and Models, p.249-266, April 15-17, 1996
• 15: Alexandra A. Holzbacher, Coordination of distributed and parallel programs: programs in ConCoord, Coordination programming: mechanisms, models and semantics, Imperial College Press, London, UK, 1996
• 16: Paola Inverardi , Alexander L. Wolf, Formal Specification and Analysis of Software Architectures Using the Chemical Abstract Machine Model, IEEE Transactions on Software Engineering, v.21 n.4, p.373-386, April 1995 [doi>10.1109/32.385973]
• 17: Rick Kazman , Len Bass , Mike Webb , Gregory Abowd, SAAM: a method for analyzing the properties of software architectures, Proceedings of the 16th international conference on Software engineering, p.81-90, May 16-21, 1994, Sorrento, Italy
• 18: J. Kramer, Configuration programming. A framework for the development of distributable systems, Proc. COMPEURO'90, IEEE, pp. 374-384, 1990.
• 19: Carl E. Landwehr, Formal Models for Computer Security, ACM Computing Surveys (CSUR), v.13 n.3, p.247-278, Sept. 1981 [doi>10.1145/356850.356852]
• 20: David C. Luckham , John J. Kenney , Larry M. Augustin , James Vera , Doug Bryan , Walter Mann, Specification and Analysis of System Architecture Using Rapide, IEEE Transactions on Software Engineering, v.21 n.4, p.336-355, April 1995 [doi>10.1109/32.385971]
• 21: J. Magee and J. Kramer, Modelling distributed software architectures, Proc. First int. workshop on Architectures for Software Systems, CMU Technical Report,CMU-CS-95-151, April 1995.
• 22: Nicolas Mercouroff, An Algorithm for Analyzing Communicating Processes, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, p.312-325, March 25-28, 1991
• 23: Robin Milner , Joachim Parrow , David Walker, A calculus of mobile processes, I, Information and Computation, v.100 n.1, p.1-40, Sept. 1992 [doi>10.1016/0890-5401(92)90008-4]
• 24: Mark Moriconi , Xiaolei Qian , R. A. Riemenschneider, Correct Architecture Refinement, IEEE Transactions on Software Engineering, v.21 n.4, p.356-3, April 1995 [doi>10.1109/32.385972]
• 25: Hanne Riis Nielson , Flemming Nielson, Higher-order concurrent programs with finite communication topology (extended abstract), Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.84-97, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174538]
• 26: Oscar Nierstrasz, Regular types for active objects, ACM SIGPLAN Notices, v.28 n.10, p.1-15, Oct. 1, 1993
• 27: Dewayne E. Perry , Alexander L. Wolf, Foundations for the study of software architecture, ACM SIGSOFT Software Engineering Notes, v.17 n.4, p.40-52, Oct. 1992 [doi>10.1145/141874.141884]
• 28: Jean-Claude Raoult , Frédéric Voisin, Set-Theoretic Graph Rewriting, Proceedings of the International Workshop on Graph Transformations in Computer Science, p.312-325, January 01, 1993
• 29: M. Shaw and D. Garlan, Formulations and formalisms in software architecture, Computer Science Today, Recent Trends and Developments, Springer Verlag, LNCS 1000, pp. 307-323, 1995.
• 30: Mary Shaw , Robert DeLine , Daniel V. Klein , Theodore L. Ross , David M. Young , Gregory Zelesnik, Abstractions for Software Architecture and Tools to Support Them, IEEE Transactions on Software Engineering, v.21 n.4, p.314-335, April 1995 [doi>10.1109/32.385970]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Languages
        D.2.10 Design**
            Subjects: Representation**

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Verification

Keywords:
coordination, graph rewriting, software architecture, static verification