Journal article
Nagging: A scalable fault-tolerant paradigm for distributed search
Artificial intelligence, Vol.140(1), pp.71-106
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,
αβ minimax game tree search, and the Davis–Putnam algorithm.
Details
- Title: Subtitle
- Nagging: A scalable fault-tolerant paradigm for distributed search
- Creators
- Alberto Maria Segre - University of IowaSean Forman - Saint Joseph's UniversityGiovanni Resta - Informatica (South Korea)Andrew Wildenberg - Stony Brook University
- Resource Type
- Journal article
- Publication Details
- Artificial intelligence, Vol.140(1), pp.71-106
- DOI
- 10.1016/S0004-3702(02)00228-X
- ISSN
- 0004-3702
- eISSN
- 1872-7921
- Publisher
- Elsevier B.V
- Language
- English
- Date published
- 2002
- Academic Unit
- Nursing; Fraternal Order of Eagles Diabetes Research Center; Computer Science
- Record Identifier
- 9984259493002771
Metrics
6 Record Views