A State Space Distribution Policy based on Abstract Interpretation

Simona Orzan Jaco van de Pol Miguel Valero Espada


Abstract

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. Based on this approximation, the connectivity of concrete states is predicted. This information is used to distributed 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.