Correctness Verification of Mutual Exclusion Algorithms by Model Checking

Abstract

Mutual exclusion algorithms are at the heart of concurrent/parallel and distributed systems. It is well known that such algorithms are very difficult to analyze, and in the literature, different conjectures about starvation freedom and the number of by-passes (also called the overtaking factor) exist. The overtaking factor affects the (hopefully) bounded waiting time that a process competing for entering the critical section has to suffer before accessing the shared resource. This paper proposes a novel modeling approach based on Timed Automata and the Uppaal toolset, which proves effective for studying all the properties of a mutual exclusion algorithm for N≥2 processes, by exhaustive model checking. Although the approach, as already confirmed by similar experiments reported in the literature, is not scalable due to state explosion problems and can be practically applied until N≤5, it is of great value for revealing the true properties of analyzed algorithms. For dimensions N>5, the Statistical Model Checker of Uppaal can be used, which, although based on simulations, can confirm properties by estimations and probabilities. This paper describes the proposed modeling and verification method and applies it to several mutual exclusion algorithms, thus retrieving known properties but also showing new results about properties often studied by informal reasoning.

Keywords

• mutual exclusion algorithms
• correctness analysis
• automated reasoning
• model checking
• statistical model checking
• Timed Automata