KNOWLEDGE-BASED PROGRAMS

Reasoning about activities in a distributed computer system at the lev el of the knowledge of individuals and groups allows us to abstract aw ay from many concrete details of the system we are considering. In thi s paper, we make use of two notions introduced in our recent book to f acilitate designing and reasoning about systems in terms of knowledge. The first notion is that of a knowledge-based program. A knowledge-ba sed program is a syntactic object: a program with tests for knowledge. The second notion is that of a context, which captures the setting in which a program is to be executed. In a given context, a standard pro gram (one without tests for knowledge) is represented by (i.e., corres ponds in a precise sense to) a unique system. A knowledge-based progra m, on the other hand, map be represented by no system, one system, or many systems. In this paper, we provide a sufficient condition for a k nowledge-based program to be represented in a unique way in a given co ntext. This condition applies to many cases of interest, and covers ma ny of the knowledge-based programs considered in the literature. We al so completely characterize the complexity of determining whether a giv en knowledge-based program has a unique representation, or any represe ntation at all, in a given finite-state context.