Techniques for Distributed Reachability Analysis with Partial Order and Symmetry based Reductions

2009/01/01 by Janardan Misra, Misra, Janardan, Suman Roy +1
Computer Science · #Distributed #FOS: Computer and information sciences #Formal Methods in Verification #Parallel #Software Engineering (cs.SE) #Software Reliability and Analysis Research #Software Testing and Debugging Techniques #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.0901.0179

openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work we propose techniques for efficient reachability analysis of the state space (e.g., detection of bad states) using a combination of partial order and symmetry based reductions in a distributed setting. The proposed techniques are focused towards explicit state space enumeration based model-checkers like SPIN. We consider variants for both depth-first as well as breadth-first based generation of the reduced state graphs on-the-fly.

Citations

• Algebraic laws for nondeterminism and concurrency

Related

• Local State Space Analysis to Assist Partial Order Reduction
• Alleviating State-space Explosion in Component-based Systems with\n Distributed, Parallel Reachability Analysis Algorithm
• Revisiting Stateful Partial-Order Reduction
• Approximate Partial Order Reduction
• Symbolic Reachability Analysis of B through ProB and LTSmin