Parameterized Verification of Round-Based Distributed Algorithms via Extended Threshold Automata
Open Access
- 11 September 2024
- book chapter
- Published by Springer Nature
- p. 638-657
Abstract
Threshold automata are a computational model that has proven to be versatile in modeling threshold-based distributed algorithms and enabling their completely automatic parameterized verification. We present novel techniques for the verification of threshold automata, based on well-structured transition systems, that allow us to extend the expressiveness of both the computational model and the specifications that can be verified. In particular, we extend the model to allow decrements and resets of shared variables, possibly on cycles, and the specifications to general coverability. While these extensions of the model in general lead to undecidability, our algorithms provide a semi-decision procedure. We demonstrate the benefit of our extensions by showing that we can model complex round-based algorithms such as the phase king consensus algorithm and the Red Belly Blockchain protocol (published in 2019), and verify them fully automatically for the first time.Keywords
All Related Versions
This publication has 53 references indexed in Scilit:
- PyLTA: A Verification Tool for Parameterized Distributed Algorithms2023
- Parameterized Analysis of Reconfigurable Broadcast Networks2022
- Complexity of Verification and Synthesis of Threshold Automata2020
- Parameterized Verification of Systems with Global Synchronization and Guards2020
- Ivy: A Multi-modal Verification Tool for Distributed Algorithms2020
- ByMC: Byzantine Model Checker2018
- Consensus in One Communication Step2001
- Regular Model Checking2000
- Reducing Model Checking of the Many to the Few2000
- The minimal coverability graph for Petri netsLecture Notes in Computer Science, 1993