Communication pattern logic: epistemic and topological views

DOI10.1007/S10992-023-09713-8MaRDI QIDQ6054065zbMATH OpenFDO

Authors Armando Castañeda, Hans van Ditmarsch, David A. Rosenblueth, Diego A. Velázquez

Publication date 24 October 2023

Published in Journal of Philosophical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.00823

zbMATH Keywords

combinatorial topologydistributed computingdynamic epistemic logicmodal logicmultiagent systems

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Abstract: We propose communication pattern logic. A communication pattern describes how processes or agents inform each other, independently of the information content. The full-information protocol in distributed computing is the special case wherein all agents inform each other. We study this protocol in distributed computing models where communication might fail: an agent is certain about the messages it receives, but it may be uncertain about the messages other agents have received. In a dynamic epistemic logic with distributed knowledge and with modalities for communication patterns, the latter are interpreted by updating Kripke models. We propose an axiomatization of communication pattern logic, and we show that collective bisimilarity (comparing models on their distributed knowledge) is preserved when updating models with communication patterns. We can also interpret communication patterns by updating simplicial complexes, a well-known topological framework for distributed computing. We show that the different semantics correspond, and propose collective bisimulation between simplicial complexes.

Cites work

• A dynamic epistemic logic analysis of equality negation and other epistemic covering tasks
• A simplicial complex model for dynamic epistemic logic to study distributed task computability
• A survey of gossiping and broadcasting in communication networks
• Action emulation
• Arrow update logic
• Arrow update synthesis
• Asynchronous announcements
• Cheating husbands and other stories: A case study of knowledge, action, and communication
• Distributed knowledge
• Dynamic epistemic logic
• Dynamic logic of preference upgrade
• Free logic and the concept of existence
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Group announcement logic
• Handbook of epistemic logic
• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Merging frameworks for interaction
• Modal logic
• Moorean phenomena in epistemic logic
• Oblivious Collaboration
• On axiomatizations of public announcement logic
• Public announcement logic with distributed knowledge: expressivity, completeness and complexity
• Reasoning about information change
• Relativized common knowledge for dynamic epistemic logic
• Resolving distributed knowledge
• The asynchronous computability theorem for t-resilient tasks
• The Byzantine Generals Problem
• The Heard-Of model: computing in distributed systems with benign faults
• The logic of public announcements, common knowledge, and private suspicions
• Topological Characterization of Consensus under General Message Adversaries
• Wait-free k-set agreement is impossible
• Wanted dead or alive: epistemic logic for impure simplicial complexes

Cited in

(3)

• Simplicial models for the epistemic logic of faulty agents
• Synergistic knowledge
• A combinatorial topology approach to Arrow's impossibility theorem

This page was built for publication: Communication pattern logic: epistemic and topological views

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6054065)