Scalable, Anytime Constraint Optimization through Iterated, Peer-to-Peer Interaction in Sparsely-Connected Networks

This paper reports on an algorithm for any- time, stochastic, distributed constraint optimization that uses iterated, peer-to-peer interaction to try to achieve rapid, approximate solutions to large constraint problems in which the constraint variables are naturally distributed. Two examples are given — graph coloring and coordina- tion of distributed sensors — together with experimental results on performance. I. I NTRODUCTION Dynamic, distributed constraint optimizationproblems arise naturally in high-latency networks of loosely-coupled nodes that must collaborate to accomplish some time- varying set of tasks. The objective is to determine a time-