Dynamic, distributed constraint solving and thermodynamic theory

摘要

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 and optimization (DCSP/DCOP) formalisms with the understanding that many critical real-world problems can be represented using them. Subsequently, these formalisms have led to the creation of numerous protocols where most ignore a critical feature of the problems they are designed to solve: the problems change over time. Dynamic variations of the DCSP and DCOP formalisms were invented to address this deficiency, but these models have 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 and DynDCOP formalisms onto thermodynamic systems. Under this mapping, it shows that these problems 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.