Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization

Ben Rachmut, Roie Zivan, William Yeoh

TL;DR

Standard distributed optimization algorithms that coordinate pairs of agents (like MGM-2) break down under real-world network latency due to rigid synchronization barriers. The authors propose LAMDLS-2, a latency-aware, asynchronous local search algorithm that uses an ordered coloring scheme to form agent pairs deterministically without round-based handshakes. It guarantees monotonic improvement and converges to a 2-opt solution dramatically faster than MGM-2 across varying network delays.

What Problem Does This Paper Address?

In Distributed Constraint Optimization Problems (DCOPs), autonomous agents (such as smart home devices or sensors) adjust their local variables to minimize a shared global cost. While standard algorithms often assume instantaneous, synchronous communication, real-world networks suffer from unpredictable message delays and congestion—a setting modeled as Communication-Aware DCOPs (CA-DCOPs).

When message delays occur, synchronous algorithms like MGM-2 grind to a halt because agents must wait for round synchronization. Conversely, existing asynchronous algorithms either lack robustness to out-of-order message delivery (e.g., DALO) or are restricted to 1-opt solutions (where individual agents change values unilaterally, as in LAMDLS). Prior to this work, there were no latency-robust distributed local search algorithms that could reach 2-opt solutions (states that cannot be improved by any pair of agents coordinating a joint move).

Methods

The paper introduces LAMDLS-2 (Latency-Aware Monotonic Distributed Local Search-2), structured around two alternating phases:

  1. Ordering Phase:
  2. Agents run an asynchronous graph-coloring procedure called DOCS (Distributed Ordered Color Selection).
  3. Instead of static agent IDs, each agent draws a random identifier (docsId) at each step. This produces a dynamic partial order (color ranking) across neighbors that changes between steps.
  4. Pair Selection Phase:
  5. Instead of using multi-round request–reply handshakes to propose pairs, pairing candidates are determined deterministically from the coloring order: an agent only offers to pair with neighbors whose assigned color index is exactly one greater than its own (coi + 1 = coj), breaking ties via the smallest docsId.
  6. Agents execute bilateral value revisions sequentially down color tiers while unconstrained pairs act concurrently. Step counters (sci) track local progress, ensuring agents only commit when neighboring updates are accounted for.

By randomizing docsId across steps, every neighboring pair is guaranteed to eventually be selected, ensuring the algorithm converges to a true 2-opt state while remaining strictly monotonic (every move decreases global cost).

   [Agent A (Color 1)]  -- deterministic offer -->  [Agent B (Color 2)]
          |                                                 |
  (No round sync)                               (Waits only on lower colors)
          v                                                 v
  Calculates unilateral/bilateral gain & updates step counter sequentially

Datasets

The authors evaluated the algorithms on 100 randomly generated problem instances (each with 50 agents) across three standard benchmark problem topologies:

  • Uniform Random Problems: Constraint densities of 0.2 (sparse) and 0.7 (dense), domain size of 10, constraint costs uniformly sampled from $[1, 100]$.
  • Graph Coloring Problems: Density 0.05, domain size of 3 colors; matching colors between neighbors incurred costs sampled from $\mathcal{U}(10, 100)$, while distinct colors had zero cost.
  • Scale-Free Networks: Generated via the Barabási–Albert model (starting with 10 agents, adding agents connected to 3 existing agents proportionally by degree), domain size 10, costs from $[1, 100]$.

Evaluations simulated three communication environments measured in Non-Concurrent Logic Operations (NCLOs):

  1. Perfect communication (zero delay).
  2. Uniform latency: Delays sampled uniformly from $\mathcal{U}(0, UB)$ with $UB \in \{0; 5,000; 10,000\}$ NCLOs.
  3. Poisson latency: Delays sampled from $\text{Pois}(|MSG|) \cdot m$ where $|MSG|$ is network message traffic and $m \in \{0, 20, 50\}$.

Key Insights and Ideas

  • Eliminating Negotiation Overhead: In MGM-2, forming a pair requires multiple synchronous communication rounds. LAMDLS-2 derives pairings directly from the ordered coloring, bypassing back-and-forth negotiation and shielding the system from latency bottlenecks.
  • Random Identifiers Enable 2-Opt Coverage: A static graph coloring would repeatedly favor the same pairings. Drawing a random docsId before each color selection phase shuffles the color hierarchy, guaranteeing that every edge gets the opportunity to optimize over time.
  • Latency Invariance in Dense Topologies: Because agents only wait on direct predecessors in the color order rather than an entire synchronous iteration barrier, idling is dramatically reduced, allowing unconstrained network regions to compute in parallel.

Key Results

  • Faster Convergence Across Latencies: LAMDLS-2 consistently converged faster than MGM-2. Strikingly, in dense uniform graphs, LAMDLS-2 under maximum delay ($UB = 10,000$) converged faster than MGM-2 under perfect communication ($UB = 0$).
  • Identical 2-Opt Quality: Both algorithms converged to virtually identical solution costs. Paired $t$-tests confirmed no statistically significant difference in final cost for sparse ($p = 0.7514$), dense ($p = 0.8364$), and scale-free networks ($p = 0.4839$). On graph coloring, LAMDLS-2 achieved a statistically significant improvement ($p = 0.005$).
  • Efficiency and Activity: Analysis of execution traces revealed that LAMDLS-2 drastically reduces agent idle time and requires significantly fewer messages to reach convergence.

Limitations and Future Work

  • Pairwise Scope (2-opt): While 2-opt avoids many local minima compared to 1-opt, larger coalitions ($k > 2$) are often required for higher solution quality in complex domains.
  • Theoretical Extension Only: The authors conceptually propose LAMDLS-ROpt—an extension of the ordered coloring scheme to region-optimal ($k$-opt / mediator-based) algorithms—but leave its implementation, empirical evaluation, and comparison against algorithms like RODA to future work.

Summary updated

Abstract

Researchers recently extended Distributed Constraint Optimization Problems (DCOPs) to Communication-Aware DCOPs so that they are applicable in scenarios in which messages can be arbitrarily delayed. Distributed asynchronous local search and inference algorithms designed for CA-DCOPs are less vulnerable to message latency than their counterparts for regular DCOPs. However, unlike local search algorithms for (regular) DCOPs that converge to k-opt solutions (with k > 1), that is, they converge to solutions that cannot be improved by a group of k agents), local search CA-DCOP algorithms are limited to 1-opt solutions only. In this paper, we introduce Latency-Aware Monotonic Distributed Local Search-2 (LAMDLS-2), where agents form pairs and coordinate bilateral assignment replacements. LAMDLS-2 is monotonic, converges to a 2-opt solution, and is also robust to message latency, making it suitable for CA-DCOPs. Our results indicate that LAMDLS-2 converges faster than MGM-2, a benchmark algorithm, to a similar 2-opt solution, in various message latency scenarios.
BibTeX
@inproceedings{rachmut2024latency,
  author = {Ben Rachmut and Roie Zivan and William Yeoh},
  title = {{Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization}},
  booktitle = {CP},
  year = {2024},
  url = {https://openreview.net/forum?id=sAdIL6rP7r},
}
Figure