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. 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.

Authors

• Adrian Petcu Boi Faltings

Keywords

No keywords are indexed for this paper.