Multi-Directional Distributed Search with Aggregation

Competition and cooperation can boost the out-of-the-box performance of search. Both can be implemented with a portfolio of algorithms which run in parallel, give hints to each other and compete for being the first to finish and deliver the solution. In this paper we present a new generic framework for the application of algorithms for distributed constraint satisfaction which makes use of both cooperation and competition. This framework improves the performance of two different standard algorithms by one to two order of magnitude and can reduce the risk of poor performance by up to three orders of magnitude. We expect our new methods to be similarly beneficial for any distributed search algorithm and describe ways on how to incorporate them.