Post-mortem analysis of emergent behavior in complex simulation models

ABSTRACT

Analyzing and validating emergent behavior in component-based models is increasingly challenging as models grow in size and complexity. Despite increasing research interest, there is a lack of automated, formalized approaches to identify emergent behavior and its causes. As part of our integrated framework for understanding emergent behavior, we propose a post-mortem emergence analysis approach that identifies the causes of emergent behavior in terms of properties of the composed model and properties of the individual model components, and their interactions. In this paper, we detail the use of reconstructability analysis for post-mortem analysis of known emergent behavior. The two-step process first identifies model components that are most likely to have caused emergent behavior, and then analyzes their interaction. Our case study using small and large examples demonstrates the applicability of our approach.

References

1. M. Bedau. Weak Emergence. Philosophical Perspectives, 11:375--399, 1997.
2. R. Cavallo and G. Klir. Reconstructability Analysis of Multi-dimensional Relations: A Theoretical Basis for Computer-aided Determination of Acceptable System Models. Int. Journal of General Systems, 5:143--171, 1979.
3. W. Chan, Y. S. Son, and C. M. Macal. Simulation of Emergent Behavior and Differences Between Agent-Based Simulation and Discrete-Event Simulation. In Proceedings of the Winter Simulation Conference, pages 135--150, 2010.
4. W. K. V. Chan. Interaction Metric of Emergent Behaviors in Agent-based Simulation. In Proceedings of the Winter Simulation Conference, pages 357--368, Phoenix, USA, 2011.
5. C. Chen, S. B. Nagl, and C. D. Clack. Specifying, Detecting and Analysing Emergent Behaviours in Multi-Level Agent-Based Simulations. In Proceedings of the Summer Computer Simulation Conference, 2007.
6. L. Chi. Transplating Social Capital to the Online World: Insights from Two Experimental Studies. Journal of Organizational Computing and Electronic Commerce, 19:214--236, 2009.
7. P. Cilliers. Complexity & Postmodernism. Routledge, 1998.
8. P. Davis. New Paradigms and Challenges. In Proceedings of the Winter Simulation Conference, Orlando , USA, 2005.
9. U. Fayyad and R. Uthurusamy. Evolving Data Into Mining Solutions for Insights. Communications of the ACM, 45, 2002.
10. S. Floyd and V. Jacobson. The synchronization of Periodic Routing Messages. In Proceedings of SIGCOMM, pages 33--44, 1993.
11. M. Gardner. The Fantastic Combinations of John Conway's New Solitaire Games. Mathematical Games, 1970.
12. C. Gershenson and N. Fernandez. Complexity and Information: Measuring Emergence, Self-organization, and Homeostatis at Multiple Scales. Complexity, 2012.
13. R. Gore and P. Reynolds. An Exploration-based Taxonomy for Emergent Behavior Analysis in Simulation. In Proceedings of the Winter Simulation Conference, pages 1232--1240, Miami, USA, 2007.
14. R. Gore and P. Reynolds. Applying Causal Inference to Understand Emergent Behavior. In Proceedings of the Winter Simulation Conference, pages 712--721, Miami, USA, 2008.
15. J. Holland. Emergence, From Chaos to Order. Basic Books, 1999.
16. O. T. Holland. Taxonomy for the Modeling and Simulation of Emergent Behavior Systems. In Proceedings of the 2007 Spring Simulation Multiconference, pages 28--35, 2007.
17. C. W. Johnson. What are Emergent Properties and How Do They Affect the Engineering of Complex Systems? Reliability Engineering and System Safety, 12:1475--1481, 2006.
18. A. Kubik. Towards a Formalization of Emergence. Journal of Artificial Life, 9:41--65, 2003.
19. E. Manley and T. Cheng. Understanding Road Congestion as an Emergent Property of Traffic Networks. In Proceedings of International Multiconference on Complexity, Informatics and Cybernetics, pages 109--114, 2010.
20. J. C. Mogul. Emergent (mis)behavior vs. Complex Software Systems. In Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems, pages 293--304, New York, USA, 2006.
21. Occam. Occam reconstructability analysis: http://dmm.sysc.pdx.edu/, Last retrieved Feb. 2013.
22. E. Page and J. Opper. Observations on the Complexity of Composable Simulations. In Proceedings of the Winter Simulation Conference, volume 1, pages 553--560, Phoenix, USA, 1999.
23. M. Prokopenko, F. Boschetti, and A. J. Ryan. An Information-theoretic Primer of Complexity, Self-organization and Emergence. Complexity, 15:11--28, 2009.
24. K. K. Ramakrishnan and H. Yang. The Ethernet Capture Effect: Analysis and Solution. In Proceedings of the IEEE Local Computer Networks Conference, Minneapolis, USA, 1994.
25. C. Reynolds. Flocks, Herds, and Schools: A Distributed Behavioral Model. In Proceedings of ACM SIGGRAPH, pages 25--34, 1987.
26. A. K. Seth. Measuring Emergence via Nonlinear Granger Causality. In Proceedings of the Eleventh International Conference on the Simulation and Synthesis of Living Systems, pages 545--553, 2008.
27. C. Szabo, Y. Teo, and S. See. An Integrated Approach for the Validation of Emergence in Component-based Simulation Models. In Proceedings of the Winter Simulation Conference, pages 2412--2423, 2012.
28. C. Szabo and Y. M. Teo. Semantic Validation of Emergent Properties in Component-based Simulation Models. Ontology, Epistemology, and Teleology of Modeling and Simulation -- Philosophical Foundations for Intelligent M&S Applications, pages 319--333, 2012.
29. Y. Teo and C. Szabo. CODES: An Integrated Approach to Composable Modeling and Simulation. In Proceedings of the 41st Annual Simulation Symposium, pages 103--110, Ottawa, Canada, 2008.
30. M. Treiber and A. Kesting. Traffic Flow Dynamics. Springer, 2013.
31. B.-Y. Yaneer. A Mathematical Theory of Strong Emergence using Multiscale Variety. Complexity, 9:15--24, 2004.
32. M. Zwick. An Overview of Reconstructability Analysis. Kybernetes, 33:877--905, 2004.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Validation

• Software and its engineering

  • Software creation and management

    • Software verification and validation

      • Empirical software validation

      • Process validation