Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Calgary

$22,000.00

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

FY 2016-17

Summary
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.
Program
Discovery Grants Program - Individual
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2016-04067
Name nom
Far, Behrouz
Department département
Electrical and Computer Engineering - Electrical and Computer Engineering
Organization id
11
Institution établissement
University of Calgary
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
22000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2706
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Software engineering
Research subject fr
Génie logiciel
Partie
1
Nb partie
1
Application title
Verification of distributed and multi-agent systems using data analytics and message contents independence approach
Keyword
NSERC
Application summary
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.