An Antecedence Graph Approach for Fault Tolerance in a Multi-Agent

In this paper, we propose a strategy to implement fault-tolerance in a multi-agent system. We have based our strategy on the concept of antecedence graphs, used in causal logging and as used by the manetho protocol for distributed systems. Each agent in the multi-agent system keeps an antecedence graph of all the collaborating agents in the system. If one or more agents fail due to any reason, the other agents can reconstruct the same agent state in a partial or comprehensive manner by using their own antecedence graphs. The recovering agents then regenerate their antecedence graphs and message logs and replay the messages to achieve a global consistent state, after which normal operation continues. We believe that introducing fault tolerance in a multi-agent system through antecedence graphs is novel and provides a low overhead and effective solution for fault-tolerance in a multi-agent system.