A simplicial complex model for dynamic epistemic logic to study distributed task computability
From MaRDI portal
Publication:2029604
Logics of knowledge and belief (including belief change) (03B42) Homotopical algebra, Quillen model categories, derivators (18N40) Abstract and axiomatic homotopy theory in algebraic topology (55U35) Distributed systems (68M14) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Abstract: The usual epistemic model S5n for a multi-agent system is based on a Kripke frame, which is a graph whose edges are labeled with agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in this structure, by considering a dual, simplicial complex model. We use dynamic epistemic logic (DEL) to study how an epistemic simplicial complex model changes after a set of agents communicate with each other. We concentrate on an action model that represents the so called immediate snapshot communication patterns of asynchronous agents, because it is central to distributed computability (but our setting works for other communication patterns). There are topological invariants preserved from the initial epistemic complex to the one after the action model is applied, which determine the knowledge that the agents gain after communication. Finally, we describe how a distributed task specification can be modeled as a DEL action model, and show that the topological invariants determine whether the task is solvable. We thus provide a bridge between DEL and the topological theory of distributed computability, which studies task solvability in a shared memory or message passing architecture.
Recommendations
- A simplicial complex model for dynamic epistemic logic to study distributed task computability
- On knowledge and communication complexity in distributed systems
- A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks
- Symbolic model checking for Dynamic Epistemic Logic — S5 and beyond*
- Observing Distributed Computation. A Dynamic-Epistemic Approach
Cites work
- A combinatorial characterization of the distributed 1-solvable tasks
- A completeness theorem in modal logic
- A dynamic epistemic logic analysis of the equality negation task
- An Intuitionistic Epistemic Logic for Sequential Consistency on Shared Memory
- Announcements to attentive agents
- Asynchronous announcements
- Chromatic subdivision of a simplicial complex
- Collapsibility of read/write models using discrete Morse theory
- Computable obstructions to wait-free computability
- Dynamic Epistemic Logic and Knowledge Puzzles
- Graph theory with applications
- scientific article; zbMATH DE number 996442 (Why is no real title available?)
- scientific article; zbMATH DE number 1559574 (Why is no real title available?)
- scientific article; zbMATH DE number 795590 (Why is no real title available?)
- Impossibility of distributed consensus with one faulty process
- Interpreted systems and Kripke models for multiagent systems from a categorical perspective
- Knowledge in multiagent systems: initial configurations and broadcast
- Logics of communication and change
- On the logic of ``agreeing to disagree type results
- Relating knowledge and coordinated action: the knowledge of preconditions principle
- Semantic results for ontic and epistemic change
- Simulations and reductions for colorless tasks
- The algebra of topology
- The Combinatorial Structure of Wait-Free Solvable Tasks
- The renaming problem in shared memory systems: an introduction
- Three-Processor Tasks Are Undecidable
- Topo-logic as a dynamic-epistemic logic
- Unbeatable set consensus via topological and combinatorial reasoning
- Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
Cited in
(21)- On knowledge and communication complexity in distributed systems
- A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks
- Wanted dead or alive: epistemic logic for impure simplicial complexes
- Geometric aspects of multiagent systems
- A simplicial complex model for dynamic epistemic logic to study distributed task computability
- The McKinsey-Tarski theorem for locally compact ordered spaces
- Communication pattern logic: epistemic and topological views
- Impure Simplicial Complexes: Complete Axiomatization
- A Spatial Logic for Simplicial Models
- Modal and justification logics for multi-agent systems (invited talk)
- Simplicial models for the epistemic logic of faulty agents
- Communication pattern models: an extension of action models for dynamic-network distributed systems
- Synergistic knowledge
- A many-sorted epistemic logic for chromatic hypergraphs
- The topology of surprise
- Wanted dead or alive: epistemic logic for impure simplicial complexes
- On two- and three-valued semantics for impure simplicial complexes
- The topological mu-calculus: completeness and decidability
- Simplicial belief
- R-Mod: minimal structural revision of \(\mathrm{S}5\) epistemic models
- A dynamic epistemic logic analysis of the equality negation task
This page was built for publication: A simplicial complex model for dynamic epistemic logic to study distributed task computability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029604)
