Design and implementation of distributed state space generation
Hao Yuan, Pla Information · Computer Engineering and Applications Journal · 2009
Parallelization of state space generation is an important technical method to deal with the state space explosion problem.A practical approach based on MapReduce framework is presented.It has the virtues of simpleness and easiness to use,which let the user need not caring about how to parallelize the state space generation algorithm,and that is where it differs from the existing distributed state space generation algorithms.Meanwhile,the manner that the MapReduce framework is used in this approach is also different from the common ones:It has the abilities of dynamically generating input files and repeatedly executing the state space generation process in need,while the common use of MapReduce is to one-off process vast amounts of data in-parallel.This approach has been implemented in a small-scale distributed environment and the experimental results show that:(1)distributed state space generation based on MapReduce does have the ability to analyze a model with large state space,and that(2)this method is quite applicable and scalable for a model with an increasing token number and a fixed place number,whose state space scales up mainly with the token number.