A formal model of knowledge, action, and communication in distributed systems: Preliminary report

Abstract

We present a formal model that captures the subtle interaction between knowledge, action, and communication in distributed systems. We extend the standard notion of protocol by defining knowledge-based protocols, ones in which a processor's action may explicitly depend on its knowledge. We also consider what it means for a processor to follow an honest protocol, one where, intuitively, it only sends messages that it knows to be true. Defining these notions turns out to be surprisingly delicate.