Dynamic Theoretical Analysis of the Distributed Stochastic and Distributed Breakout Algorithms

The distributed constraint satisfaction problem is often used to model real-world situations and find agent-based solutions. A number of methods have been developed to solve these problems, including the well-known DSA and DBA algorithms. In many real scenarios, however, the problems are not static. This forces practitioners to adapt these protocols to solve dynamic distributed constraint satisfaction problems (DynDCSP). Surprisingly, despite long-running study of the problem, practically all analysis of Dyn-DCSP algorithms has been experimental in nature. This work presents a new theoretical assessment of the DSA and DBA algorithms, leveraging a mapping of DynDCSP instances to a physical thermodynamics model to develop a deeper understanding of the algorithms' behavior. Here, we assess the static versions of DSA and DBA, but focus on examining their rates of convergence, not just their final convergence points, as a means of understanding how they will perform in dynamic settings. We develop various theoretical approaches to show how the algorithms' convergence rates are affected by problem density and tightness, and examine the impact that problem size has on an algorithm's performance. Finally, we show the accuracy of our analytical predictions through comparison with experimental results.