CSCE 782: Problem Set 1

Figure 1: The basic idea behind the nagging algorithms, taken from Segre's paper.

Nagging Algorithms for Distributed Constraint Optimization

You will implement a nagging strategy to solve the distributed constraint optimization problem using the branch and bound algorithm from Figure 2.12 in our text book.

Nagging

The nagging idea is described in the following paper:

• Alberto Maria Segre, Sean Forman, Giovanni Resta, and Andrew Wildenberg. Nagging: A scalable fault-tolerant paradigm for distributed search. Artificial Intelligence, 140(1--1):71--106, 2002.

  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.

Specifications

The first to note is that the assumptions in nagging are different from those in Chapter 2. Specifically, while the textbook assumes that each variable is an agent, in the nagging algorithm this assumption no longer holds. Instead, your agents all know the complete graph and perform parts of the branch and bound search over arbitrary sets of nodes.

Your first step for this problem set is to implement a centralized branch and bound function which solves the constraint optimization problem. That is, start with one of our existing NetLogo models which already solve the DCOP problem, get rid of the algorithm part and replace it with one function which implements Figure 2.12 from the textbook.

Once you have a centralized function then you can start implementing the nagging strategy by creating a fixed set of worker agents which perform parts of the search. You are free to implement the details of the nagging strategy in the way you think will be best, but there are some specific requirements you should obey:

1. There should be a slider with num-workers which lets the user change the number of worker agents on each run.
2. There should be a plot of the work performed by each worker, as well as a measure of how much of that work resulted in an Abort.

What we are looking for is a nagging algorithm that

1. Does as little wasted (Abort) work as possible.
2. Evenly distributes work among all workers regardless of the number of workers, again, as much as possible.
3. Has linear speedup in the number of workers: with twice as many workers it finds the solution in half the time.

These are really just a wish list. Do the best you can.

Alternate PS1

YOu can also try to implement Asynchronous Backtracking for graph coloring. There is already an implementation of this algorithm in my netlogo mas page but it does not work anymore under 4.0. It also needs to be updated as it does not use the new links primitives (which should make everything much easier). Note that implementing the hyperesolution rule is also not easy, in fact, I would be happy with just a partial implementation. The current implementation only finds some possible nogoods.