Guard Automata for the Verification of Safety and Liveness of Distributed Algorithms Article Swipe

View

Related Concepts

Liveness Guard (computer science) Computer science Correctness Soundness Automaton Reachability Distributed algorithm Algorithm Theoretical computer science Model checking Distributed computing Mutual exclusion Abstraction Predicate abstraction Finite-state machine Programming language Philosophy Epistemology

Nathalie Bertrand , Bastien Thomas , Josef Widder ·

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.4230/lipics.concur.2021.15 · OA: W3193655279

Distributed algorithms typically run over arbitrary many processes and may involve unboundedly many rounds, making the automated verification of their correctness challenging. Building on domain theory, we introduce a framework that abstracts infinite-state distributed systems that represent distributed algorithms into finite-state guard automata. The soundness of the approach corresponds to the Scott-continuity of the abstraction, which relies on the assumption that the distributed algorithms are layered. Guard automata thus enable the verification of safety and liveness properties of distributed algorithms.