Component compatibility and its verification

Craig, D.C. and Zuberek, W.M.

Proc. First Int. Workshop on Software Architecture Research and Practice (SARP-07), part of the 2-nd Int. Conf. on Digital Telecommunications (ICTD-07), Silicon Valley, 1-5 July 2007, pp.26-32.

Abstract:

An approach to verification of component compatibility is proposed in which each component's behavior (at its interfaces) is represented by a labeled Petri net in such a way that the sequences of services (provided or requested) correspond to sequences of labels assigned to occuring transitions. The behavior of a component can thus be defined as the language of its modeling net. Two interacting components are compatible if and only if all possible sequences of services requested by one of these two components can be satisfied by the other component; in other words, two components are compatible if the language of the requesting component is a subset of the language of the component providing the services. Verification of this simple relation depends upon the class of languages defining the behaviors of the components. If the languages are regular, the verification of compatibility is straightforward. For nonregular languages, a more elaborate approach is needed in which a net model composed of the interacting components is checked for the absense of deadlocks. Some applications of the proposed approach are also discussed.

Keywords:

Software components, component-based systems, component compatibility, compatilibility verification, Petri nets, deadlock detection, structural analysis.

References:

• S.T. Albin, The art of software architecture: design methods and techniques; Wiley 2003.
• K. Beck, Extreme Programming Explained: Embrace Change; Addison-Wesley 2000.
• B. Boehm, R. Turner, Balancing Agility and Discipline: A Guide for the Perplexed; Addison-Wesley Pearson Education 2004.
• E.R. Boer, T. Murata, "Generating basis siphons and traps of Petri nets using the sign incidence matrix", IEEE Trans. on Circuits and Systems, I - Fundamental Theory and Applications, vol.41, no.4, pp.266-271, 1994.
• A.W. Brown, "An overview of components and component-based development"; in Advances in Computers, vol.54 - Trends in Software Engineering, pp.1-34, Academic Press 2001.
• D. Bugden, Software Design (2nd ed.); Pearson Addison-Wesley 2003.
• F. Buschmann, R. Meunier, H. Rohnert, P. Sommerlad, M. Stal, Pattern-Oriented Software Architecture: A System of Patterns; J. Willey 1996.
• F. Chu, X. Xie, "Deadlock analysis of Petri nets using siphons and mathematical programming"; IEEE Trans. on Robotics and Automation, vol.13, no.6, pp.793-804, 1997.
• P. Clements, R. Kazman, M. Klein, Evaluating software architectures - methods and case studies; Addison-Wesley 2002.
• J.M. Colom, M. Silva, "Improving the linearly based characterization of p/t nets", in Advances in Petri Nets 1990 (Lecture Notes in Computer Science 483); pp.113-145, Springer-Verlag 1991.
• R. Cordone, L. Ferrarini, L. Piroddi, "Enumeration algorithms for minimal siphons in Petri ners based on place constraints"; IEEE Trans. on Systems, Man and Cybernetics - part A, vol.35, no.6, pp.855-854, 2005.
• D.C. Craig, "Compatibility of software components - modeling and verification"; Ph.D. Thesis, Department of Computer Science, Memorial University, St.John's, Canada A1B 3X5, 2006.
• D.C. Craig, W.M. Zuberek, "Compatibility of software components - modeling and verification"; Proc. Int. Conf. on Dependability of Computer Systems, Szklarska Poreba, Poland, pp.11-18, 2006.
• R. Enns, "NETCONF Configuration Protocol, Internet draft; http://www.ietf.org/rfc/rfc4741/txt, December 2006.
• E. Gamma, R. Helm, R. Johnson, J. Vlissides, Design Pattarns: Elements of Reusable Object-Oriented Software; Addison-Wesley 1995.
• J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to automata theory, languages, and computations (2 ed.); Addison Wesley 2001.
• A. Martens, "Usability of web services"; Porc. of the 4-th Int. Conf. on Web Information Systems Engineering Workshops, pp.182-190, IEEE CS 2003.
• S. Melzer, J. Esparza, "Checking system properties via integer programming" in Programming Languages and Systems, Proc. 6-th European Symp. on Programming Languages and Systems (Lecture Notes In Computer Science 1058), pp.250-264, Springer-Verlag 1996.
• W. Reisig, Petri nets - an introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• I. Sommerville, Software Engineering (6th ed.); Addison-Wesley 2001.
• A. Valmari, "The state explosion problem"; in Lectures on Petri Nets I: Basic Models (Lecture Notes in Computer Science 1491), pp.429-528, Springer-Verlag 1998.
• M. Weber, E. Kindler, "The Petri net markup language"; in Petri Net Technology for Communication-Based Systems (Lecture Notes in Computer Science 2472), pp.124-144, Springer-Verlag 2003.
• W.M Zuberek, "Timed Petri nets - definitions, properties and applications"; Microelectronics and Reliability (Special Issue on Petri Nets and Related Graph Models), vol.31, no.4, pp.627-644, 1991.

Keywords:

Software components, component-based systems, component compatibility, compatilibility verification, Petri nets, deadlock detection, structural analysis.

Available in pdf.