Programming simultaneous actions using common knowledge
This work applies the theory of knowledge in distributed systems to the design of efficient fault-tolerant protocols. We define a large class of problems requiring coordinated, simultaneous action in synchronous systems, and give a method of transforming specifications of such problems into protocols that are optimal in all runs: these protocols are guaranteed to perform the simultaneous actions as soon as any other protocol could possibly perform them, given the input to the system and faulty processor behavior. This transformation is performed in two steps. In the first step we extract, directly from the problem specification, a high-level protocol programmed using explicit tests for common knowledge. In the second step we carefully analyze when facts become common knowledge, thereby providing a method of efficiently implementing these protocols in many variants of the omissions failure model. In the generalized omissions model, however, our analysis shows that testing for common knowledge is NP-hard. Given the close correspondence between common knowledge and simultaneous actions, we are able to show that no optimal protocol for any such problem can be computationally efficient in this model. The analysis in this paper exposes many subtle differences between the failure models, including the precise point at which this gap in complexity occurs.
- Common knowledge and consistent simultaneous coordination
- Reasoning about concurrent interaction
- Reasoning about effects of concurrent actions
- Entailment-based actions for coordination
- Parallel action: Concurrent dynamic logic with independent modalities
- scientific article; zbMATH DE number 2182499
- Representing and reasoning about concurrent actions with abductive logic programs
- Asynchronous knowledge with hidden actions in the situation calculus
- scientific article; zbMATH DE number 928018
- A lower bound for the time to assure interactive consistency
- Distributed agreement in the presence of processor and communication faults
- How processes learn
- scientific article; zbMATH DE number 3902018 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Reaching Agreement in the Presence of Faults
- The Distributed Firing Squad Problem
- On the round complexity of Byzantine agreement without initial set-up
- I'm OK if you're OK: On the notion of trusting commmunication
- A guide to completeness and complexity for modal logics of knowledge and belief
- Concurrent common knowledge: Defining agreement for asynchronous systems
- Modelling knowledge and action in distributed systems
- Using knowledge to optimally achieve coordination in distributed systems
- Wait-free implementations in message-passing systems
- Knowledge in shared memory systems.
- Belief as defeasible knowledge
- Common knowledge and update in finite environments
- Choosing social laws for multi-agent systems: Minimality and simplicity
- Naming and identity in epistemic logic. II: A first-order logic for naming
- Continuous consensus via common knowledge
- Unbeatable consensus
- Common knowledge and consistent simultaneous coordination
- Coordinated consensus in dynamic networks
- Error-free multi-valued consensus with Byzantine failures
- Distributed graph coloring in a few rounds
- MIS on trees
- Toward more localized local algorithms, removing assumptions concerning global knowledge
- The complexity of robust atomic storage
- Resilience of mutual exclusion algorithms to transient memory faults
- The impact of memory models on software reliability in multiprocessors
- A complexity separation between the cache-coherent and distributed shared memory models
- From bounded to unbounded concurrency objects and back
- Locally checkable proofs
- Fault-tolerant spanners
- Adaptively secure broadcast, revisited
- Scalable rational secret sharing
- Analyzing consistency properties for fun and profit
- Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions
- Optimal-time adaptive strong renaming, with applications to counting
- The round complexity of distributed sorting, extended abstract
- A tight unconditional lower bound on distributed randomwalk computation
- Minimum congestion mapping in a cloud
- Conflict on a communication channel
- Xheal, localized self-healing using expanders
- Stability of a peer-to-peer communication system
- Tight bounds on information dissemination in sparse mobile networks
- Time-efficient randomized multiple-message broadcast in radio networks
- Faster information dissemination in dynamic networks via network coding
- A knowledge-based analysis of the blockchain protocol
- Continuous Consensus with Failures and Recoveries
- No Double Discount: Condition-Based Simultaneity Yields Limited Gain
- Optimum Simultaneous Consensus for General Omissions Is Equivalent to an NP Oracle
- scientific article; zbMATH DE number 4085005 (Why is no real title available?)
- No double discount: condition-based simultaneity yields limited gain
- Reasoning about knowledge and messages in asynchronous multi-agent systems
- States of knowledge
- Relating knowledge and coordinated action: the knowledge of preconditions principle
- Causality and epistemic reasoning in Byzantine multi-agent systems
- Knowledge-based programs
- A note on knowledge-based programs and specifications
- Hundreds of impossibility results for distributed computing
- Using counterfactuals in knowledge-based programming
- Dealing with logical omniscience: expressiveness and pragmatics
- Continuous Consensus with Ambiguous Failures
- Byzantine agreement with homonyms
- Structuring unreliable radio networks
- Distributed deterministic edge coloring using bounded neighborhood independence
- Compact policy routing
- Order optimal information spreading using algebraic gossip
- Levels of knowledge in distributed systems.
- A Sufficient Condition for Gaining Belief in Byzantine Fault-Tolerant Distributed Systems
- Epistemic Logics of Structured Intensional Groups
- Comparing the Update Expressivity of Communication Patterns and Action Models
- Optimal Eventual Byzantine Agreement Protocols with Omission Failures
- A knowledge-based analysis of global function computation
- Revisiting epistemic logic with names
- Fire!
- The complexity of almost-optimal simultaneous coordination
- Communication modalities
- Simultaneity is harder than agreement
- The perfectly synchronized round-based model of distributed computing
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Continuous consensus with ambiguous failures
This page was built for publication: Programming simultaneous actions using common knowledge
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104074)
