Verifying Recurrence Properties in Self-Stabilization by Checking the Absence of Finite Counterexamples

Oday Jubran and Eike Möhlmann and Oliver E. Theel
Stabilization, Safety, and Security of Distributed Systems - 17th International Symposium, {SSS} 2015
A performance-related property of a system can be defined as the ratio of states satisfying some condition in each execution of the system, which we signify as the recurrence of the condition in the execution. In this work, we concern self-stabilization with respect to this property: the convergence to an execution that guarantees a minimum recurrence of a condition. For a system exhibiting infinite executions, it may not be straightforward to verify that the system satisfies the property, while considering the convergence as well. Towards simplifying such a verification, we show that for each system violating the property, there exists a finite execution prefix that is a counterexample with a reasonably short length. Furthermore, we exploit model checking to verify the absence of such counterexamples, to conclude that a system satisfies its property. We apply this approach by using the nuXmv model checker to analyze the service time of a self-stabilizing mutual exclusion algorithm having a finite state space, and running over many topologies.
Lecture Notes in Computer Science (LNCS)
Andrzej Pelc and Alexander A. Schwarzmann