×

zbMATH — the first resource for mathematics

Nagging: A scalable fault-tolerant paradigm for distributed search. (English) Zbl 0999.68048
Summary: 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.

MSC:
68P10 Searching and sorting
68W05 Nonnumerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D. Applegate, R. Bixby, W. Cook, and V. Chvátal, On the solution of traveling salesman problems, Technical Report 98744, Center for Research on Parallel Computation, Rice University, Houston, TX, July 1998 · Zbl 0904.90165
[2] Beguelin, A.; Dongarra, J.; Jiang, W.; Manchek, R.; Sunderam, V., PVM users guide and reference manual, (1994), Oak Ridge National Laboratory Oak Ridge, TN
[3] Brockington, M.; Schaeffer, J., APHID: asynchronous parallel game-tree search, J. parallel distributed comput., 60, 2, 247-273, (2000) · Zbl 0954.68064
[4] Cook, D.; Varnell, R.C., Adaptive parallel iterative deepening search, J. artificial intelligence res., 9, 139-166, (1998) · Zbl 0910.68059
[5] Cook, S., The complexity of theorem-proving procedures, (), 151-158
[6] Davis, M.; Logemann, G.; Loveland, D., A machine program for theorem-proving, Comm. ACM, 5, 7, 394-397, (1962) · Zbl 0217.54002
[7] W. Ertel, Performance analysis of competitive or-parallel theorem proving, Technische Universität München, FKI-162-91, 1992
[8] Feldmann, R.; Mysliwietz, P.; Monien, B., Game tree search on a massively parallel system, (), 203-218
[9] Ferguson, C.; Korf, R.E., Distributed tree search and its application to alpha-beta pruning, (), 128-132
[10] S.L. Forman, Torsion angle selection and emergent non-local secondary structure in protein structure prediction, Ph.D. Thesis, Department of Mathematics, The University of Iowa, Iowa City, IA, August 2001
[11] Foster, I.; Kesselman, C., Globus: A metacomputing infrastructure toolkit, Internat. J. supercomput. appl. high performance comput., 11, 2, 115-128, (1997)
[12] Gomes, C.; Selman, B.; Crato, N.; Kautz, H., Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, J. automat. reasoning, 24, 1-2, 67-100, (2000) · Zbl 0967.68145
[13] Grama, A.; Kumar, V., Parallel search algorithms for discrete optimization problems, ORSA J. comput., 7, 4, 365-385, (1995) · Zbl 0843.90098
[14] Grama, A.; Kumar, V., State of the art in parallel search techniques for discrete optimization problems, IEEE trans. knowledge data engrg., 11, 1, 28-35, (1999)
[15] Gropp, W.; Lusk, E.; Doss, N.; Skjellum, A., A high-performance, portable implementation of the MPI message-passing interface standard, Parallel comput., 22, 6, 789-828, (1996) · Zbl 0875.68206
[16] Gu, J.; Purdom, P.W.; Franco, J.; Wah, B.W., Algorithms for the satisfiability (SAT) problem: A survey, (), 19-151 · Zbl 0945.03040
[17] Joerg, C.; Kuszmaul, B., Massively parallel chess, () · Zbl 0881.68059
[18] Knuth, D.E.; Moore, R.W., An analysis of alpha-beta pruning, Artificial intelligence, 6, 4, 293-326, (1975) · Zbl 0358.68143
[19] Lai, T.H.; Sahni, S., Anomalies in parallel branch-and-bound algorithms, Comm. ACM, 27, 4, 594-602, (1984) · Zbl 0587.68032
[20] Lawler, E.; Wood, D., Branch and bound methods: A survey, Oper. res., 14, 4, 699-719, (1966) · Zbl 0143.42501
[21] Lee, E., Statistical methods for survival data analysis, (1992), Wiley New York
[22] Litzkow, M.; Livny, M.; Mutka, M., Condor: A Hunter of idle workstations, ()
[23] Mahanti, A.; Daniels, C.J., A SIMD approach to parallel heuristic search, Artificial intelligence, 60, 2, 243-282, (1993)
[24] Mann, N.; Schafer, R.; Singpurwalla, N., Methods for statistical analysis of reliability and life data, (1974), Wiley New York · Zbl 0339.62070
[25] Meeker, W.; Escobar, L., Statistical methods for reliability data, (1998), Wiley New York · Zbl 0949.62086
[26] Mitchell, D.; Selman, B.; Levesque, H., Hard and easy distributions of SAT problems, (), 459-465
[27] Newell, A.; Shaw, J.; Simon, H., Chess playing programs and the problem of complexity, IBM J. res. development, 2, 320-335, (1958)
[28] Nilsson, N., Problem-solving methods in artificial intelligence, (1971), McGraw Hill New York
[29] Norvig, P., Paradigms of artificial intelligence programming: case studies in common lisp, (1992), Morgan Kaufmann San Mateo, CA
[30] Paarsch, H.J.; Segre, A.M., Extending the computational horizon: effective distributed resource-bounded computation for intractable problems, ()
[31] Powley, C.; Ferguson, C.; Korf, R.E., Depth-first heuristic search on a SIMD machine, Artificial intelligence, 60, 2, 199-242, (1993)
[32] Reinefeld, A.; Schnecke, V., Work-load balancing in highly parallel depth-first search, (), 773-780
[33] Reinelt, G., The traveling salesman: computational solutions for TSP applications, (1994), Springer Berlin
[34] Segre, A.M.; Elkan, C.P.; Russell, A., A critical look at experimental evaluations of EBL, Machine learning, 6, 2, 183-196, (1991)
[35] Segre, A.M.; Sturgill, D.B., Using hundreds of workstations to solve first-order logic problems, (), 187-192
[36] Selman, B.; Levesque, H.; Mitchell, D., A new method for solving hard satisfiability problems, (), 440-446
[37] Selman, B.; Mitchell, D.; Levesque, H., Generating hard satisfiability problems, Artificial intelligence, 81, 17-29, (1996)
[38] Stephens, M.A., EDF statistics for goodness of fit and some comparisons, J. amer. statist. soc., 69, 720-727, (1974)
[39] Sturgill, D.B.; Segre, A.M., Nagging: A distributed adversarial search-pruning technique applied to first-order logic, J. automat. reasoning, 19, 3, 347-376, (1997) · Zbl 0884.68116
[40] Sturgill, D.B.; Segre, A.M., A novel asynchronous parallelization scheme for first-order logic, (), 484-498
[41] C. Whittinghill, Social choice and resource allocation in a professional sports league, Ph.D. Thesis, Department of Economics, The University of Iowa, Iowa City, IA, 1999
[42] Wilcoxon, F., Individual comparisons by ranking methods, Biometrics, 1, 80-83, (1945)
[43] Zhang, W., State-space search: algorithms, complexity, extensions, and applications, (1999), Springer Berlin · Zbl 0942.90001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.