Cluster-based LTL model checking of large systems

J Barnat, L Brim, I Černá - Formal Methods for Components and Objects …, 2006 - Springer
Formal Methods for Components and Objects: 4th International Symposium, FMCO …, 2006Springer
In recent years a bundle of parallel and distributed algorithms for verification of finite state
systems has appeared. We survey distributed-memory enumerative LTL model checking
algorithms designed for networks of workstations communicating via MPI. In the automata-
based approach to LTL model checking the problem is reduced to the accepting cycle
detection problem in a graph. Distributed algorithms, in opposite to sequential ones, cannot
rely on depth-first search postorder which is essential for efficient detection of accepting …
Abstract
In recent years a bundle of parallel and distributed algorithms for verification of finite state systems has appeared. We survey distributed-memory enumerative LTL model checking algorithms designed for networks of workstations communicating via MPI. In the automata-based approach to LTL model checking the problem is reduced to the accepting cycle detection problem in a graph. Distributed algorithms, in opposite to sequential ones, cannot rely on depth-first search postorder which is essential for efficient detection of accepting cycles. Therefore, diverse conditions that characterise the existence of cycles in a graph have to be employed in order to come up with efficient and practical distributed algorithms. We compare these algorithms both theoretically and experimentally and determine cases where particular algorithms can be successful.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果

Google学术搜索按钮

example.edu/paper.pdf
搜索
获取 PDF 文件
引用
References