Parameterized Verification of Distributed Algorithms in Dynamic Graphs

Examensarbete för masterexamen

Använd denna länk för att citera eller länka till detta dokument: https://hdl.handle.net/20.500.12380/304456
Ladda ner:
Fil Beskrivning StorlekFormat 
CSE 22-03 Kokkou.pdfParameterized Verification of Distributed Algorithms in Dynamic Graphs1.45 MBAdobe PDFVisa
Bibliografiska detaljer
FältVärde
Typ: Examensarbete för masterexamen
Titel: Parameterized Verification of Distributed Algorithms in Dynamic Graphs
Författare: Kokkou, Maria
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.
Nyckelord: Parameterized verification;distributed computing;mobile agents;dynamic graphs;thesis
Utgivningsdatum: 2022
Utgivare: Chalmers tekniska högskola / Institutionen för data och informationsteknik
URI: https://hdl.handle.net/20.500.12380/304456
Samling:Examensarbeten för masterexamen // Master Theses



Materialet i Chalmers öppna arkiv är upphovsrättsligt skyddat och får ej användas i kommersiellt syfte!