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)- Syntactic cut-elimination for common knowledge
- Formal theories of knowledge in AI and robotics
- How processes learn
- Interpreting logics of knowledge in propositional dynamic logic
- The synthesis of communication protocols
- I'm OK if you're OK: On the notion of trusting commmunication
- On the knowledge requirements of tasks
- A guide to completeness and complexity for modal logics of knowledge and belief
- Formal timing analysis of distributed systems
- Concurrent common knowledge: Defining agreement for asynchronous systems
- Modelling knowledge and action in distributed systems
- Reaching agreements through argumentation: a logical model and implementation
- A model of reasoning about knowledge
- Using knowledge to optimally achieve coordination in distributed systems
- Wait-free implementations in message-passing systems
- Common knowledge revisited
- Knowledge in shared memory systems.
- Belief as defeasible knowledge
- Minimal knowledge problem: A new approach
- Knowledge and best responses in games
- A non-minimal but very weak axiomatization of common belief
- The relationship between knowledge, belief, and certainty
- Belief closure: A semantics of common knowledge for modal propositional logic
- Common knowledge and update in finite environments
- Modeling agents as qualitative decision makers
- Probabilistic belief logic and its probabilistic Aumann semantics
- A computer scientist looks at game theory.
- Mutual exclusion as a matter of priority
- Second-order propositional modal logic: expressiveness and completeness results
- Local properties in modal logic
- On the logical unsolvability of the Gettier problem
- About cut elimination for logics of common knowledge
- Group knowledge is not always distributed (neither is it always implicit)
- Efficiency and equilibrium in the electronic mail game; the general case
- Naming and identity in epistemic logic. II: A first-order logic for naming
- Simplifying the design of knowledge-based algorithms using knowledge consistency
- Recognition of distributed intelligence
- Common learning with intertemporal dependence
- The many faces of closure and introspection. An ineractive perspective
- Continuous consensus via common knowledge
- Bilattice logic of epistemic actions and knowledge
- Knowledge, behavior, and rationality: rationalizability in epistemic games
- Reasoning about distributed information with infinitely many agents
- Epistemic interpretations of decentralized discrete-event system problems
- On the proof theory of infinitary modal logic
- Unbeatable consensus
- Wanted dead or alive: epistemic logic for impure simplicial complexes
- Knowledge-based strategies for multi-agent teams playing against nature
- Integration of weighted knowledge bases
- Formalizing common belief with no underlying assumption on individual beliefs
- Epistemic reasoning with Byzantine-faulty agents
- Optimistically tuning synchronous Byzantine consensus: another win for null messages
- Extensive games with possibly unaware players
- The Ryōan-ji axiom for common knowledge on hypergraphs
- Recursively modeling other agents for decision making: a research perspective
- Intensional protocols for dynamic epistemic logic
- Asynchronous knowledge with hidden actions in the situation calculus
- Non-circular proofs and proof realization in modal logic
- Common knowledge and consistent simultaneous coordination
- Performing work in broadcast networks
- Subjective reasoning -- dynamic games
- Revisiting games of incomplete information with analogy-based expectations
- Distributed knowability and Fitch's paradox
- Justified common knowledge
- Deduction chains for common knowledge
- Dynamic input/output automata: a formal and compositional model for dynamic systems
- A semantics for reasoning consistently in the presence of inconsistency
- Computing distributed knowledge as the greatest lower bound of knowledge
- On the unusual effectiveness of logic in computer science
- Correlated information: a logic for multi-partite quantum systems
- On interactive knowledge with bounded communication
- A logic for extensional protocols
- 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
- Common knowledge in email exchanges
- Contemporary epistemic logic and the Lockean thesis
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)
