« cvs using ssh | Main | Planet lab »
November 18, 2003
"Random Walk Based Heuristic Algorithms for ... Model Checking" by Sivaraj and Gopalakrishnan
[PDMC'2003 - Programme (paper not available)] Improve the performance of parallel random walks at finding errors by mixing in DFS and BFS as a kind of heuristic.
Four heuristics are proposed:
- Heuristic 1: Pure multiple random walks.
- Heuristic 2: RWs + bounded breadth first search from states visited by the random walks.
- Heuristic 3: Initial random walks + bounded breadth first search from the states visited by the initial random walks, followed by random walks from the states visited by bounded breadth first search.
- Heuristic 4: Initial random walks followed by second set of random walks from states visited by initial random walks.
[This figure is from the paper.] The dark discs represent periodic BFS searches of a neighborhood around a given state. The neighborhood search is designed to avoid the possibility of RWing past an error state. This is very similar to the casting behavior we considered. In heuristic 3, the local exploration is done and other nodes join the search at an expansion state. This further distributes the search.
Posted by jones at November 18, 2003 11:13 AM
Comments
Post a comment
Thanks for signing in, . Now you can comment. (sign out)
(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)