Parameterized Verification of Distributed Algorithms in Dynamic Graphs
Ladda ner
Typ
Examensarbete för masterexamen
Program
Publicerad
2022
Författare
Kokkou, Maria
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Problems set in dynamic graphs have recently been gaining more attention. However,
automated verification methods for the proposed solutions to these problems
have not yet been studied. We aim in this work to provide some first results in this
direction by focusing on distributed algorithms set in dynamic rings.
This work consists of three main parts. We provide a formalization of the mobile
agents and algorithms that are used to solve known problems from the distributed
computing literature. We then show that under the most common assumptions for
mobile agent capabilities, constructing an automated decision procedure for algorithms
that solve the distributed computing problems in dynamic rings is undecidable.
Finally, we use a different framework for algorithmic verification called “Regular
Model Checking”. In this part, we provide a method to transform algorithms
that solve the problems that we study in dynamic graphs into the components that
are needed for the application of regular model checking techniques.
Beskrivning
Ämne/nyckelord
Parameterized verification , distributed computing , mobile agents , dynamic graphs , thesis