A Sheaf-Theoretic Characterization of Tasks in Distributed Systems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911123863764992 |
|---|---|
| author | Felber, Stephan Flores, Bernardo Hummes Galeana, Hugo Rincon |
| author_facet | Felber, Stephan Flores, Bernardo Hummes Galeana, Hugo Rincon |
| contents | We introduce a sheaf-theoretic characterization of task solvability in general distributed computing models, unifying distinct approaches to message-passing models. We establish cellular sheaves as a natural mathematical framework for analyzing the global consistency requirements of local computations. Our main contribution is a task sheaf construction that explicitly relates both the distributed system and task, in which terminating solutions are precisely its global sections. We prove that a task can only be solved by a system when such sections exist in a task sheaf obtained from an execution cut, the frontier in which processes have enough information to decide. Our characterization is model-independent, working under varying synchronicity, failures and message adversaries, as long as the model produces runs composed of global states of the system. Furthermore, we show that the cohomology of the task sheaf provides a linear algebraic description of the decision space of the processes, and encodes the obstructions to find solutions. This opens way to a computational approach to protocol synthesis, which we illustrated by deriving a protocol for approximate agreement. This work bridges distributed computing and sheaf theory, providing both theoretical foundations for analyzing task solvability and tools for protocol design leveraging computational topology. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02556 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Sheaf-Theoretic Characterization of Tasks in Distributed Systems Felber, Stephan Flores, Bernardo Hummes Galeana, Hugo Rincon Distributed, Parallel, and Cluster Computing Category Theory C.2.4; F.1.0 We introduce a sheaf-theoretic characterization of task solvability in general distributed computing models, unifying distinct approaches to message-passing models. We establish cellular sheaves as a natural mathematical framework for analyzing the global consistency requirements of local computations. Our main contribution is a task sheaf construction that explicitly relates both the distributed system and task, in which terminating solutions are precisely its global sections. We prove that a task can only be solved by a system when such sections exist in a task sheaf obtained from an execution cut, the frontier in which processes have enough information to decide. Our characterization is model-independent, working under varying synchronicity, failures and message adversaries, as long as the model produces runs composed of global states of the system. Furthermore, we show that the cohomology of the task sheaf provides a linear algebraic description of the decision space of the processes, and encodes the obstructions to find solutions. This opens way to a computational approach to protocol synthesis, which we illustrated by deriving a protocol for approximate agreement. This work bridges distributed computing and sheaf theory, providing both theoretical foundations for analyzing task solvability and tools for protocol design leveraging computational topology. |
| title | A Sheaf-Theoretic Characterization of Tasks in Distributed Systems |
| topic | Distributed, Parallel, and Cluster Computing Category Theory C.2.4; F.1.0 |
| url | https://arxiv.org/abs/2503.02556 |