Common knowledge and consistent simultaneous coordination
There is a very close relationship between common knowledge and simultaneity in synchronous distributed systems. The analysis of several well-known problems in terms of common knowledge has lead to round- optimal protocols for these problems, including Reliable Broadcast, Distributed Consensus, and the Distributed Firing Squad problem. These problems require that the correct processors coordinate their actions in some way but place no restrictions on the behavior of the faulty processors. In systems with benign processor failures, however, it is reasonable to require that the actions of a faulty processor be consistent with those of the correct processors, assuming it performs any action at all. We consider problems requiring consistent, simultaneious coordination. We then analyze these problems in terms of common knowledge in several failure models. The analysis of these stronger problems requires a stronger definition of common knowledge, and we study the relationship between these two definitions. In many cases, the two definitions are actually equivalent, and simple modifications of previous solutions yield round-optimal solutions to these problems. When the definitions differ, however, we show that such problems cannot be solved, even in failure- free executions.
- A characterization of eventual Byzantine agreement
- A lower bound for the time to assure interactive consistency
- Automatically increasing the fault-tolerance of distributed algorithms
- Distributed agreement in the presence of processor and communication faults
- Early stopping in Byzantine agreement
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Knowledge and common knowledge in a distributed environment
- Programming simultaneous actions using common knowledge
- Reaching Agreement in the Presence of Faults
- The Byzantine Generals Problem
- The Distributed Firing Squad Problem
- Using knowledge to optimally achieve coordination in distributed systems
- Programming simultaneous actions using common knowledge
- Concurrent common knowledge: Defining agreement for asynchronous systems
- Using knowledge to optimally achieve coordination in distributed systems
- Common knowledge revisited
- A knowledge-theoretic analysis of uniform distributed coordination and failure detectors
- Continuous consensus via common knowledge
- Agent-time epistemics and coordination
- The buck stops here: order, chance, and coordination in distributed control
- Symmetric and Synchronous Communication in Peer-to-Peer Networks
- Continuous Consensus with Failures and Recoveries
- Optimum Simultaneous Consensus for General Omissions Is Equivalent to an NP Oracle
- scientific article; zbMATH DE number 67445 (Why is no real title available?)
- scientific article; zbMATH DE number 2149446 (Why is no real title available?)
- Relating knowledge and coordinated action: the knowledge of preconditions principle
- Combining fault injection and model checking to verify fault tolerance, recoverability, and diagnosability in multi-agent systems
- The complexity of almost-optimal simultaneous coordination
- Simultaneity is harder than agreement
- Knowledge and common knowledge in a Byzantine environment: Crash failures
This page was built for publication: Common knowledge and consistent simultaneous coordination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2365570)
