We aim at improving the performance of distributed algorithms for model checking and state space reduction. To this end, we introduce a new distribution policy of states over workers. This policy reduces the number of transitions between states located at different workers. This in turn is expected to reduce the communication costs of the distributed algorithms. The main idea is to use Abstract Interpretation techniques to compute a small approximation of the state space, starting from some high level description of the system. Based on this approximation, the connectivity of concrete states is predicted. This information is used to distribute states with expected connectivity to the same worker. Experiments show a considerable reduction of cross transitions, at the expense of a modest unbalance of nodes per worker.
Additional Metadata
Keywords Distributed Model Checking, Abstract Interpretation
Publisher Elsevier
Journal Electronic Notes in Theoretical Computer Science
Conference International Workshop on Parallel and Distributed Methods in Verification
Citation
Orzan, S.-M, van de Pol, J.C, & Espada, M.V. (2005). A state space distribution policy based on abstract interpretation. In Electronic Notes in Theoretical Computer Science (Vol. 128, pp. 35–45). Elsevier.