Grant: Discovery Grants Program - Individual
Université de Sherbrooke
$46,000.00
Efficient verification of concurrent and distributed infinite-state systems
FY 2024-25
Summary
Concurrent and distributed systems are becoming more widespread as advances are made on multiprocessor architectures, cheap low-power devices, and natural computing. It is challenging to develop such systems in a reliable way, especially in the context of critical systems whose malfunction can, e.g., endanger lives, harm the environment, damage expensive equipment, or leak private data. Algorithmic verification is a powerful method that can be used to tackle this task. It involves abstracting concurrent or distributed systems into mathematical models which can then be analyzed exhaustively, rigorously and automatically. Most concurrent and distributed systems of practical use have infinitely many configurations. Unfortunately, central verification problems for infinite-state systems suffer from tremendously high computational complexity. Despite this, there has been important progress on the algorithmic verification of infinite-state systems. However, current techniques based on exact algorithms seem to have reached a ceiling, and hence new insights are needed to scale further. I intend to break this ceiling by developing a novel and unified theoretical framework of low complexity infinite-state systems (LCIS). This will be achieved incrementally by (a) studying relaxations of extended Petri nets, a prominent class of LCIS; (b) by demonstrating the applicability and efficiency of the theory to the verification of crowd systems, an emerging paradigm of distributed computing; and (c) by laying the foundations of an abstract LCIS framework inspired by the theory of well-structured transition systems.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2019-06039
Name nom
Blondin, Michael
Department département
Département d'informatique
Organization id
68
Institution établissement
Université de Sherbrooke
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2019
Award amount
46000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Efficient verification of concurrent and distributed infinite-state systems
Keywords
concurrency theory; model checking; formal verification; automata theory; petri nets; computational complexity
Application summary
Concurrent and distributed systems are becoming more widespread as advances are made on multiprocessor architectures, cheap low-power devices, and natural computing. It is challenging to develop such systems in a reliable way, especially in the context of critical systems whose malfunction can, e.g., endanger lives, harm the environment, damage expensive equipment, or leak private data. Algorithmic verification is a powerful method that can be used to tackle this task. It involves abstracting concurrent or distributed systems into mathematical models which can then be analyzed exhaustively, rigorously and automatically. Most concurrent and distributed systems of practical use have infinitely many configurations. Unfortunately, central verification problems for infinite-state systems suffer from tremendously high computational complexity. Despite this, there has been important progress on the algorithmic verification of infinite-state systems. However, current techniques based on exact algorithms seem to have reached a ceiling, and hence new insights are needed to scale further. I intend to break this ceiling by developing a novel and unified theoretical framework of low complexity infinite-state systems (LCIS). This will be achieved incrementally by (a) studying relaxations of extended Petri nets, a prominent class of LCIS; (b) by demonstrating the applicability and efficiency of the theory to the verification of crowd systems, an emerging paradigm of distributed computing; and (c) by laying the foundations of an abstract LCIS framework inspired by the theory of well-structured transition systems.