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.

Abstract:

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.