Abstract

This talk describes NICE, the Network Infrastructure for Combinatorial Exploration. NICE was developed primarily to support 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 intrinsically fault tolerant and robust to relatively long message latencies. In this talk, we describe how nagging was used to parallelize three standard combinatorial search algorithms (A* search, $alpha beta$ minimax game tree search, and the Davis-Putnam 3SAT algorithm), and present both theoretical and empirical results showing the advantage of nagging over more traditional partitioning strategies. We then discuss two practical applications of nagging and the NICE framework to biological problems in genetics and proteomics, and describe the ongoing work on the NICE infrastructure.

Alberto Maria Segre received his Ph.D. in Electrical Engineering from the University of Illinois at Urbana-Champaign in 1987, and subsequently served as an Assistant Professor of Computer Science at Cornell University before joining the University of Iowa's Department of Management Sciences in 1994. In 2003, he became Professor and Associate Chair of the University's Computer Science Department and Associate Director of the Center for Statistical Genetics Research. His research interests focus on distributed algorithms for discrete optimization problems, with particular emphasis on problems in the biological sciences.