Knowledge and common knowledge in a distributed environment
From MaRDI portal
Abstract: Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols. Communication in a distributed system can be viewed as the act of transforming the system's state of knowledge. This paper presents a general framework for formalizing and reasoning about knowledge in distributed systems. We argue that states of knowledge of groups of processors are useful concepts for the design and analysis of distributed protocols. In particular, distributed knowledge corresponds to knowledge that is ``distributed among the members of the group, while common knowledge corresponds to a fact being ``publicly known. The relationship between common knowledge and a variety of desirable actions in a distributed system is illustrated. Furthermore, it is shown that, formally speaking, in practical systems common knowledge cannot be attained. A number of weaker variants of common knowledge that are attainable in many cases of interest are introduced and investigated.
Recommendations
Cited in
(only showing first 100 items - show all)- Towards Partial Order Reduction for Model Checking Temporal Epistemic Logic
- Wait-free implementations in message-passing systems
- Faster information dissemination in dynamic networks via network coding
- Tight bounds on information dissemination in sparse mobile networks
- Bilattice logic of epistemic actions and knowledge
- Reasoning with protocols under imperfect information
- Group Belief
- Levels of knowledge in distributed systems.
- The synthesis of communication protocols
- Recognition of distributed intelligence
- Resilience of mutual exclusion algorithms to transient memory faults
- Single-bit messages are insufficient for data link over duplicating channels
- Coordinating distributed organizational knowledge
- Reasoning about Knowledge in Asynchronous Distributed Systems
- scientific article; zbMATH DE number 795590 (Why is no real title available?)
- scientific article; zbMATH DE number 1497792 (Why is no real title available?)
- Keeping track of the latest gossip in a distributed system
- HyperATL*: A Logic for Hyperproperties in Multi-Agent Systems
- Deduction chains for common knowledge
- Interpreting logics of knowledge in propositional dynamic logic
- Adaptively secure broadcast, revisited
- Recursively modeling other agents for decision making: a research perspective
- Byzantine agreement with homonyms
- On the Decision Problem for Two-Variable First-Order Logic
- Using knowledge to optimally achieve coordination in distributed systems
- Weak models of distributed computing, with connections to modal logic
- Naming and identity in epistemic logic. II: A first-order logic for naming
- Dissecting distributed coordination
- Finite state implementations of knowledge-based programs (extended abstract)
- Formal theories of knowledge in AI and robotics
- Acknowledged broadcasting in ad hoc radio networks
- Correlated knowledge: an epistemic-logic view on quantum entanglement
- scientific article; zbMATH DE number 7649937 (Why is no real title available?)
- On interactive knowledge with bounded communication
- Common knowledge in email exchanges
- The limits to gossip: second-order shared knowledge of all secrets is unsatisfiable
- The complexity of almost-optimal simultaneous coordination
- Probabilistic belief logic and its probabilistic Aumann semantics
- No double discount: condition-based simultaneity yields limited gain
- A modal type theory for formalizing trusted communications
- Distributed deterministic edge coloring using bounded neighborhood independence
- Coordinated consensus in dynamic networks
- Compact policy routing
- Local properties in modal logic
- Salience reasoning in coordination games
- AN OVERVIEW OF ROUGH SET SEMANTICS FOR MODAL AND QUANTIFIER LOGICS
- Concurrent common knowledge: Defining agreement for asynchronous systems
- I'm OK if you're OK: On the notion of trusting commmunication
- Dynamic input/output automata: a formal and compositional model for dynamic systems
- Common knowledge does not have the Beth property
- Unbeatable consensus
- MIS on trees
- A semantics for reasoning consistently in the presence of inconsistency
- scientific article; zbMATH DE number 7009346 (Why is no real title available?)
- Distributed graph coloring in a few rounds
- Message-optimal protocols for Byzantine Agreement
- Hundreds of impossibility results for distributed computing
- Minimal knowledge problem: A new approach
- Modeling agents as qualitative decision makers
- Individual learning of coordination knowledge
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Groups, communication and coordination
- Time-efficient randomized multiple-message broadcast in radio networks
- Optimistically tuning synchronous Byzantine consensus: another win for null messages
- A logic for extensional protocols
- Non-circular proofs and proof realization in modal logic
- From bounded to unbounded concurrency objects and back
- An epistemic foundation for authentication logics (extended abstract)
- О трудностях определения имплицитного знания группы
- Xheal, localized self-healing using expanders
- Reasoning about knowledge and conditional probability
- Extensive games with possibly unaware players
- The Ryōan-ji axiom for common knowledge on hypergraphs
- A model of reasoning about knowledge
- Toward more localized local algorithms, removing assumptions concerning global knowledge
- scientific article; zbMATH DE number 4085005 (Why is no real title available?)
- Computing distributed knowledge as the greatest lower bound of knowledge
- Under the hood of the bakery algorithm: mutual exclusion as a matter of priority
- On the knowledge requirements of tasks
- Syntactic cut-elimination for common knowledge
- Distributed knowledge
- Taming the Complexity of Temporal Epistemic Reasoning
- Locally checkable proofs
- Relating knowledge and coordinated action: the knowledge of preconditions principle
- Contemporary epistemic logic and the Lockean thesis
- First-Order Linear-Time Epistemic Logic with Group Knowledge: An Axiomatisation of the Monodic Fragment
- Optimal-time adaptive strong renaming, with applications to counting
- Communication pattern logic: epistemic and topological views
- A communication algorithm for teamwork in multi-agent environments
- The shadow knows: refinement and security in sequential programs
- Tableau-Based Procedure for Deciding Satisfiability in the Full Coalitional Multiagent Epistemic Logic
- scientific article; zbMATH DE number 3930375 (Why is no real title available?)
- Common knowledge revisited
- Offline supervisory control synthesis: taxonomy and recent developments
- Analyzing consistency properties for fun and profit
- Stability of a peer-to-peer communication system
- The impact of memory models on software reliability in multiprocessors
- BDD-based decision procedures for the modal logic K ★
- A tight unconditional lower bound on distributed randomwalk computation
- Agreeing to disagree in probabilistic dynamic epistemic~logic
This page was built for publication: Knowledge and common knowledge in a distributed environment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3477999)
