Knowledge and common knowledge in a distributed environment
From MaRDI portal
Publication:3477999
DOI10.1145/79147.79161zbMath0699.68115arXivcs/0006009OpenAlexW2022205872WikidataQ30051985 ScholiaQ30051985MaRDI QIDQ3477999
Joseph Y. Halpern, Yoram Moses
Publication date: 1990
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0006009
verificationreliabilitynetworkstestingfault-tolerancecommon knowledgeprogramnetwork protocolsdistributed knowledgeprogramsprotocol verificationknowledge representation formalisms and methodscomputer-communicationspecifying and verifying and reasoning about
Specification and verification (program logics, model checking, etc.) (68Q60) Artificial intelligence (68T99) Theory of operating systems (68N25) Theory of software (68N99)
Related Items
Unbeatable consensus, Formal theories of knowledge in AI and robotics, Minimal knowledge problem: A new approach, How processes learn, Common knowledge and consistent simultaneous coordination, Mutual exclusion as a matter of priority, Knowledge and best responses in games, A non-minimal but very weak axiomatization of common belief, Contemporary epistemic logic and the Lockean thesis, On interactive knowledge with bounded communication, A logic for extensional protocols, Dynamic input/output automata: a formal and compositional model for dynamic systems, Performing work in broadcast networks, Logic and social cognition. The facts matter, and so do computational models, Interpreting logics of knowledge in propositional dynamic logic, The synthesis of communication protocols, The relationship between knowledge, belief, and certainty, Wanted dead or alive: epistemic logic for impure simplicial complexes, Knowledge-based strategies for multi-agent teams playing against nature, Subjective reasoning -- dynamic games, Arbitrary arrow update logic, The topology of distributed adversaries, Everyone knows that everyone knows, Integration of weighted knowledge bases, Belief closure: A semantics of common knowledge for modal propositional logic, Formalizing common belief with no underlying assumption on individual beliefs, Common knowledge and update in finite environments, On the knowledge requirements of tasks, 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, 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, Modeling agents as qualitative decision makers, Automata for epistemic temporal logic with synchronous communication, Correlated knowledge: an epistemic-logic view on quantum entanglement, A semantics for reasoning consistently in the presence of inconsistency, Common learning with intertemporal dependence, To know or not to know: Epistemic approaches to security protocol verification, No double discount: condition-based simultaneity yields limited gain, Revisiting games of incomplete information with analogy-based expectations, A modal type theory for formalizing trusted communications, Communication, timing, and common learning, The many faces of closure and introspection. An ineractive perspective, Probabilistic belief logic and its probabilistic Aumann semantics, Computing distributed knowledge as the greatest lower bound of knowledge, A computer scientist looks at game theory., Continuous consensus via common knowledge, The shadow knows: refinement and security in sequential programs, Efficient communication in the electronic mail game, Second-order propositional modal logic: expressiveness and completeness results, Agreeing to disagree in probabilistic dynamic epistemic~logic, Fast and compact self-stabilizing verification, computation, and fault detection of an MST, Distributed knowability and Fitch's paradox, On the Unusual Effectiveness of Logic in Computer Science, The complexity of almost-optimal simultaneous coordination, Epistemic protocols for dynamic gossip, Optimistically tuning synchronous Byzantine consensus: another win for null messages, Bilattice logic of epistemic actions and knowledge, A guide to completeness and complexity for modal logics of knowledge and belief, Formal timing analysis of distributed systems, Graph aggregation, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Concurrent common knowledge: Defining agreement for asynchronous systems, Extensive games with possibly unaware players, Infinite games with finite knowledge gaps, Single-bit messages are insufficient for data link over duplicating channels, Local properties in modal logic, The Ryōan-ji axiom for common knowledge on hypergraphs, Acknowledged broadcasting in ad hoc radio networks, On the logical unsolvability of the Gettier problem, About cut elimination for logics of common knowledge, Justified common knowledge, Common knowledge does not have the Beth property, Deduction chains for common knowledge, Recursively modeling other agents for decision making: a research perspective, Knowledge, behavior, and rationality: rationalizability in epistemic games, Reasoning about distributed information with infinitely many agents, Intensional protocols for dynamic epistemic logic, Group knowledge is not always distributed (neither is it always implicit), Simultaneity is harder than agreement, Syntactic cut-elimination for common knowledge, Correlated Information: A Logic for Multi-Partite Quantum Systems, Reaching agreements through argumentation: a logical model and implementation, A logic for multiple-source approximation systems with distributed knowledge base, Efficiency and equilibrium in the electronic mail game; the general case, A model of reasoning about knowledge, Epistemic interpretations of decentralized discrete-event system problems, Using knowledge to optimally achieve coordination in distributed systems, Wait-free implementations in message-passing systems, Common knowledge revisited, Naming and identity in epistemic logic. II: A first-order logic for naming, Asynchronous knowledge with hidden actions in the situation calculus, Knowledge in shared memory systems., Belief as defeasible knowledge, On the proof theory of infinitary modal logic, Non-circular proofs and proof realization in modal logic, Probabilistic Common Knowledge Among Infinite Number of Agents, Reconstruction of non‐logical axioms from the propositions of multi‐agent doxastic logic, Unnamed Item, О трудностях определения имплицитного знания группы, Under the Hood of the Bakery Algorithm: Mutual Exclusion as a Matter of Priority, Beyond Lamport's Happened-before, Reasoning about knowledge and messages in asynchronous multi-agent systems, A quantitative analysis of modal logic, Unnamed Item, A complexity separation between the cache-coherent and distributed shared memory models, From bounded to unbounded concurrency objects and back, The space complexity of long-lived and one-shot timestamp implementations, 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, A tight unconditional lower bound on distributed randomwalk computation, Minimum congestion mapping in a cloud, Conflict on a communication channel, 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, Group Belief, Communication pattern logic: epistemic and topological views, Dissecting distributed coordination, Reasoning about knowledge and conditional probability, Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds, Message-optimal protocols for Byzantine Agreement, The Failure Discovery problem, Impure Simplicial Complexes: Complete Axiomatization, Do what you know: coupling knowledge with action in discrete-event systems, METRICS FOR FORMAL STRUCTURES, WITH AN APPLICATION TO KRIPKE MODELS AND THEIR DYNAMICS, A Sufficient Condition for Gaining Belief in Byzantine Fault-Tolerant Distributed Systems, HyperATL*: A Logic for Hyperproperties in Multi-Agent Systems, Salience reasoning in coordination games, The limits to gossip: second-order shared knowledge of all secrets is unsatisfiable, Unnamed Item, Joint Behavior and Common Belief, Optimal Eventual Byzantine Agreement Protocols with Omission Failures, On the Decision Problem for Two-Variable First-Order Logic, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Order optimal information spreading using algebraic gossip, Unnamed Item, How to Solve Consensus in the Smallest Window of Synchrony, Continuous Consensus with Failures and Recoveries, No Double Discount: Condition-Based Simultaneity Yields Limited Gain, Keeping track of the latest gossip in a distributed system, Knowledge-based programs, A note on knowledge-based programs and specifications, Hundreds of impossibility results for distributed computing, Using counterfactuals in knowledge-based programming, The power of logical clock abstractions, The Proof Theory of Common Knowledge, Partially Ordered Knowledge Sharing and Fractionated Systems in the Context of other Models for Distributed Computing, Introduction (to the special issue on: Economics and artificial intelligence), Coordinated action in the electronic mail game, Common knowledge and consensus with noisy communication, A communication algorithm for teamwork in multi-agent environments, Structuring unreliable radio networks, Byzantine agreement with homonyms, Distributed deterministic edge coloring using bounded neighborhood independence, Compact policy routing, Individual learning of coordination knowledge, Levels of knowledge in distributed systems., Tableau-Based Procedure for Deciding Satisfiability in the Full Coalitional Multiagent Epistemic Logic, Learning in a Changing World, an Algebraic Modal Logical Approach, Towards Partial Order Reduction for Model Checking Temporal Epistemic Logic, DEL-sequents for progression, DEL-sequents for progression, Weak models of distributed computing, with connections to modal logic, Unnamed Item, Common Knowledge and the Knowledge Account of Assertion, First-Order Linear-Time Epistemic Logic with Group Knowledge: An Axiomatisation of the Monodic Fragment, REASONING WITH PROTOCOLS UNDER IMPERFECT INFORMATION, Syntactic Cut-elimination for Common Knowledge, BDD-based decision procedures for the modal logic K ★, Taming the Complexity of Temporal Epistemic Reasoning, Temporal Aspects of the Dynamics of Knowledge, AN OVERVIEW OF ROUGH SET SEMANTICS FOR MODAL AND QUANTIFIER LOGICS, Xheal
