Impure Simplicial Complexes: Complete Axiomatization
From MaRDI portal
Abstract: Combinatorial topology is used in distributed computing to model concurrency and asynchrony. The basic structure in combinatorial topology is the simplicial complex, a collection of subsets called simplices of a set of vertices, closed under containment. Pure simplicial complexes describe message passing in asynchronous systems where all processes (agents) are alive, whereas impure simplicial complexes describe message passing in synchronous systems where processes may be dead (have crashed). Properties of impure simplicial complexes can be described in a three-valued multi-agent epistemic logic where the third value represents formulas that are undefined, e.g., the knowledge and local propositions of dead agents. In this work we present the axiomatization called and show that it is sound and complete for the class of impure complexes. The completeness proof involves the novel construction of the canonical simplicial model and requires a careful manipulation of undefined formulas.
Recommendations
- Pure simplicial complexes and well-covered graphs
- A simplification of the Eilenberg-Steenrod axioms for finite simplicial complexes
- Completions and Simplicial Complexes
- scientific article; zbMATH DE number 6734532
- Alexandroff spaces via simplicial complexes
- Simplicial girth and pure resolutions
- Finite simplicial multicomplexes
- Simplicial structures in higher Auslander-Reiten theory
- Simplicial complexes and closure systems induced by indistinguishability relations
- De Rham theory of a simplicial complex
Cites work
- A combinatorial characterization of the distributed 1-solvable tasks
- A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks
- A new hope
- A simplicial complex model for dynamic epistemic logic to study distributed task computability
- A Simplicial Model for KB4_n: Epistemic Logic with Agents that May Die
- A Sound Foundation for the Topological Approach to Task Solvability
- An axiomatic approach to computing the connectivity of synchronous and asynchronous systems
- An overview of synchronous message-passing and topology
- Belief as defeasible knowledge
- DEFINING KNOWLEDGE IN TERMS OF BELIEF: THE MODAL LOGIC PERSPECTIVE
- Distributed computing through combinatorial topology
- Dynamic epistemic logic
- Handbook of epistemic logic
- Impossibility of distributed consensus with one faulty process
- Knowledge and belief. An introduction to the logic of the two notions. Prepared by Vincent F. Hendricks and John Symons
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Knowledge and common knowledge in a distributed environment
- On knowledge and communication complexity in distributed systems
- Resolving distributed knowledge
- The logic of public announcements, common knowledge, and private suspicions
- The topological structure of asynchronous computability
- Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
- Wanted dead or alive: epistemic logic for impure simplicial complexes
Cited in
(4)
This page was built for publication: Impure Simplicial Complexes: Complete Axiomatization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076177)
