Distributed Computing Approaches to Pathfinding Problems

Abstract

The problem of determining the existence of a path between vertices in problem domains with large graphs is outpacing the increases in commonly available processor speeds. This presents a growing need for pathfinding algorithms which can capitalize on parallel approaches. These approaches are often based on parallelizing the search on a single machine. However, some problems may be so large that it becomes appropriate to use distributed computing. This research explores the Distributed Fringe Search algorithm as a more conducive approach for pathfinding problems over multiple distributed machines. The work presented here is novel in its extension of DFS by developing the Distributed Computing Fringe Search. Additionally, this research proposes the Hash Distributed Fringe Search that utilizes space abstraction techniques for work distribution and a more uniform memory requirement. Finally, results are presented to show the impact of the approaches in large searches; these results inform suggestions for future work.