Communication-Aware Local Search for Distributed Constraint Optimization

Ben Rachmut, Roie Zivan, William Yeoh

Introduction

Distributed Constraint Optimization Problems (DCOPs) provide a robust framework for coordinating multi-agent systems, such as smart home devices, IoT sensor networks, and autonomous vehicle fleets. The primary goal is to minimize a global cost function through local interactions. However, traditional DCOP research has long relied on a significant simplification: the assumption of "perfect communication." In these models, messages between agents are assumed to arrive instantaneously and without fail.

In real-world deployments, distributed systems are plagued by network congestion, latency, and packet loss. Standard local search algorithms, such as the Distributed Stochastic Algorithm (DSA) and the Maximum Gain Messaging (MGM) algorithm, are typically synchronous by design. They require agents to wait for updates from all neighbors before proceeding, making them vulnerable to deadlocks or significant performance degradation when communication is imperfect. This paper addresses this gap by introducing a communication-aware model and a latency-robust algorithm designed for asynchronous environments.

The CA-DCOP Model

To bridge the gap between theory and practice, the authors propose the Communication-Aware DCOP (CA-DCOP) model. This framework extends standard DCOPs by incorporating a Constrained Communication Graph (CCG). Unlike standard models that treat communication links as ideal pipes, the CCG assigns a latency function and a loss probability to every link. This allows for the simulation of realistic network disturbances, where the time it takes for information to travel is variable and delivery is not guaranteed.

Algorithmic Innovations: LAMDLS and AAM

The paper introduces two primary technical contributions to handle the complexities of the CA-DCOP model:

LAMDLS is designed to preserve the "monotonicity" property—the guarantee that the global cost never increases—without requiring strict synchronization. In asynchronous systems, "thrashing" often occurs when neighboring agents update their values simultaneously based on outdated information. LAMDLS mitigates this using a Distributed Ordered Color Selection (DOCS) phase. By ensuring that neighbors do not move at the same time, the algorithm maintains stability even when messages are delayed.

2. AAM (Asynchronous Anytime Mechanism)

Standard "anytime" frameworks, which track and report the best solution found during a run, typically rely on global iteration counters. These counters do not exist in truly asynchronous settings. The Asynchronous Anytime Mechanism (AAM) solves this by using a spanning tree and local context storage. Agents aggregate and report the best global solution found across various states, allowing the system to provide a high-quality result even if the algorithm is interrupted.

Experimental Setup

The researchers evaluated their approach across four distinct problem topologies:

  • Uniform Random Problems: Standard benchmarks with varying constraint densities.
  • Graph Coloring Problems: Classic tasks used to test constraint satisfaction.
  • Scale-free Networks: Modeled using the Barabasi-Albert method to simulate "hub-and-spoke" structures common in real-world internet and social networks.
  • Overlapped Solar Systems: A realistic benchmark where agents are geographically clustered. In this model, latency and loss are calculated as functions of the Euclidean distance between agents, mimicking the signal degradation found in wireless networks.

Key Insights: The Exploration Paradox

The most significant finding of the study is what might be termed the "Exploration Paradox." While latency is generally viewed as a hindrance, the authors discovered that imperfect communication can actually improve solution quality.

When an agent acts on obsolete information due to message latency, it may perform a move that it believes is exploitative (greedy) but is actually explorative relative to the current global state. This "accidental exploration" allows the system to escape local optima that would trap a perfectly synchronized, greedy search. Consequently, asynchronous versions of DSA and MGM often reached lower cost floors than their synchronous counterparts.

Furthermore, asynchrony provides a natural speedup. Agents in an asynchronous system do not waste time waiting for the "slowest" message in a cycle, leading to faster convergence in terms of Non-Concurrent Logic Operations (NCLOs).

Results and Performance

Experimental results confirmed that LAMDLS is significantly more robust than synchronous MGM. On structured problems like Scale-Free and Solar Systems, LAMDLS converged to superior solutions more rapidly. Additionally, the AAM framework proved effective; by storing a limited number of local contexts (approximately 100), the mechanism could identify the best-found solution without significant computational overhead or a global clock.

Limitations and Future Work

Despite the success in handling latency, message loss remains a critical challenge. The authors note that LAMDLS can still encounter deadlocks if a vital message is lost and not resent. While sending redundant copies of messages can mitigate this, it increases network overhead.

Future research will focus on developing more sophisticated "handshaking" protocols (akin to TCP/IP) to handle loss more efficiently and exploring the impact of bandwidth limitations on these distributed algorithms. Expanding these communication-aware techniques to other multi-agent tasks, such as distributed task allocation, remains a promising avenue for further study.

Summary updated

Abstract

Most studies investigating models and algorithms for distributed constraint optimization problems (DCOPs) assume that messages arrive instantaneously and are never lost. Specifically, distributed local search DCOP algorithms, have been designed as synchronous algorithms (i.e., they perform in synchronous iterations in which each agent exchanges messages with all its neighbors), despite running in asynchronous environments. This is true also for an anytime mechanism that reports the best solution explored during the run of synchronous distributed local search algorithms. Thus, when the assumption of perfect communication is relaxed, the properties that were established for the state-of-the-art local search algorithms and the anytime mechanism may not necessarily apply. In this work, we address this limitation by: (1) Proposing a Communication-Aware DCOP model (CA-DCOP) that can represent scenarios with different communication disturbances; (2) Investigating the performance of existing local search DCOP algorithms, specifically Distributed Stochastic Algorithm (DSA) and Maximum Gain Messages (MGM), in the presence of message latency and message loss; (3) Proposing a latency-aware monotonic distributed local search DCOP algorithm; and (4) Proposing an asynchronous anytime framework for reporting the best solution explored by non-monotonic asynchronous local search DCOP algorithms. Our empirical results demonstrate that imperfect communication has a positive effect on distributed local search algorithms due to increased exploration. Furthermore, the asynchronous anytime framework we proposed allows one to benefit from algorithms with inherent explorative heuristics.
BibTeX
@article{rachmut2022communication,
  author = {Ben Rachmut and Roie Zivan and William Yeoh},
  title = {{Communication-Aware Local Search for Distributed Constraint Optimization}},
  journal = {J. Artif. Intell. Res.},
  year = {2022},
  doi = {10.1613/jair.1.13826},
}

Loading related content...

Figure