Skip to main content
SpringerLink
Log in

An analysis of the cost of validating semantic composability

  • Article
  • Published:
Journal of Simulation

Abstract

Validation of semantic composability is a non-trivial problem and a key step in component-based modelling and simulation. Recent work in semantic composability validation promises to reduce verification, validation, and accreditation efforts. However, the underlying cost of current validation approaches can undermine the promised benefits, and the trade-off between validation accuracy and validation cost is not well understood. In this paper we present, to the best of our knowledge, the first quantitative study on the cost of validating semantic composability. Our study covers four representative validation approaches, including two DEVS-based methods, Petty and Weisel formal validation, and deny-validity, and for simplicity, we use computation time as a measure of validation cost. For a queueing model with 1000 components, there is significant trade-off between validation accuracy and cost, with the time-based deny-validity costing seven times that of timeless Petty and Weisel formalism.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6

Similar content being viewed by others

Notes

  1. We ensured that models with invalid syntax were eliminated using an approach based on compositional grammars expressed in EBNF (Teo and Szabo, 2008).

  2. In particular, provided that the transformation from the meta-model to integers is sound, the algorithm to determine mathematical composability could employ a Radix sort algorithm (Knuth, 1997) to first sort the integer values, followed by an inclusion check, resulting in O(kn) steps, where n is the number of elements in the interval, and k is the average element length.

  3. However, the validation of component coordination using model checking remains capped to reduce state space explosion.

References

  • Balci O (1997). Verification, validation and accreditation of simulation models. In: Andradóttir S, Healy KJ, Withers DH and Nelson BL (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 135–141.

  • Balci O and Sargent RG (1981). A methodology for cost-risk analysis in the statistical validation of simulation models. Communications of the ACM 24 (4): 190–197.

    Article  Google Scholar 

  • Balci O and Sargent RG (1982). Some examples of simulation model validation using hypothesis testing. In: Chao YW, Madrigal O and Highland HJ (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 621–629.

  • Banks J, Carson JS, Nelson BL and Nicol DM (2005). Discrete Event System Simulation. Prentice-Hall: USA.

    Google Scholar 

  • Bartholet RG, Brogan BC, Reynolds PP and Carnahan JC (2004). In search of the philosopher's stone: Simulation composability versus component-based software design. In: Smith J, Peters B, Ingalls RG and Rossetti MD (eds). Proceedings of the Fall Simulation Interoperability Workshop, (PCE) Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA.

  • Ben-Ari M (2008). Principles of the Spin Model Checker, Springer Verlag: Berlin.

    Google Scholar 

  • Choco Constraint Programming System. http://sourceforge.net/projects/choco/, accessed January 2010.

  • Cowie J (1999). Towards realistic million-node internet simulations. In: Arabnia HR (ed). Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications, CSREA Press: Las Vegas, USA, pp 2129–2135.

  • Dalle O (2006). OSA: An open component-based architecture for discrete-event simulation. In: Burotzky W (ed). Proceedings of the 20th European Conference on Modeling and Simulation, Society of Modeling and Simulation Europe: Leipzig, Germany.

  • Davis PK and Anderson RH (2003). Improving the composability of Department of Defense models and simulations.

  • Defense Modeling and Simulation Office (DMSO) (1996). Verification, validation, and accreditation recommended practices guide. U.S. Department of Defense. Office of the Director of Defense Research and Engineering.

  • Department of the Navy (2004). Modeling and Simulation Verification, Validation, and Accreditation Implementation Handbook. Department of the Navy, http://nmso.navy.mil/NMSODigitalLibrary.aspx?Command=Core_Download&EntryId=3988.

  • Duke R, King P and Rose G (1991). The Object-Z Specification Language: Version 1. Technical Report, http://www.dc.uba.ar/people/materias/isoft1/papers/tr91-1.pdf.

  • Garavel H, Lang F, Mateescu R and Serwe W (2007). CADP 2006: A toolbox for the construction and analysis of distributed processes. In: Werner D and Holger H (eds). Proceedings of the 19th International Conference on Computer Aided Verification, Springer Verlag: Bonn, Germany, pp 158–163.

  • Gore R and Reynolds PP (2008). Applying causal inference to understand emergent behavior. In: Mason SJ, Hill R, Moench L and Rose O (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 712–721.

  • Gustavson P and Root L (1999). Object model use cases: A mechanism for capturing requirements and supporting BOM reuse. In: Hieb M and Blalock J (eds). Spring Simulation Interoperability Workshop, Simulation Interoperability Standards Organization: Orlando, USA.

  • Kasputis S and Ng HC (2000). Composable simulations. In: Joines JA and Barton RlR (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 1577–1584.

  • Kennedy KE (2003). Formal methods in the verification and validation of simulation models. In: Mason SJ and Hill R (eds). Proceedings of the Spring Simulation Interoperability Workshop, Simulation Interoperability Standards Organization: Orlando, USA.

  • Knuth DE (1997). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley: Reading, MA.

    Google Scholar 

  • Love G and Back G (2000). Model verification and validation for rapidly developed simulation models: Balancing cost and theory. In: Davidsen PI, Ford DN and Mashayekhi, AN (eds). Proceedings of the 18th International Conference of the System Dynamics Society, Bergen, Norway.

  • Moradi F et al (2007). A rule-based approach to syntactic and semantic composition of BOMs. In: Roberts DJ, Theodoropoulos GK and Saddik AEl (eds). Proceedings of the 11th IEEE Symposium on Distributed Simulation and Real-Time Applications, Systems Dynamics Society, IEEE Computer Society: Crete, Greece, pp 145–155.

  • Pace DK (2004). Modeling and simulation verification and validation challenges. Johns Hopkins APL Technical Digest 25 (3): 163–172.

    Google Scholar 

  • Petty MD and Weisel EW (2003a). A composability lexicon. In: Mason SJ and Hill R (eds). Proceedings of the Spring Simulation Interoperability Workshop, Simulation Interoperability Standards Organization: Orlando, USA, pp 181–187.

  • Petty MD and Weisel EW (2003b). Basis for a theory of semantic composability. In: Mason SJ and Hill R (eds). Proceedings of the Spring Simulation Interoperability Workshop, Simulation Interoperability Standards Organization: Orlando, USA.

  • Petty MD, Weisel EW and Mielke R (2005). Composability theory overview and update. In: Hill R and Rose O (eds). Proceedings of the Spring Simulation Interoperability Workshop, Simulation Interoperability Standards Organization: Orlando, USA.

  • Saaltink M (1997). The Z/EVES system. Lecture Notes in Computer Science 1212 (1): 72–85.

    Article  Google Scholar 

  • Sargent R (2000). Verification, validation, and accreditation of simulation models. In: Joines JA and Barton RlR (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 50–59.

  • Sargent RG (1979). Validation of simulation models. In: Highland HJ, Spiegel MG and Shannon R (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 497–503.

  • Smith G (2000). The Object-Z Specification Language. Kluwer Academic Publishers: Dordrecht, MA.

    Book  Google Scholar 

  • Smith G, Kamm?ller F and Santen T (2002). Encoding object-z in Isabelle/HOL. In: Bert D, Bowen JP, Henson MC and Robinson K (eds). Proceedings of the International Conference of B and Z Users, Springer Verlag: London, UK, pp 82–89.

  • Srba J (2001). On the power of labels in transition systems. In: Larsen KG and Nielsen M (eds). Proceedings of the 12th International Conference on Concurrency Theory, Springer Verlag: Aalborg, Denmark, pp 277–291.

  • Szabo C and Teo YM (2009). An approach for validation of semantic composability in simulation models. In: Hill R and Moench L (eds). Proceedings of the 23rd ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation, IEEE Computer Society: New York, USA, pp 3–10.

  • Szabo C, Teo YM and See S (2009). A time-based formalism for the validation of semantic composability. In: Rossetti M, Hill R, Johansson B and Dunkin A et al (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 1411–1422.

  • Teo YM and Szabo C (2008). CODES: An integrated approach to composable modeling and simulation. In: Roberts DJ and Karatza H (eds). Proceedings of the 41st Annual Simulation Symposium, IEEE Computer Society: Ottawa, Canada, pp 103–110.

  • Tolk A (2006). What comes after the semantic web—PADS implications for the dynamic web. In: Turner S and Riley G (eds). Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, IEEE Computer Society: Singapore, pp 55–62.

  • Tolk A, Diallo SY and Turnitsa CD (2008). Mathematical models towards self-organizing formal federation languages based on conceptual models of information exchange capabilities. In: Mason SJ, Hill R, Moench L and Rose O (eds). Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 966–974.

  • Traore MK (2006). Analyzing static and temporal properties of simulation models. In: Lawson B, Liu J, Perrone F and Wieland F et al (eds). Proceedings of the Winter Simulation Conference, Institute of Electrical and Electronics Engineers Inc.: Piscataway, New Jersey, USA, pp 897–904.

  • Trojet MW, Frydman C and Hamri ME-A (2009). Practical application of lightweight Z in DEVS framework. In: Spiegel MG and Shannon R (eds). Proceedings of the Spring Simulation Multiconference, Simulation Interoperability Standards Organization: Orlando, USA.

  • Wainer G, Morihama L and Passuello V (2002). Automatic verification of DEVS Models. In: Liu J and Hill R (eds). Proceedings of the SISO Spring Interoperability Workshop, Simulation Interoperability Standards Organization: Orlando, USA.

  • Zeigler BP, Praehofer H and Kim TG (2000). Theory of Modeling and Simulation. Academic Press: New York.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The University of Adelaide, Adelaide, Australia

    C Szabo

  2. National University of Singapore, Singapore

    Y M Teo

Authors
  1. C Szabo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Y M Teo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to C Szabo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Szabo, C., Teo, Y. An analysis of the cost of validating semantic composability. J Simulation 6, 152–163 (2012). https://doi.org/10.1057/jos.2012.11

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jos.2012.11

Keywords

Search

Navigation