Speculative Computation by Abduction under Incomplete Communication Environments

Ken Satoh, Katsumi Inoue, Koji Iwanuma, and Chiaki Sakama

Proceedings of the 4th International Conference on Multi-Agent Systems (ICMAS'00), IEEE Computer Society, pages 263-270, 2000.


In this paper, we present a method of problem solving in multi-agent systems when communication between agents is not guaranteed. Under incomplete communication environments such as the Internet, the communication might fail and a reply might be significantly delayed. Therefore, research of problem solving under incomplete communication is very important. To solve the problem, we propose a method using abduction. Abduction is a way of reasoning where some hypothesis will be used to complement unknown information. The idea is as follows. When communication is delayed or failed, then we use a default hypothesis as a tentative answer and continue computation. When some response is obtained, we check consistency of the response and the current computation. If the response is consistent, then we continue the current computation; else if the response is inconsistent, we seek an alternative computation. This way of computation is called speculative computation, since computation using a tentative answer would lead to a significant advantage if it succeeds. In this paper, we restrict our attention to a master-slave multi-agent system and propose an implementation of speculative computation and show that abduction plays an important role in speculative computation.

Full Paper (gzipped postscript 51K)