A Sheaf-Theoretic Characterization of Tasks in Distributed Systems

Stephan Felber, Bernardo Hummes Flores, Hugo Rincon Galeana · 2025

Read A Sheaf-Theoretic Characterization of Tasks in Distributed Systems by Stephan Felber, Bernardo Hummes Flores, Hugo Rincon Galeana (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02556.txt.

Introduction

Stephan Felber and co-authors recast distributed computing tasks in the language of sheaf theory, in a 2025 paper. A distributed system is a crew of processes that swap messages and must each reach a choice. Whether a task can be solved at all depends on global rules that local views must jointly meet. Sheaves, a math tool for gluing local data into global wholes, fit that shape well.

Their build, the task sheaf, binds the system and the task into one object. Valid end states of a run are exactly the sheaf's global sections, its full glued wholes. A task is solvable only when such sections exist at the cut where processes know enough to decide. The sheaf's cohomology then charts the choice space and marks where solutions get blocked. The team shows the payoff by deriving a protocol for approximate agreement.

Catalog record

CREATORStephan Felber, Bernardo Hummes Flores, Hugo Rincon Galeana
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE141 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-02556

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Sheaf-Theoretic Characterization of Tasks in Distributed Systems Stephan Felber, Bernardo Hummes Flores, Hugo Rincon Galeana Abstract Task solvability lies at the heart of distributed computing, with direct implications for both theoretical understanding and practical system design. The field has evolved multiple theoretical frameworks for this purpose, including topological approaches, epistemic logic, and adversarial models, but these often address specific problem classes, limiting cross-domain applications. Our approach provides a unifying mathematical perspective across message-passing system models. We introduce a unifying sheaf-theoretic perspective that represents task solvability across message-passing system models while maintaining clear connections to the underlying distributed computing principles. A fundamental challenge in distributed computing is constructing global solutions from local computations and information. Sheaf theory addresses this challenge by providing a mathematical framework for assessing globally consistent properties from locally defined data, offering a natural language to describe and reason about distributed tasks. Sheaves have proven valuable in studying similar local-to-global phenomena, from opinion dynamics to contextuality in quantum mechanics and sensor integration. We now extend this framework to distributed systems. In this paper, we introduce a sheaf-theoretic characterization of task solvability in any model with a message based adversary. We provide a novel construction of a task sheaf, and prove that non-trivial sections correspond to valid solutions of a task, while obstructions to global sections represent system limitations that make tasks unsolvable. Furthermore, we also show that the cohomology of a task sheaf may be used to compute solving protocols. This opens space for new connections between distributed computing and sheaf theory for both protocol design and impossibility analysis. TU Wien, Vienna, [email protected] École Polytechnique, Palaiseau, Francebernardo.hummes-flores@lix.polytechnique.fr0000-0003-2325-1497 TU Berlin, Berlin, [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003753.10003761.10003763¡/concept_id¿ ¡concept_desc¿Theory of computation Distributed computing models¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10002950¡/concept_id¿ ¡concept_desc¿Mathematics of computing¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Distributed computing models ccs Mathematics of computing keywords Task Solvability, Locality, Distributed computing, Sheaf Theory, Kripke Frame, Applied Category Theory, Cohomology Theory † † runningauthor: S. Felber, B. Hummes Flores, H. Rincon Galeana 1 Introduction todoinline, author=R1,caption=1. [It is] somewhat missing motivation for introducing a new formalism.,textcolor=red, todoinline, author=R1,caption=1. [It is] somewhat missing motivation for introducing a new formalism.,textcolor=red, todo: todoinline, author= R1 ,caption=1. [It is] somewhat missing motivation for introducing a new formalism.,textcolor=red, [It is] somewhat missing motivation for introducing a new formalism. todoinline, author=R2,caption=2. Add to the introduction some explanation of what sheaf theory is (and pictures!). Even Categories are not familar to a SIROCCO audience.,textcolor=red, todoinline, author=R2,caption=2. Add to the introduction some explanation of what sheaf theory is (and pictures!). Even Categories are not familar to a SIROCCO audience.,textcolor=red, todo: todoinline, author= R2 ,caption=2. Add to the introduction some explanation of what sheaf theory is (and pictures!). Even Categories are not familar to a SIROCCO audience.,textcolor=red, Add to the introduction some explanation of what sheaf theory is (and pictures!). Even Categories are not familar to a SIROCCO audience. todoinline, author=R2,caption=3. The notions studied in the paper — using per-process indistinguishability — are reminiscent of [Biran, Moran and Zaks https://doi.org/10.1016/0196-6774(90)90020-F]. This paper is not cited, and of course, not discussed.,textcolor=red, todoinline, author=R2,caption=3. The notions studied in the paper — using per-process indistinguishability — are reminiscent of [Biran, Moran and Zaks https://doi.org/10.1016/0196-6774(90)90020-F]. This paper is not cited, and of course, not discussed.,textcolor=red, todo: todoinline, author= R2 ,caption=3. The notions studied in the paper — using per-process indistinguishability — are reminiscent of [Biran, Moran and Zaks https://doi.org/10.1016/0196-6774(90)90020-F]. This paper is not cited, and of course, not discussed.,textcolor=red, The notions studied in the paper — using per-process indistinguishability — are reminiscent of [Biran, Moran and Zaks https://doi.org/10.1016/0196-6774(90)90020-F]. This paper is not cited, and of course, not discussed. todoinline, author=R3,caption=4. Weaknesses: (1) The characterisation only concerns fault-free models (2) The paper is presented in a way that does not welcome a reader without a sheaf-theory background. (3) The bibliography is incomplete and the discussion of related work is superficial. ,textcolor=red, todoinline, author=R3,caption=4. Weaknesses: (1) The characterisation only concerns fault-free models (2) The paper is presented in a way that does not welcome a reader without a sheaf-theory background. (3) The bibliography is incomplete and the discussion of related work is superficial. ,textcolor=red, todo: todoinline, author= R3 ,caption=4. Weaknesses: (1) The characterisation only concerns fault-free models (2) The paper is presented in a way that does not welcome a reader without a sheaf-theory background. (3) The bibliography is incomplete and the discussion of related work is superficial. ,textcolor=red, Weaknesses: (1) The characterisation only concerns fault-free models (2) The paper is presented in a way that does not welcome a reader without a sheaf-theory background. (3) The bibliography is incomplete and the discussion of related work is superficial. todoinline, author=R3,caption=5. The introduction is written in a very abstract yet careless manner, without giving examples or referring to any concrete problem or model of computation. I found it difficult to follow and sometimes I was not even able to understand the logic behind the sequence of claims. As a result, the very motivation of why this particular approach makes sense in exploring distributed computability is not very convincing.,textcolor=red, todoinline, author=R3,caption=5. The introduction is written in a very abstract yet careless manner, without giving examples or referring to any concrete problem or model of computation. I found it difficult to follow and sometimes I was not even able to understand the logic behind the sequence of claims. As a result, the very motivation of why this particular approach makes sense in exploring distributed computability is not very convincing.,textcolor=red, todo: todoinline, author= R3 ,caption=5. The introduction is written in a very abstract yet careless manner, without giving examples or referring to any concrete problem or model of computation. I found it difficult to follow and sometimes I was not even able to understand the logic behind the sequence of claims. As a result, the very motivation of why this particular approach makes sense in exploring distributed computability is not very convincing.,textcolor=red, The introduction is written in a very abstract yet careless manner, without giving examples or referring to any concrete problem or model of computation. I found it difficult to follow and sometimes I was not even able to understand the logic behind the sequence of claims. As a result, the very motivation of why this particular approach makes sense in exploring distributed computability is not very convincing. todoinline, author=R3,caption=6. The choice of bibliography in the area of distributed computing is sometimes surprising, overlooking older original papers for some results and referring to scarcely related for others. There are some deceivingly imprecise and sometimes even wrong claims about classical results in distributed computing. In particular, the chronology of these results is not always presented correctly.,textcolor=red, todoinline, author=R3,caption=6. The choice of bibliography in the area of distributed computing is sometimes surprising, overlooking older original papers for some results and referring to scarcely related for others. There are some deceivingly imprecise and sometimes even wrong claims about classical results in distributed computing. In particular, the chronology of these results is not always presented correctly.,textcolor=red, todo: todoinline, author= R3 ,caption=6. The choice of bibliography in the area of distributed computing is sometimes surprising, overlooking older original papers for some results and referring to scarcely related for others. There are some deceivingly imprecise

Read the complete text