A state space distribution policy based on abstract interpretation
Electronic Notes in Theoretical Computer Science , Volume 128 - Issue 3 p. 35- 45
Presented at the International Workshop on Parallel and Distributed Methods in Verification
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.
|Keywords||Distributed Model Checking, Abstract Interpretation|
|Journal||Electronic Notes in Theoretical Computer Science|
|Conference||International Workshop on Parallel and Distributed Methods in Verification|
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.