Communication Pattern Logic: Epistemic and Topological Views
Por:
Castañeda A., van Ditmarsch, Hans, Rosenblueth, David A., Velazquez, Diego A.
Publicada:
1 ene 2023
Ahead of Print:
1 jul 2023
Categoría:
Philosophy
Resumen:
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. © 2023, The Author(s), under exclusive licence to Springer Nature B.V.
Filiaciones:
Castañeda A.:
Instituto de Matematicas, Universidad Nacional Autonoma de Mexico, UNAM, Mexico
van Ditmarsch, Hans:
University of Toulouse, CNRS, IRIT, France
Univ Toulouse, CNRS, IRIT, Toulouse, France
Rosenblueth, David A.:
Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas, Universidad Nacional Autónoma de México, UNAM, Mexico
Univ Nacl Autonoma Mexico, UNAM, Inst Invest Matemat Aplicadas & Sistemas, University City, Mexico
Velazquez, Diego A.:
Programa de Doctorado en Ciencia e Ingenieriá de la Computación, Universidad Nacional Autónoma de México, UNAM, Mexico
Univ Nacl Autonoma Mexico, Programa Doctorado Ciencia Ingenieria Comp, UNAM, University City, Mexico
Univ Nacl Autonoma Mexico, UNAM, Inst Matemat, University City, Mexico
Green Submitted
|