Partial-order reduction for multi-core LTL model checking

A. Laarman, A.J. Wijs

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

Abstract

Partial-Order Reduction (POR) is a well-known, successful technique for on-the-fly state space reduction in model checking, as evidenced by the prestigious CAV 2014 award for its pioneers. The combination of POR with LTL model checking is long known to cause the so-called ignoring problem, i.e. relevant behavior is continuously ignored and never selected for exploration. This problem has been solved with increasing sophistication over the years, using various ignoring provisos, which include all necessary actions along cycles in the state space. However, parallel model checking algorithms still suffer from a lack of an efficient solution; the best known ones causing severe decrease in reductions. We present a new parallel ignoring proviso for POR, which solves this issue by exploiting parallel DFS-based algorithms. Its similarity to the sequential solutions allows the combination with sophisticated earlier methods solving the ignoring problem. We prove correctness of the new proviso and empirically show that it maintains good reductions, runtime performance and parallel scalability.
Original languageEnglish
Title of host publicationHardware and Software: Verification and Testing
Subtitle of host publication10th International Haifa Verification Conference, HVC 2014, Haifa, Israel, November 18-20, 2014. Proceedings
EditorsE. Yahav
Place of PublicationDordrecht
PublisherSpringer
Pages267-283
ISBN (Print)978-3-319-13338-6
DOIs
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
Volume8855
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Partial-order reduction for multi-core LTL model checking'. Together they form a unique fingerprint.

  • Cite this

    Laarman, A., & Wijs, A. J. (2014). Partial-order reduction for multi-core LTL model checking. In E. Yahav (Ed.), Hardware and Software: Verification and Testing: 10th International Haifa Verification Conference, HVC 2014, Haifa, Israel, November 18-20, 2014. Proceedings (pp. 267-283). (Lecture Notes in Computer Science; Vol. 8855). Springer. https://doi.org/10.1007/978-3-319-13338-6_20