Wide-area transposition-driven scheduling

The distributed searching of state spaces containing cycles is a challenging task and has been studied for several years. Traditional parallel search algorithms either ignore the cyclic nature of the state space and waste much time in duplicated search effort, or they rely on heavy communication to reduce duplicate work, resulting in a large communication overhead. Both methods perform poorly, even when using a fast, local interconnection. A recently-developed task distribution scheme, called transposition-driven scheduling (TDS), performs much better, since it communicates asynchronously and efficiently suppresses duplicate search effort. TDS, however, requires bandwidths of megabytes per second per processor. In this paper, we investigate how cyclic state spaces can be searched efficiently on a meta-computing system containing multiple clusters, connected by high-latency, low-bandwidth wide-area links. This is quite a challenge, because the wide-area links provide neither the bandwidth required for TDS nor the latency required for traditional distributed search algorithms. We propose a scheme that strongly reduces communication between clusters at the expense of some duplicate search effort. Performance measurements for several applications show that the new scheme outperforms traditional schemes by a wide margin