Rocky Mountain College * Department of Computer Science * 406 208 3193 * turn on javascript to see my email

Nagging: A Scalable Fault Tolerant Paradigm for Distributed Search

A. Segre, S. Forman, G. Resta and A. Wildenberg, Artificial Intelligence 140:1-2, September 2002, pp. 71-106.



This paper describes nagging, a technique for parallelizing search in a heterogeneous distributed computing environment. Nagging exploits the speedup anomaly often observed when parallelizing problems by playing multiple reformulations of the problem or portions of the problem against each other. Nagging is both fault tolerant and robust to long message latencies. In this paper, we show how nagging can be used to parallelize several different algorithms drawn from the artificial intelligence literature, and describe how nagging can be combined with partitioning, the more traditional search parallelization strategy. We present a theoretical analysis of the advantage of nagging with respect to partitioning, and give empirical results obtained on a cluster of 64 processors that demonstrate nagging's effectiveness and scalability as applied to A* search, Alpha Beta minimax game tree search, and the Davis-Putnam algorithm.
You know we're constantly taking. We don't make most of the food we eat, we don't grow it, anyway. We wear clothes other people make, we speak a language other people developed, we use a mathematics other people evolved and spent their lives building. I mean we're constantly taking things. It's a wonderful ecstatic feeling to create something and put it into the pool of human experience and knowledge. -- Steve Jobs, Rolling Stone, November 1983.