Parameterized Verification of Distributed Algorithms in Dynamic Graphs

Visa enkel post
dc.contributor.authorKokkou, Maria
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data och informationstekniksv
dc.contributor.examinerAhrendt, Wolfgang
dc.contributor.supervisorPiterman, Nir
dc.date.accessioned2022-01-27T10:27:07Z
dc.date.available2022-01-27T10:27:07Z
dc.date.issued2022sv
dc.date.submitted2020
dc.description.abstractProblems 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.sv
dc.identifier.coursecodeDATX05sv
dc.identifier.urihttps://hdl.handle.net/20.500.12380/304456
dc.language.isoengsv
dc.setspec.uppsokTechnology
dc.subjectParameterized verificationsv
dc.subjectdistributed computingsv
dc.subjectmobile agentssv
dc.subjectdynamic graphssv
dc.subjectthesissv
dc.titleParameterized Verification of Distributed Algorithms in Dynamic Graphssv
dc.type.degreeExamensarbete för masterexamensv
dc.type.uppsokH
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
CSE 22-03 Kokkou.pdf
Storlek:
1.42 MB
Format:
Adobe Portable Document Format
Beskrivning:
Parameterized Verification of Distributed Algorithms in Dynamic Graphs
Ladda ner
License bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
license.txt
Storlek:
1.51 KB
Format:
Item-specific license agreed upon to submission
Beskrivning:
Ladda ner
Samling
Examensarbeten för masterexamen