The Paxos distributed consensus algorithm is a challenging case-study for standard, vector-based model checking techniques. Due to asynchronous communication, exhaustive analysis may generate very large state spaces already for small model instances. In this paper, we show the advantages of graph transformation as an alternative modelling technique. We model Paxos in a rich declarative transformation language, featuring (among other things) nested quantifiers, and we validate our model using the GROOVE model checker, a graph-based tool that exploits isomorphism as a natural way to prune the state space via symmetry reductions. We compare the results with those obtained by the standard model checker Spin on the basis of a vector-based encoding of the algorithm.
|Name||Electronic Proceedings in Theoretical Computer Science|
|Workshop||3rd Workshop on GRAPH Inspection and Traversal Engineering, GRAPHITE 2014|
|Period||5/04/14 → 5/04/14|
|Other||5 April 2014|
- Graph Transformation
- Consensus Protocols
- Model Checking