Information Technology Reference
In-Depth Information
Fig. 4.
First Message Passing in Cooperative Consequence Finding
Theorem 3 (Soundness and Completeness of Cooperative Consequence Finding)
.
Suppose an axiom set and its partitions
=
i≤n
A
i
. We assume that every agent
A
i
has a sound and complete algorithm for consequence finding. Then, Algorithm 4 is
sound and complete for distributed consequence finding of
Newcarc
(
A
A
,I,
P
A
)
.
Proof.
Soundness is proved in the same way as Theorem 2. For completeness,
Newcar
c
(
A
P
)
can be decomposed into multiple clause-by-clause
Newcarc
operations
by (1). Since we use the production field
A
,I,
P
A
in which all literals appearing in
A
can be
skipped, all Skip operations in any SOL deduction from the whole
are also applied
by Algorithm 4. On the other hand, all Resolve operations of SOL deductions can be
simulated by sending resolving clauses to other agents. Ancestor resolution in SOL
deductions can also be done by sending back to previous agents. As a result, any SOL
deduction can be simulated in a distributed setting by Algorithm 4.
A
5
Comparing Two Approaches
We here compare the two proposed methods for distributed consequence finding. We
first note that the two methods are not designed to compute the same consequences
as long as Theorems 2 and 3 are concerned. Given an axiom set
A
, partition-based
consequence finding computes
Carc
(
A
,
P
)
belonging to a given production field
P
in Theorem 2, while cooperative consequence finding computes
Newcarc
(
P
A
)
for a given set of inputs
I
in Theorem 3. We could extend both methods to deal with
any case by considering the same conditions for them. However, the current conditions
are natural in both methods. The partition-based approach is based on Interpolation
Theorem [6], which refers to the set of consequences of an axiom set of one partition,
yet a language restriction can be used effectively. On the other hand, the cooperative
approach is more dynamic and reflective so that ramification from the new input is
propagated to other agents, but the language restriction is not easily set since every
agent could be related to any other. Nevertheless, an obvious merit of the cooperative
method is that we do not need to break cycles and assume no agent who does this.
We compare these two methods with the centralized approach with an accessibil-
ity problem in a metabolic networks (the citric acid cycle), depicted in Fig. 5. Given a
A
,I,
