Nagging: A scalable, fault-tolerant, paradigm for distributed search

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.