Monotonic Abstraction in Action

Parosh Aziz Abdulla, Giorgio Delzanno, Ahmed Rezine

We consider verification of safety properties for parameterized distributed protocols. Such a protocol consists of an arbitrary number of (infinite-state) processes that communicate asynchronously over FIFO channels. The aim is to perform parameterized verification, i.e., showing correctness regardless of the number of processes inside the system. We consider two non-trivial case studies: the distributed Lamport and Ricart-Agrawala mutual exclusion protocols. We adapt the method of monotonic abstraction that considers an over-approximation of the system, in which the behavior is monotonic with respect to a given pre-order on the set of configurations. We report on an implementation which is able to fully automatically verify mutual exclusion for both protocols.

In Proceedings of the 5th international colloquium on Theoretical Aspects of Computing, 2008,

Last version (pdf) 2008