Ron van der Meyden
University of Technology, Sidney
Computational Issues in Knowledge-Based
Programming of Distributed Systems
- DIMACS Center - Room 433 (small conference room)
- Busch Campus
- Piscataway, New Jersey
- July 19, 11:00 a.m.
Viewing agents in a distributed system as having states of knowledge
provides a highly intuitive level of abstraction, that replaces a
focus on the local states of agents by consideration of the
information that these states encode. The usefulness of this
abstraction for analytic purposes has led to proposals for
_knowledge-based programs_, in which agents' actions have
preconditions that test for their state of knowledge. It has been
argued that knowledge-based programs can provide uniform descriptions
of apparently unrelated protocols operating with respect to different
assumptions concerning the communications substrate, and lead to
protocols that are optimal in their use of information.
These benefits come at a cost, however: knowledge-based programs
cannot be directly executed, but are more like specifications that
must be _implemented_ by translating the tests for knowledge into
concrete computations based on the agents' local states. Since the
agents' knowledge depends on their behaviour, which in turn depends on
their knowledge, this is a nontrivial problem, involving the solution
of a fixpoint equation.
The talk will introduce knowledge-based programs and survey recent
results on computational aspects of their implementation.