Superstabilizing, Fault-Containing Distributed Combinatorial Optimization
Superstabilizing, Fault-Containing Distributed Combinatorial Optimization
复制标题
超稳定、包含故障的分布式组合优化
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
B. Faltings
中科院分区：
文献类型：
--
作者：
Adrian Petcu;B. Faltings
分布式系统中的自稳定是系统通过最终达到法律的状态并在之后保持该状态来响应瞬时故障的能力。这使得这样的系统特别有趣，因为它们可以容忍故障，并且能够科普动态环境。
我们提出了多智能体组合优化的第一个自稳定机制，它工作在一般网络上，并稳定在一个状态对应的最优解的优化问题。我们的算法是基于动态规划，并需要一个线性数量的消息，以找到最佳的解决方案，在没有故障。
我们展示了我们的算法是如何超稳定的，在这个意义上，而从一个稳定状态过渡到下一个，我们的系统保留分配从以前的最佳状态，直到新的最优solutions.We提供相等的界限的稳定和超稳定时间。
此外，我们描述了一个通用的计划，故障遏制和快速响应时间低影响故障。多个孤立的故障得到有效处理。
为了显示我们的方法的优点，我们报告的实验与实际规模的分布式会议调度问题的多智能体系统。
Self stabilization in distributed systems is the ability of a system to respond to transient failures by eventually reaching a legal state, and maintaining it afterwards. This makes such systems particularly interesting because they can tolerate faults, and are able to cope with dynamic environments.
We propose the first self stabilizing mechanism for multiagent combinatorial optimization, which works on general networks and stabilizes in a state corresponding to the optimal solution of the optimization problem. Our algorithm is based on dynamic programming, and requires a linear number of messages to find the optimal solution in the absence of faults.
We show how our algorithm can be made super-stabilizing, in the sense that while transiting from one stable state to the next, our system preserves the assignments from the previous optimal state, until the new optimal solution is found. We offer equal bounds for the stabilization and the superstabilization time.
Furthermore, we describe a general scheme for fault containment and fast response time upon low impact failures. Multiple, isolated failures are handled effectively.
To show the merits of our approach we report on experiments with practically sized distributed meeting scheduling problems in a multiagent system.