A new analysis method for dynamic distributed constraint satisfaction
Roger Mailler, Huimin Zheng · 2014
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 under-standing that many critical real-world problems can be rep-resented 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 inad-equate attention from the research community. A key im-pediment 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 for-malism onto thermodynamic systems. Under this mapping, it shows that DynDCSPs obey the three laws of thermody-namics. 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 pre-dicting the expected performance of distributed protocols under various levels of dynamics.