Communication Resource Sharing in Diffusing Inference

Yasuhiko Kitamura, Ken-ichi Teranishi, Shoji Tatsumi, and Takaaki Okumoto

International Symposium on Fifth Generation Computer Systems 1994, Workshop on Heterogeneous Cooperative Knowledge-Bases, 167-179, 1994.


The diffusing inference is a generic cooperative inference method in which multiple agents cooperatively find a solution. We can apply this method to heterogeneous distributed knowledge-base systems since we can view such a system as a multi-agent system. In the diffusing inference, its communication has a nondeterministic feature by which we mean all communication demands need not always to be satisfied to find a solution. In the nondeterministic communication, sending more request messages concurrently leads to inference speedup since it makes more agents involved in an inference. On the other hand, it leads to communication overhead also. Hence, we should develop a communication control method to send messages balancing the inference speedup and the communication overhead. We propose, in this paper, local and global communication control methods. In the local method, each agent individually controls the number of request messages based on its locally available information. In the global method, multiple agents cooperate to control the total number of request messages in a whole system by using tokens which permit sending messages. We experimentally evaluated both methods through simulations on distributed maze problems. Obtained results are as follows. The local method becomes ineffective once the inference spreads out among many agents because the total amount of communication becomes quite large even if each agent limits its communication. In such a case, the global method is superior to the local one and still effective even when the communication cost is high.

(161K bytes)

Last Updated: 97/2/13