DiVinE is a tool for LTL model checking and reachability analysis of discrete distributed systems. The tool is able to efficiently exploit the aggregate computing power of multiple network-interconnected multi-cored workstations in order to deal with extremely large verification tasks. As such it allows to analyse systems whose size is far beyond the size of systems that can be handled with regular sequential tools. While the main focus of the tool is on high-performance explicit state model checking, an emphasis is also put on ease of deployment and usage. Additionally, the component architecture and publicly available source code of DiVinE allow for its usage as a platform for research on parallel and distributed-memory model checking techniques.

Partial order reduction and distributed-memory processing are the two essential techniques to fight the well-known state space explosion problem in explicit state model checking. Unfortunately, these two techniques have not been integrated yet to a satisfactory degree. While for verification of safety properties, there are a few rather successful approaches to parallel partial order reduction, for LTL model checking all suggested approaches are either too technically involved to be smoothly incorporated with the existing parallel algorithms, or they are simply weak in the sense that the achieved reduction in the size of the state space is minor. The main source of difficulties is the cycle proviso that requires one fully expanded state on every cycle in the reduced state space graph. This can be easily achieved in the sequential case by employing depth-first search strategy for state space generation. Unfortunately, this strategy is incompatible with parallel (hence distributed-memory) processing, which limits application of partial order reduction technique to the sequential case. In this paper we suggest a new technique that guarantees correct construction of the reduced state space graph w.r.t. the cycle proviso. Our new technique is fully compatible with the parallel graph traversal procedure while at the same time it provides competitive reduction of the state space if compared to the serial case. The new technique has been implemented within the parallel and distributed-memory LTL model checker DiVinE and its performance is reported in this paper.