提出新算法，让分布式任务分配更快找到更优解且抗延迟。
Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization
- 通过成对代理协同调整分配，实现2-最优解搜索
- 在多种延迟场景下收敛速度优于基准算法MGM-2
- 兼顾效率与抗延迟能力，适合高延迟分布式系统
研究人员将分布式约束优化问题（DCOP）扩展为通信感知型DCOP（CA-DCOP），以应对消息任意延迟的场景。针对常规DCOP的局部搜索算法可收敛至k-最优解（即无法由k个代理联合改进），而现有CA-DCOP的局部搜索算法仅能保证1-最优解。本文提出延迟感知单调分布式局部搜索-2（LAMDLS-2），代理成对协作进行双向分配替换，具有单调性，能收敛至2-最优解，同时对消息延迟鲁棒，适用于CA-DCOP。实验表明，在不同消息延迟场景下，LAMDLS-2比基准算法MGM-2更快收敛至相似的2-最优解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。