A categorical and logical framework for iterated protocols
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915288018059264 |
|---|---|
| author | Goubault, Eric Flores, Bernardo Hummes Kniazev, Roman Ledent, Jeremy Rajsbaum, Sergio |
| author_facet | Goubault, Eric Flores, Bernardo Hummes Kniazev, Roman Ledent, Jeremy Rajsbaum, Sergio |
| contents | In this article, we show that the now classical protocol complex approach to distributed task solvability of Herlihy et al. can be understood in standard categorical terms. First, protocol complexes are functors, from chromatic (semi-) simplicial sets to chromatic simplicial sets, that naturally give rise to algebras. These algebras describe the next state operator for the corresponding distributed systems. This is constructed for semi-synchronous distributed systems with general patterns of communication for which we show that these functors are always Yoneda extensions of simpler functors, implying a number of interesting properties. Furthermore, for these protocol complex functors, we prove the existence of a free algebra on any initial chromatic simplicial complex, modeling iterated protocol complexes. Under this categorical formalization, protocol complexes are seen as transition systems, where states are structured as chromatic simplicial sets. We exploit the epistemic interpretation of chromatic simplicial sets and the underlying transition system (or algebra) structure to introduce a temporal-epistemic logic and its semantics on all free algebras on chromatic simplicial sets. We end up by giving hints on how to extend this framework to more general dynamic network graphs and state-dependent protocols, and give example in fault-tolerant distributed systems and mobile robotics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_10071 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A categorical and logical framework for iterated protocols Goubault, Eric Flores, Bernardo Hummes Kniazev, Roman Ledent, Jeremy Rajsbaum, Sergio Logic in Computer Science Distributed, Parallel, and Cluster Computing In this article, we show that the now classical protocol complex approach to distributed task solvability of Herlihy et al. can be understood in standard categorical terms. First, protocol complexes are functors, from chromatic (semi-) simplicial sets to chromatic simplicial sets, that naturally give rise to algebras. These algebras describe the next state operator for the corresponding distributed systems. This is constructed for semi-synchronous distributed systems with general patterns of communication for which we show that these functors are always Yoneda extensions of simpler functors, implying a number of interesting properties. Furthermore, for these protocol complex functors, we prove the existence of a free algebra on any initial chromatic simplicial complex, modeling iterated protocol complexes. Under this categorical formalization, protocol complexes are seen as transition systems, where states are structured as chromatic simplicial sets. We exploit the epistemic interpretation of chromatic simplicial sets and the underlying transition system (or algebra) structure to introduce a temporal-epistemic logic and its semantics on all free algebras on chromatic simplicial sets. We end up by giving hints on how to extend this framework to more general dynamic network graphs and state-dependent protocols, and give example in fault-tolerant distributed systems and mobile robotics. |
| title | A categorical and logical framework for iterated protocols |
| topic | Logic in Computer Science Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2505.10071 |