A New Analysis Method for Dynamic Distributed Constraint Satisfaction

There has been an increasing recognition that a number of key computational problems require distributed solution techniques. To facilitate the creation and advancement of these techniques, researchers have developed the distributed constraint satisfaction (DCSP) formalism with the understanding that many critical real-world problems can be represented using it. Consequently, this formalism has led to the creation of myriad protocols for solving problems in this class. However, this formalism ignores a critical feature of many environments: problems change over time. The dynamic, DCSP (DynDCSP) formalism was invented to address this deficiency, but this model has received inadequate attention from the research community. A key impediment to advancing this research area is the lack of a compelling theoretical underpinning to the analysis of these problems and the evaluation of the protocols used to solve them. This work creates a mapping of the DynDCSP formalism onto thermodynamic systems. Under this mapping, it shows that DynDCSPs obey the three laws of thermodynamics. Utilizing these laws, this work develops, for the first time, a method for characterizing the impact that dynamics has on a distributed problem as well as a technique for predicting the expected performance of distributed protocols under various levels of dynamics.