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.