Verification of distributed and multi-agent systems using data analytics and message contents independence approach

点击翻译按钮获取中文摘要

Distributed software systems (DSS) are a class of software systems in which functionality and/or control are distributed. In DSS the way components interact is usually described by scenarios, e.g. sequence diagrams. Maintaining consistency among the scenarios in multiple design iteration is a complex and expensive task. Lack of centralized control and multiplicity of scenarios imply that there may be unintended/unexpected behavior during execution, commonly known as “emergent behavior” (EB) and “implied scenario” (IS). They may lead to costly and/or irreversible damage to the users, environment, and the business. Our goal in this research is to manage (i.e. model, analyze, detect and resolve) EB and IS by identifying design flaws that may lead to them. We focus on addressing the problems using novel social network analysis and data mining approach. The main focus is on detecting the “shared states” and “shared interactions”, which are the main culprits of EB and IS in a DSS, respectively. However, detecting shared states and/or interactions is not an easy task in terms of computational resources and complexity of the algorithms. We view a component’s behavior as a language equivalent to its state transition diagram. Similarly, interaction among components - as constrained by the design scenarios - are modeled by a graph similar to what is common in social networks. Clustering technique are applied to the strings of the language and the graph to identify common sequences of states and interactions. Largest frequent subset of shared states in string mining and higher changes of pairwise members in graph mining are suspects of causing EB and IS. Unique points in this research besides being computationally manageable are: (1) Modeling both interactions of components and their internal states together that saves the components’ states and preserves the interaction information among the components; (2) Using interaction information to detect potential problems; (3) Ability to investigate whether new path can exist between components based on identified interactions; (4) Ability to suggest solutions based on exact cause of the detected problem; (5) Ability to investigate interactions of the same-type components/agents. This research has a solid theoretical basis and a fully implemented system. Through both simulated and detailed case studies applied to various domain problems we will show the efficiency and effectiveness of the approach. This research provides a cost effective solution to model-based verification of DSS which appeals to a large audience, namely medium/large companies. It has great potential for lightweight software development processes, especially appealing to Agile developers. Although formal models and Agile methodologies are generally considered immiscible, our research shows that “just enough” documentation is “good enough” to produce useful results.