Impact of Problem Centralization in Distributed Constraint Optimization Algorithms
John Davin and Pragnesh Jay Modi


Abstract

Recent progress in Distributed Constraint Optimization Problems (DCOP) has led to a range of algorithms now available which differ in their amount of problem centralization. Problem centralization can have a significant impact on the amount of computation required by an agent but unfortunately the dominant evaluation metric of  number of cycles  fails to account for this cost. We analyze the relative performance of two recent algorithms for DCOP: OptAPO, which performs partial centralization, and Adopt, which maintains distribution of the DCOP. Previous comparison of Adopt and OptAPO has found that OptAPO requires fewer cycles than Adopt. We extend the cycles metric to define  Cycle-Based Runtime (CBR)  to account for both the amount of computation required in each cycle and the communication latency between cycles. Using the CBR metric, we show that Adopt outperforms OptAPO under a range of communication latencies. We also ask: What level of centralization is most suitable for a given communication latency? We use CBR to create performance curves for three algorithms that vary in degree of centralization, namely Adopt, OptAPO, and centralized Branch and Bound search.