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.
Abstract
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
kitamura@info.eng.osaka-cu.ac.jp