Programming Simultaneous Actions Using Common Knowledge: Preliminary Version

This work applies the theory of knowledge in distributed systems to the design of faulttolerant protocols for problems involving coordinated simultaneous actions in synchronous systems. We give a simple method for transforming specifications of such problems into high-level protocols programmed using explicit tests of whether certain facts are common knowledge. The resulting protocols are optimal in all runs: for every possible input to system and pattern of processor failures, they are guaranteed to perform the simultaneous actions as soon as any other protocol can possibly perform them. A careful analysis of when facts become common knowledge shows how to efficiently implement these protocols in many variants of the omissions failure model. In the generalized omissions model, however, it is shown that any protocol that is optimal in this sense must require co-NP hard computations. The analysis in this paper exposes subtle differences between the failure models, including the precise point at which this gap in complexity occurs.

Authors

• Yoram Moses
• Mark R. Tuttle

Keywords

• Protocols
• Contracts
• Failure analysis
• Laboratories
• Computer science
• Testing
• Distributed databases
• Fault tolerant systems
• Timing
• Mathematics
• Social Cognition
• Simultaneous Activation
• Distribution System
• Cognitive Theory
• Protocol Design
• Failure Model
• Failure Pattern
• Synchronization Of Systems
• Standard Protocol
• Computational Efficiency
• Outdoor Environments
• Model Problem
• Conceptual Knowledge
• Class Of Problems
• Tacit Knowledge
• Point System
• External Input
• Factual Knowledge
• Practical Choice
• Similarity Graph
• Vertex Labels
• Communication Graph
• Protocol Execution
• Number Of Processors
• Choice Problem
• Precise Sense
• Lemma States