Modelling knowledge and action in distributed systems (Q1262142): Difference between revisions

The authors give a formal model of the interaction between knowledge and action in distributed systems. They define the concept of knowledge-based protocols, providing a natural way of describing how actions should take place in a distributed system. The very promising way of thinking about distributed systems, was introduced in preliminary forms by the authors [A formal model of knowledge, action, and communication in distributed systems: preliminary report (Proc. 4th ACM Symp. on Principles of Distributed Computing, 224-236 (1985)] and [Lect. Notes Comput. Sci. 335, 18-32 (1988; Zbl 0663.68038)]. In the proposed model, a distributed system is identified with a set of runs, where a run is a function from time to global states. A global state is a tuple consisting of an environment state and a local state for each process in the system. The actions are associated with functions from global states to global states, while the protocol is defined as a function from local states to actions. The authors extend the standard concept of protocols by defining knowledge-based protocols, ones in which a process' action may depend explicitly on its knowledge. The paper is profound and very well-structured scientific work. After the short introduction given in Section 1, the authors define the concepts of runs, actions and systems in Sections 2. They also give some well-chosen examples to show how the proposed formalism can be used to capture a number of situations that arise in distributed and parallel computing. How to ascribe knowledge to processes in a distributed system is shown in Section 3. In Section 4, the notion of protocol is discussed, while Section 5 is dedicated to the knowledge-based protocols. In Section 6, the authors consider the cheating husbands problem, informally discussed in \textit{Y. Moses}, \textit{D. Dolev} and \textit{J. Y. Halpern} [Distrib. Comput. 1, 167-176 (1986; Zbl 0609.68072)], and show how it can be caputed in the proposed framework. Section 7 is dedicated to demonstrate that the notion of one protocol implementing another may be easily included in the new model. As a conclusion, in Section 8, some directions for further research are suggested. The paper is an exceptional scientific work, and it will certainly be of reference for the future research in distributed systems.