Analyzing the Effect of Information Stagnancy on the Distributed Stochastic Algorithm

Despite the fact that many real world problems change over time, many Distributed Constraint Optimization Problem (DCOP) algorithms assume that the problem is constant or changing at a negligible rate. In addition, these algorithms also assume that changes to the environment are instantaneously observable. However, in highly dynamic environments with communication delays, both of these assumptions can be violated resulting in problem solving with out-of-date information. In this study, we explore the relationship between environmental dynamics, information stagnancy, and solution quality in Dynamic DCOP problems. By using recent advances in the analysis of dynamic, distributed problems, we show that information stagnancy can be characterized and used to accurately predict the behavior of a protocol. To evaluate our finding, we use the Distributed Stochastic Algorithm (DSA) as a basis. Through extensive empirical testing, we show that the prediction function is accurate.