The algebra of connectors: structuring interaction in BIP

ABSTRACT

We provide an algebraic formalisation of connectors in BIP. These are used to structure interactions in a component-based system. A connector relates a set of typed ports. Types are used to describe different modes of synchronisation: rendezvous and broadcast, in particular.

Connectors on a set of ports P are modelled as terms of the algebra AC(P), generated from P by using a binary fusion operator and a unary typing operator. Typing associates with terms (ports or connectors) synchronisation types - trigger or synchron - , which determine modes of synchronisation. Broadcast interactions are initiated by triggers. Rendezvous is a maximal interaction of a connector including only synchrons.

The semantics of AC(P) associates with a connector the set of its interactions. It induces on connectors an equivalence relation which is not a congruence as it is not stable for fusion. We provide a number of properties of AC(P) used to symbolically simplify and handle connectors. We provide examples illustrating applications of AC(P), including a general component model encompassing synchrony, methods for incremental model decomposition, and efficient implementation by using symbolic techniques.

REFERENCES

• 1: Farhad Arbab, Abstract behavior types: a foundation model for components and their composition, Science of Computer Programming, v.55 n.1-3, p.3-52, March 2005 [doi>10.1016/j.scico.2004.05.010]
• 2: Felice Balarin , Yosinori Watanabe , Harry Hsieh , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli, Metropolis: An Integrated Electronic System Design Environment, Computer, v.36 n.4, p.45-52, April 2003 [doi>10.1109/MC.2003.1193228]
• 3: Krishnakumar Balasubramanian , Aniruddha Gokhale , Gabor Karsai , Janos Sztipanovits , Sandeep Neema, Developing Applications Using Model-Driven Design Environments, Computer, v.39 n.2, p.33, February 2006 [doi>10.1109/MC.2006.54]
• 4: Ananda Basu , Marius Bozga , Joseph Sifakis, Modeling Heterogeneous Real-time Components in BIP, Proceedings of the Fourth IEEE International Conference on Software Engineering and Formal Methods, p.3-12, September 11-15, 2006 [doi>10.1109/SEFM.2006.27]
• 5: A. Basu, L. Mounier, M. Poulhiès, J. Pulou, and J. Sifakis. Using BIP for modeling and verification of networked systems - A case study on TinyOS-based networks. Technical Report TR-2007-5, VERIMAG, 2007. http://www-verimag.imag.fr/index.php?page=techrep-list.
• 6: A. Benveniste, P. Caspi, S. A. Edwards, N. Halbwachs, P. L. Guernic, and R. de Simone. The synchronous languages twelve years later. Proc. of the IEEE, Special Issue on Embedded Systems, 91(1):64--83, 2003.
• 7: Marco Bernardo , Paolo Ciancarini , Lorenzo Donatiello, On the formalization of architectural types with process algebras, ACM SIGSOFT Software Engineering Notes, v.25 n.6, p.140-148, Nov. 2000
• 8: BIP. http://www-verimag.imag.fr/~async/index.php?view=components.
• 9: S. Bliudze and J. Sifakis. The algebra of connectors - structuring interaction in BIP. Technical Report TR-2007-3, VERIMAG, 2007. http://www-verimag.imag.fr/index.php?page=techrep-list.
• 10: R. Bruni, J. L. Fiadeiro, I. Lanese, A. Lopes, and U. Montanari. New insights on architectural connectors. In J.-J. Lévy, E. W. Mayr, and J. C. Mitchell, editors, IFIP TCS, pages 367--380. Kluwer, 2004.
• 11: Cω. http://research.microsoft.com/comega/.
• 12: J. Eker, J. Janneck, E. Lee, J. Liu, X. Liu, J. Ludvig, S. Neuendorffer, S. Sachs, and Y. Xiong. Taming heterogeneity: The Ptolemy approach. Proceedings of the IEEE, 91(1):127--144, 2003.
• 13: JosT Luiz Fiadeiro, Categories for Software Engineering, SpringerVerlag, 2004
• 14: G. Gö&@223;ler and J. Sifakis. Component-based construction of deadlock-free systems: Extended abstract. In P. K. Pandya and J. Radhakrishnan, editors, FSTTCS, volume 2914 of Lecture Notes in Computer Science, pages 420--433, Mumbai, India, Dec. 2003. Springer.
• 15: Gregor Gössler , Joseph Sifakis, Composition for component-based modeling, Science of Computer Programming, v.55 n.1-3, p.161-183, March 2005 [doi>10.1016/j.scico.2004.05.014]
• 16: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 17: F. Maraninchi and Y. Rémond. Argos: an automaton-based synchronous language. Computer Languages, 27:61--92, 2001.
• 18: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 19: nesC: A programming language for deeply networked systems. http://nescc.sourceforge.net/.
• 20: Joseph Sifakis, A Framework for Component-based Construction Extended Abstract, Proceedings of the Third IEEE International Conference on Software Engineering and Formal Methods, p.293-300, September 07-09, 2005 [doi>10.1109/SEFM.2005.3]
• 21: Bridget Spitznagel , David Garlan, A compositional formalization of connector wrappers, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Theory