A knowledge-theoretic account of negotiated commitment
Murray S. Mazer, G. Burns · 1989
Negotiation is a useful form of coordination in organizational systems, for establishing commitments to joint courses of action. Negotiated commitment is the process of ensuring that each agent commits consistently to the outcome of a negotiation; this process is the basis upon which a negotiating system is built. We give a formal characterization and analysis of negotiated commitment using knowledge theory, which is based on a modal logic of knowledge. Reasoning formally about knowledge is a relatively new approach to understanding distributed systems. From this perspective, a group of processes acquires and disseminates knowledge about the system, through various events, as the system computation evolves. Knowledge theory allows us to distinguish between what, the knowledge required to solve a problem, and how, the communication and processing required to achieve that knowledge in a distributed protocol. Using an event-based model of distributed computation, we articulate some important properties of knowledge evolution in systems with various failure, termination, synchrony, and communication characteristics. We give a general result on message passing requirements for knowledge transfer in systems with certain common characteristics. Our analysis of negotiated commitment yields such things as the levels of knowledge each agent requires to achieve certain behaviours, the restrictions required on distributed computations to facilitate the identified states of knowledge, and the impossibility of achieving commitment under various assumptions of system characteristics (based on the impossibility of the required knowledge transfer). We discuss the notion of protocols in which each process bases its actions on its knowledge. We also show how one protocol may be said to implement another, including how a protocol without explicit tests for knowledge may implement a knowledge-based protocol. The thesis of this dissertation is twofold: first, the problem of ensuring that each agent commits consistently to the outcome of a negotiation is fundamental to building negotiating systems; and, second, knowledge theory is a useful tool in specifying and analyzing distributed problems (such as negotiated commitment) and in providing protocols to solve the problems. This work advances the current understanding of both negotiated commitment and the use of knowledge theory to analyze problems in distributed computing.