The Constraint-Based Knowledge Broker Model: Semantics, Implementation and Analysis

Imagine distributed knowledge processing with autonomous activities and decentralized control where the handling of partial knowledge does not result in unclear semantics or failure-prone behavior. In this paper, a modular approach is taken where concurrent agents, calledconstraint-based knowledge brokers(CBKBs), process and generate new knowledge in the presence of partial information. CBKBs apply constraint solving techniques to the domain of information gathering in distributed environments. Constraints are exploited to allow partial specification of the requested information, and to relate information requests from multiple sources. We present a mathematical model where the semantics of the knowledge system is described using a standard fixed-point procedure. A basic execution model is then provided. This is incrementally refined to tackle problems of inter-argument dependencies (that arise with constraints relating information requests from different sources), of knowledge reuse inside the knowledge generators, and of recursion control. The model refinements are illustrated by a detailed complexity analysis in terms of the number of agents needed and of the number of messages sent, distinguished by requests and answers of the involved broker agents. A detailed example shows a broker-based chart-parser for unification grammars with feature terms implemented using CBKBs. As we shall point out, this apparently abstract example can be easily generalized to full-fledged information gathering.