Superstabilizing, Fault-containing Multiagent Combinatorial Optimization
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. In this paper we propose the first self stabilizing mechanism for multiagent combinatorial optimization, which 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 (similar to a "last-known-good" state), until the new optimal solution is found (without "random" changes to the variables). 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 practical sized distributed meeting scheduling problems in a multiagent system.
Record created on 2005-07-13, modified on 2016-08-08