Information Technology Reference
In-Depth Information
Distributed Consequence Finding:
Partition-Based and Cooperative Approaches
Katsumi Inoue
1
, Gauvain Bourgne
1
, and Takayuki Okamoto
2
1
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
2
Graduate School of Science and Technology, Kobe University
1-1 Rokkodai-cho, Nada-ku, Kobe 658-8501, Japan
{
ki,bourgne
}
@nii.ac.jp
Abstract.
When knowledge is physically distributed, information and knowl-
edge of individual agents may not be collected to one agent because they should
not be known to others for security and privacy reasons. We thus assume the sit-
uation that individual agents cooperate with each other to find useful information
from a distributed system to which they belong, without supposing any master or
mediate agent who collects all necessary information from the agents. Then we
propose two complete algorithms for distributed consequence finding. The first
one extends a technique of theorem proving in partition-based knowledge bases.
The second one is a more cooperative method than the first one. We compare
these two methods and other related approaches in the literature.
1
Introduction
There is a growing interest in building large knowledge bases. Dealing with a huge
amount of knowledge, two problems can be encountered in real domains. The first case
is that knowledge is originally centralized so that one can access the whole knowledge
but the size of the knowledge base is too huge to be handled. The second case is that
knowledge is
distributed
in several sources so that it is hard or impossible to immedi-
ately access the whole or part of knowledge. The former case is studied in the line of
research on
parallel
or
partition-based
reasoning. For example, partition-based theorem
proving by Amir and McIlraith [3] divide a knowledge base into several parts each of
which is easier to be handled so that the scalability of a reasoning system is improved.
On the other hand, in the second case we suppose
multi-agent systems
or
peer-to-
peer systems
[2], in which an agent does not want to expose all its information to other
agents for security and privacy reasons. Sometimes, it is inherently impossible to tell
what other agents want to know and to ask what can be obtained from others. In such a
case, each agent must give up gathering all necessary information from other agents, and
moreover, no master or mediate agent can be assumed to exist to collect all information
from agents. That is, we need to solve the problem with knowledge distributed as it is.
In this research, we mainly deal with such distributed knowledge bases, but hope that
those algorithms considered for distributed reasoning can be applied to the first case to
gain efficiency.
