Vidal's library
Title: Nagging: A scalable fault-tolerant paradigm for distributed search
Author: Alberto Maria Segre, Sean Forman, Giovanni Resta, and Andrew Wildenberg
Journal: Artificial Intelligence
Volume: 140
Number: 1--1
Pages: 71--106
Year: 2002
DOI: 10.1016/S0004-3702(02)00228-X
Abstract: 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, alphabeta minimax game tree search, and the Davis-Putnam algorithm.

Cited by 7  -  Google Scholar

@Article{segre02a,
  author =	 {Alberto Maria Segre and Sean Forman and Giovanni
                  Resta and Andrew Wildenberg},
  title =	 {Nagging: A scalable fault-tolerant paradigm for
                  distributed search},
  journal =	 {Artificial Intelligence},
  year =	 2002,
  volume =	 140,
  number =	 {1--1},
  pages =	 {71--106},
  abstract =	 {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, alphabeta minimax game tree search,
                  and the Davis-Putnam algorithm.},
  url = 	 {http://jmvidal.cse.sc.edu/library/segre02a.pdf},
  cluster = 	 {12440606795010574236},
  doi = 	 {10.1016/S0004-3702(02)00228-X}
}
Last modified: Wed Mar 9 10:15:40 EST 2011