# A Sheaf-Theoretic Characterization of Tasks in Distributed Systems

Stephan Felber, Hugo Rincon Galeana, Bernardo Hummes Flores

<figure><img src="image_1.png" /></figure>

## To cite this version:

Stephan Felber, Hugo Rincon Galeana, Bernardo Hummes Flores. A Sheaf-Theoretic Characterization of Tasks in Distributed Systems. 2025. hal-05413868

HAL Id: hal-05413868

https://hal.science/hal-05413868v1

Preprint submitted on 12 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# A Sheaf-Theoretic Characterization of Tasks in Distributed Systems

Stephan Felber ✉️ ID

TU Wien, Vienna, Austria

Bernardo Hummes Flores ✉️ ID

École Polytechnique, Palaiseau, France

Hugo Rincon Galeana ✉️ ID

TU Berlin, Berlin, Germany

## Abstract

We introduce a sheaf-theoretic characterization of task solvability in general distributed computing models, unifying distinct approaches to message-passing models. Extending our brief announcement at SIROCCO'25, 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.

**2012 ACM Subject Classification** Theory of computation → Distributed computing models; Mathematics of computing

**Keywords and phrases** Task Solvability, Locality, Distributed computing, Sheaf Theory, Kripke Frame, Applied Category Theory, Cohomology Theory

## 1 Introduction

Assessing the solvability or impossibility of a given task in a distributed system is at the center of distributed systems research. A variety of theoretical tools have been developed by sourcing from different fields such as combinatorics, topology and epistemic logic. One of the earliest results is the two generals problem impossibility [2, 19], which roughly states that consensus is impossible in networks with message loss and unbounded delays. Numerous results have followed since: the celebrated FLP [11] impossibility shows that consensus cannot be achieved in asynchronous and crash-prone systems, the lossy-link impossibility [26] (the authors referred to it as mobile failures) that shows that consensus is impossible even in a synchronous two-process model if just one message may be lost in each round, [13] characterized consensus in distributed systems via epistemic logic and [23] provides a topological characterization of consensus under general message adversaries.

Although the aforementioned results are mostly related to problem solvability, they are specifically focused on consensus. Nevertheless, these results undoubtedly contributed to the development of frameworks that would later address general task solvability. Some such noteworthy results are Herlihy and Shavit's characterization of wait-free t-resilient shared memory distributed computation, via combinatorial topology [17], Attiya, Nowak and
Castañeda's characterization of terminating tasks [4], and Alcántara, Castañeda, Flores and Rajsbaum's characterization of look-compute-move wait-free robot tasks [3].

Sheaf theory originated from studying how local constraints give rise to global solutions, paired with cohomology theory as a measure of obstructions to such global constructions. Cellular sheaves were introduced by Curry [7] as a combinatorial counterpart to the common notion of sheaves found in the literature [20], with the interest of having a theory that is computable. Most importantly to us, the theory of cellular sheaves presents the concept of sheaves in an approachable manner, whence it becomes clear its usefulness to depict global properties of local information, as is the case for distributed computing. Sheaves have proven valuable in studying similar local-to-global phenomena, from opinion dynamics [14] to contextuality in quantum mechanics [1] and sensor integration [25, 18]. We now extend this framework to distributed systems.

In this paper, we extend the brief announcement [9] introducing a generic sheaf-theoretic
framework for analyzing task solvability parametrized by indistinguishability relations on
global states of the system, forming a graph-like structure. These indistinguishability graphs
are closely related to Kripke frames in epistemic logic, as explored in [8]. Furthermore,
our framework enables us to leverage the computational methods in cohomology theory
so to analyze task solvability, and even derive solving algorithms in systems where the
indistinguishability graph admits a cohomology group construction.

**Contributions** We introduce a novel sheaf-theoretic framework for analyzing distributed task solvability. Our approach complements the existing frameworks by connecting category theory with distributed computing. This novel bridge allows us to directly apply computational methods for decision function synthesis using linear algebra. We expect this first connection to provide fertile ground for more applications in distributed computing.

More precisely, we provide the following.

- A task sheaf construction (Theorem 17) that captures both the local knowledge of each process (local constraints) and relates it to valid solutions, assessing global consistency;

- A finite substructure of the executions that preserves the task solvability as system slices (Theorem 14);

- An equivalence between the existence of solutions to a task and the existence of sections over the corresponding system slice (Theorem 20);

- A way to use cohomology to transform impossibility arguments into computational problems (Theorem 26).

**Paper Organization** We start by defining the model of a distributed computing system we use in Section 2, giving special attention to the discrete structures used to depict the system executions (Section 2.1) and its tasks (Section 2.2). Section 3 introduces system slices, the smallest sufficient structure needed to assess task solvability, and how it brought to the categorical machinery. Section 4 defines the task sheaf, first by its explicit construction (Section 4.1), then by its equivalent categorical formulation (Section 4.2), so to state the main theorem relating the solvability of tasks to the existence of sections (Section 4.3). Section 5 uses the categorical machinery of task sheaves to define its cohomology construction, so used to computationally assess task solvability. Section 6 provides some concluding words.

## 2 System Model

We now define how processes evolve, communicate and make decisions, in order to define
the runs of that system. Our main contribution on task solvability *solely depends* on the
runs and the task specification and consequently our approach is applicable to any system
providing runs consisting of global states consisting of local states. As there are multiple approaches to modeling distributed systems, we do not formally specify how to obtain said runs, but exemplify it via a synchronous message passing system, which is one common choice to represent a distributed system (e.g., [24]).

We call *local protocols* processes $\Pi = \{p\}_{i \in [n]}$ which are deterministic state machines $P_p$ containing the possible **local states**, together with distinguished input states. The local protocol is defined by **transition function**, a **communication function** and a **decision function** $\delta_p$ mapping local states to task-specific outputs. Processes evolve depending on their previous local state and some partial information about other processes local states, usually represented via messages they received. The **possibilities** of (partial) information reception of the processes about the whole system state is captured as the **adversary**, also called the **message adversary** [26, 27, 28], **heard-of predicates** [6], **time-varying-graphs** [5], **scheduler** [22] etc., which influence the behavior of the system. Since there is a palette of different adversaries, each different in their way they impact the system, and the precise capabilities of the adversary *are not important in stating our results*, we do not formalize it further. The only object we need is a **run** consisting of a sequence of **configurations**, defined in what follows.

## 2.1 System Runs and System Frames

A **global configuration** $\langle g \rangle$ is a tuple of local states, one per process. A projection function $\pi_p : S^n \to S_{p_i}$ is defined as mapping configurations to local states. A projection to the inputs $\pi_I : S^n \to I^n$ is defined as retrieving the vector of input states, and accordingly they can be composed $\pi_{I_i} = \pi_{p_i} \circ \pi_I : S^n \to I_p$, projecting to $p_j$'s input. A configuration is called **terminal** if all processes' decision functions map to a valid output value. If this is true for some processes, but not all, then the configuration is called **partially terminated**. A decision function $\delta$ that always eventually provides a terminal configuration is called **terminating**. Additionally, we assume that the input values of a process are encoded into their local states and are not forgotten. A sequence of global configurations is an **execution** or a **run** of the system, we identify the **system** with the set of all of its runs, denoted $\Sigma$.

**► Example 1 (Synchronous message-passing system with lossy link adversary).** For example, the synchronous lossy link model for two processes $\Pi = \{a, b\}$ produces a system frame. Informally a synchronous message adversary evolves in synchronous rounds where processes compute a new state from the messages received in the previous round and the current state simultaneously. Messages sent at the beginning of one round either arrive at the end of that round, or are lost forever. The message adversary is allowed to drop at most one message in each round, implying that processes know that if they receive no message at the end of a round, then their own message arrived. Written differently, possible message arrival in each round may be indicated by an edge in $\{\leftarrow, \leftrightarrow, \rightarrow\}$, i.e., the no-arrow case is excluded. We assume that processes remember everything, i.e., they have unlimited memory to keep all their history and additionally, they transmit their whole history in every round (in the literature this is known as the full information protocol and mostly used for impossibility arguments, see for example [10] where they call it a full information algorithm).

It is well known that terminating consensus is already impossible here, for example Santoro and Widmayer proved it in [26].

We can now define execution graphs that do not depend on the system's decision functions.
<figure><img src="image_3.png" /><figcaption>■ **Figure 1** The first line counts the number of rounds. In the middle we depict the actual message reception, where an arrow from *a* to *b* indicates that *a*'s message to *b* arrived in that round. At the bottom we trace the resulting *global states* in that specific run. The first global state only contains the input values:1 for *a* and 0 for *b*. The second global state records the first and which messages arrived in the first round. The third global state records the second and which messages arrived in the second round and so on ...</figcaption></figure>

► **Definition 2** (Execution Graph). Let $\Sigma$ be a set of runs. The execution graph of $\Sigma$ is a directed graph $\mathcal{E}_{\Sigma} = (V(\mathcal{E}_{\Sigma}), E(\mathcal{E}_{\Sigma}))$ where:

$$V(\mathcal{E}_{\Sigma}) := \{\langle g \rangle \mid \exists \sigma \in \Sigma, \exists i \in \mathbb{N} \text{ such that } \sigma_i = \langle g \rangle\},$$

$$E(\mathcal{E}_{\Sigma}) := \{(\langle g \rangle, \langle h \rangle) \mid \exists \sigma \in \Sigma, \exists i \in \mathbb{N} \text{ such that } \sigma_i = \langle g \rangle, \sigma_{i+1} = \langle h \rangle\}.$$

The uniquely generated execution graph generated by the system $\Sigma$ is denoted $\mathcal{E}_{\Sigma}$.

From the system model established in Section 2, we formalize the requirement that the decision function must be deterministic. This takes the form of a system frame, where any set of configurations that constitute a run are equipped with process-wise indistinguishability relations. The system frame will later parametrize where, in the space of configurations, a decision function must behave constantly for lack of distinguishing power between identical states of the same process.

► **Definition 3** (Configuration Indistinguishability). Two configurations $\langle g \rangle$, $\langle h \rangle$ are indistinguishable for process $p$, denoted $\langle g \rangle \sim_p \langle h \rangle$, iff $p$ has the same local state in both $\langle g \rangle$ and $\langle h \rangle$, i.e., $\pi_p(\langle g \rangle) = \pi_p(\langle h \rangle)$.

Edges on the execution graph are also called **causal links**, as they arrange the configurations in a causal sequences that follows the execution of a possible run. An acyclic execution graph also induces a partial order $\leq$ over configurations, we write $\langle g \rangle \leq \langle h \rangle$ if there exists a path from $\langle g \rangle$ to $\langle h \rangle$.

We define now the system frame, which formalizes the information available to each process throughout the possible executions of the distributed system. This structure will be later used in Theorem 17, on the construction of the task sheaf, to make precise the idea that a process must always choose the same value when the information available to it is the same.

► **Definition 4** (System Frame). Let $\mathcal{E}_{\Sigma}$ be the execution graph generated by the set of runs $\Sigma$, and $\{\sim_p\}_{p \in \Pi}$ the set of indistinguishability relations on $V(\mathcal{E})$, indexed by each process $p \in \Pi$. We say that $\mathcal{K} := (V(\mathcal{E}), \{\sim_p\}_{p \in \Pi})$ is the **system frame** induced by $\Sigma$.

► **Remark 5** (Equivalence Relation on the System Frame). Note the indistinguishability relation on local states defines an equivalence relation.
See in Theorem 6 for the explicit construction of a system frame after one step.

**► Example 6.** A system frame after zero and one step corresponding in the lossy-link synchronous message adversary from the previous example is shown in Figure 2. The frame after zero steps could be written as $V(\mathcal{E}_{LL}) = \{(0,0), (0,1), (1,0), (1,1)\}$ and $\sim_a = \{((0,0), (0,1)), ((1,0), (1,1))\}$, $\sim_b = \{((0,0), (1,0)), ((0,1), (1,1))\}$. This is the finest execution graph possible under the lossy-link adversary. Dotted arrows are the causal links. The colored edges denote the indistinguishability edges between configurations, orange for $a$, green for $b$. The nodes here represent the configurations: for example, after the first step, $a$ cannot distinguish between $(0, 0 \to)$ from $(0, 1 \to)$ as $a$ hasn't received a message in neither configuration, whereas $b$ can distinguish the two configurations because it has a different inputs in them.

<figure><img src="image_4.png" /><figcaption>Figure 2 Depiction of the system frame up to step 1 of the lossy-link synchronous message adversary together with a full-information protocol. This system frame grows to the right.</figcaption></figure>

An example for the causality relation would be the configuration $(0, 0 \leftrightarrow)$ depending on the configuration $(0, 0)$, written as $(0, 0) \le (0, 0 \leftrightarrow)$.

## 2.2 Distributed Tasks and their Algebraic Structure

Given a system, we can now talk about the distributed tasks for which we will provide a sheaf-theoretic perspective.

**► Definition 7 (Tasks).** A task is a triple $T = (\mathcal{I}, \mathcal{O}, \Delta)$, where $\mathcal{I}$ is the set of possible input vectors, $\mathcal{O}$ is the set of possible output vectors and $\Delta: \mathcal{I} \to 2^\mathcal{O}$ is a map associating to each input vector the set of valid output vectors. $I_p, O_p$ denote the possible inputs and outputs restricted to a process $p$.

**► Definition 8 (Terminating Task Solvability).** A decision function $\delta_i$ is said to solve a task $T$ if for every run $\sigma = (\langle g \rangle)_{t \in \mathbb{N}} \in \Sigma$ the following holds:

- **Termination:** For every process $p_j \in P_i$, there is a step $t \in \mathbb{N}$ such that $\delta(\pi_j(\langle g \rangle_t)) \neq \perp$,

- **Validity:** There is an output vector $o \in \Delta(\pi_I(\langle g \rangle))$, such that for every process $p_j \in P_i$ there is a step $t \in \mathbb{N}$ where $\delta(\pi_j(\langle g \rangle_t)) = o_p$ and for every $t' \le t$, $\delta(\pi_j(\langle g \rangle_{t'})) = \perp$.

Termination requires every process to eventually decide on some value, and validity requires that all individual decisions correspond to a valid output configuration for the
respective input configuration. Note that the decision of process $p$ corresponds to the first value obtained by its decision function other than $\perp$.

The topological approach to distributed computing [16] provides a combinatorial structure for defining tasks as simplicial complexes. Recall that a **chromatic simplicial complex** is a set of vertices and a set of simplices defined from the vertices: a subset of the powerset of vertices that is closed under inclusion. Each vertex has a color, the process identity, and each face can depict at most one instance of each color. Vertices are local states and faces are then global states.

The sets of input $\mathcal{I}$ and output $\mathcal{O}$ values are now chromatic simplicial complexes, and the task specification $\Delta: \mathcal{I} \to 2^{\mathcal{O}}$ works the same, and a task consists of a relation between valid outputs simplices for a given set of inputs simplices. This formulation captures the combinatorial nature of a task specification. It which will be later used in Section 4 as the data of the task that must be tracked by the processes.

## 3 From System Frames to Categories

Termination on an execution graph can be represented as a set of configurations that **cuts** the execution graph in half. Indeed, termination by definition is just a set of configurations that intersects any run, together with some extra conditions that we will define in the following. Unfortunately, not every such cut through the execution graph need be finite and therefore easy to find. Thus we do not concern ourselves with how we look for one, instead describe its shape.

**Definition 9 (Execution Cut).** Let $A \subset V(\mathcal{E})$ be a set of configurations. We say that $A$ is an **execution cut** iff it is a cut set in $\mathcal{E}$, i.e., it intersects every run in $\mathcal{E}$.

An execution cut represents a set of “unavoidable” configurations within the system. Furthermore, we say that an execution cut $A \subset V(\mathcal{E})$ is **terminal** iff any $U \in A$ is terminal, i.e., at configuration $U$, all processes must have decided.

**Definition 10 (Local Star).** Let $\langle g \rangle \in V(\mathcal{E})$ be a configuration, $p \in \Pi$, and $N_p(\langle g \rangle) := \{\langle h \rangle \in V(\mathcal{E}) | \langle g \rangle \sim_p \langle h \rangle\}$. That is, $N_p(\langle g \rangle)$ is the equivalence class of $\langle g \rangle$ under $\sim_p$. We define the **local star** of $\langle g \rangle$, denoted by $\mathcal{N}(\langle g \rangle)$, as the labeled graph obtained by $\bigcup_{p \in \Pi} N_p(\langle g \rangle)$ and extend it over sets by $\mathcal{N}(A) = \bigcup_{\langle g \rangle \in A} \mathcal{N}(\langle g \rangle)$

**Remark 11.** Note that for any $p \in \Pi$, $N_p(\langle g \rangle)$ induces a complete graph with all edges labeled by $p$.

**Definition 12 (Causal Closure).** Let $A$ be a terminal execution cut and $\mathcal{N}(A)$ its local star. The causal closure $ccl()$ contains all configurations that lie between $\mathcal{N}(A)$ and $A$:

$$ccl(\mathcal{N}(A)) = \{\langle g \rangle \in A | \exists \langle h \rangle \in \mathcal{N}(A), \exists \langle w \rangle \in A, \langle h \rangle \le \langle g \rangle \le \langle w \rangle\}$$

A **causal closure** $ccl(\mathcal{N}(A))$ of a terminal execution cut $A$ extends to the partially terminated configurations in $\mathcal{N}(A) \setminus A$, where at least one process $p$ has already terminated, but not necessarily all of them. Any partially terminated configuration $\langle g \rangle$ eventually results into a terminated configuration $\langle h \rangle$ in $A$. The causal closure contains all successors of partially terminated configurations up until they result in a fully terminated configuration in $A$. As some processes have already decided in a partially terminated configuration $\langle g \rangle$, we ensure that they keep their decided values in any successor configurations $\langle h \rangle$ (reflecting that decisions are final) by constructing the **causal consistency** $\{\simeq_p\}_{p \in \Pi}$ relation such that $\langle g \rangle \simeq_p \langle h \rangle$.
**► Definition 13 (Causal Consistency Relation).** We define the causal consistency relation $\{\simeq_p\}_{p \in \Pi}$ as the symmetric closure of the binary relation composition $\leq \circ \sim_p$.

Intuitively, given a causal closure of a terminal execution cut $ccl(\mathcal{N}(A))$, the causal consistency relation relates all configurations where a process terminated in a **preceding** or **indistinguishable** configuration. As $\leq$ and $\{\sim_p\}_{p \in \Pi}$ are reflexive, $\{\simeq_p\}_{p \in \Pi}$ is reflexive, and contains both relations $\leq$ and $\{\sim_p\}_{p \in \Pi}$. Observe that any causally dependent configurations in $\langle g \rangle$, $\langle h \rangle \in A$ such that $\langle g \rangle \leq \langle h \rangle$ are related $\langle g \rangle \simeq \langle h \rangle$ (and also $\langle h \rangle \simeq \langle g \rangle$) for all processes. Configurations $\langle g \rangle$ in $ccl(\mathcal{N}(A))$ that are not in $A$, are related to a configuration $\langle h \rangle$ in $A$ via the indistinguishability relation of $p$ and any successor of $\langle g \rangle$ is also related to $\langle h \rangle$ for $p$. This ensures that the partially terminated process $p$ keeps its terminated value.

**► Definition 14 (System Slice).** Let $A \subset V(\mathcal{E})$ be an execution cut in the system frame $\mathcal{K}$, we define a **system slice**, denoted by $S_A = (C, \{\simeq_p\}_{p \in \Pi})$, as a tuple consisting of the causal closure over the local star over $A$, i.e., $C = ccl(\mathcal{N}(A))$, together with its **causal consistency relation**.

In general system slices need not be finite, see Theorem 15 for an explicit construction of an execution graph with a necessarily infinite system slice. A finite system slice is depicted in Theorem 21.

**► Example 15 (System slice of single shot message adversary execution).** In this example, we consider the **tilted consensus task**, where both processes have to decide on $a$'s value. The synchronous communication adversary here allows exactly one message from $a$ to $b$ per run, the set of all runs therefore consists of all $\sigma_k = - \rightarrow^k -^\omega$, where $k < \infty$. In Figure 3 $a$'s indistinguishability relations between configurations are again orange, $b$'s are blue. The configurations within dashed boxes are terminated, the yellow boxes are partially terminated. The dashed red and blue edges represent the causal consistency relation (most transitive edges are omitted favoring readability).

<figure><img src="image_5.png" /><figcaption>■ **Figure 3** Depiction of the tilted consensus task, the configurations in neither dashed box are partially terminated. The system slice consists of all the infinitely many configurations in either of the dashed boxes. We exemplify here that system slices may necessarily be **infinite**, as there is no finite system slice with a **section**, as any configuration on the left has to decide 0 and can thus not be in the connected to any configuration on the right. We formalize this in Section 4. This system frame grows upwards.</figcaption></figure>
Clearly, *b* just waits until something arrives, whereas *a* can terminate immediately. As *b* cannot distinguish whether it will end up in the 0 or 1 deciding half until it receives that message (i.e. *b* doesn't know *a*'s value), no configuration *U* where no message has arrived yet can be terminal. At the same time, every configuration *U* is partially terminated as it is indistinguishable for *a* from a terminal configuration (marked in the dashed terminal regions). The smallest system slice therefore has infinite size in this execution graph.

System slices naturally form a graph structure where we can define sheaves, where the set of global configurations are its vertices and the causal consistency relations its edges. This suffices for our purposes, but note that this consists of the more general structure of a **cellular complex**, where vertices and edges are 0 and 1 cells, and the execution structure naturally satisfies its local finite requirement. Cellular complexes are fundamental objects in algebraic topology, and a full account can be found in [15]. Most importantly, a cellular complex *X* has an underlying partial ordering of its cells (vertices and edges), denoted *P*<sub>*X*</sub>, which we exemplify now.

Finally, in order to access the categorical machinery needed to define the task sheaves, we need to introduce the concept of a **cellular category** [21], which categorifies the cellular complex *X*. By viewing its associated poset *P*<sub>*X*</sub> as a category, which preserves the topological structure while enabling a categorical perspective better suited for defining sheaves.

**Example 16 (Undirected Graph).** An undirected graph $G = (V, E)$, with $V$ a collection of vertices and $E$ a collection of edges, gives rise to a cellular category **Cell**(*G*). Note that the data of an edge $v_1 \stackrel{e}{\leftrightarrow} v_2$ consists of an unordered pair of vertices $\{v_1, v_2\}$, and the incidence relation of an edge to a vertex satisfies the inclusion $v_1 \hookrightarrow \{v_1, v_2\} = e$. With this in mind, **Cell**(*G*) is obtained by constructing an object for each vertex $v \in V$ and for each pair of vertices $e \in E$, with an arrow $v \to e$ whenever $v \hookrightarrow e$. Objects obtained from vertices are called 0-cells and those obtained from edges are called 1-cells. This construction preserves the information of the graph, while adding a categorical structure.

Observe that any system slice is an undirected graph and therefore induces a cellular category. We will make ample use of this in the following.

# 4 Task Sheaves

In this section, we introduce the task sheaf as a mathematical framework for encoding the solvability constraints of a distributed task. Sheaves provide a formalism that captures both the global structure of a task definition and the local constraints which protocols must respect. We present two equivalent formulations. First, an explicit construction, used to build the intuition over the running examples. Then, we present its categorical foundations, which enables the use of cohomology later in Section 5. We then state the main theorem relating the solvability of a task to the existence of sections in the appropriate task sheaf.

## 4.1 The Task Sheaf

Sheaves can be informally understood as a structure allowing to track data that is associated to pieces of a space. In our case, we will be tracking the task data, the possible solutions according to the task specification, across the possible global states that our distributed system may assume. As such, the runs of the system being analyzed will provide us with our base space: a *system slice* $\mathcal{S}$, derived from its system frame $\mathcal{K}$, turned into a cellular category **Cell**($\mathcal{S}$), as seen in Section 3.
A sheaf defined on a cellular category is a cellular sheaf <fnref n="1" />. A key characteristic of cellular sheaves is the combinatorial nature of this space, which allows us to look at discrete structures and their generalizations to higher dimensions, such as the graphs and cellular complexes. This nature also gives us access to a much simpler theory. In full generality, sheaves must be shown to respect a technical sheaf condition, which is automatically satisfied in the case of cellular sheaves, as proven in [7, Theorem 4.2.10].

In a distributed system, configurations represent snapshots of the global state, while indistinguishability relations capture what each process can observe locally. The task specification defines which outputs are valid for given inputs. We introduce now the construction of a sheaf task, that connects those concepts and allows us to reason about task solvability.

**► Definition 17 (Task Sheaf).** Let $\mathcal{S} = (C, \{\simeq_p\}_{p \in \Pi})$ be a system slice obtained of set of runs $\Sigma$, and let $T = \langle \mathcal{I}, \mathcal{O}, \Delta \rangle$ be a task. The **task sheaf** $\mathcal{F}_{\mathcal{S},T}$ is a cellular sheaf defined as follows.

1. **(stalks of configurations)** For each configuration $\langle g \rangle \in \mathcal{S}$, the stalk is $\mathcal{F}_{\mathcal{S},T}(\langle g \rangle) = \Delta(\pi_I(\langle g \rangle))$, i.e., the set of possible valid output configurations given the input assignments in $\langle g \rangle$.

2. **(stalks of relations)** For each edge $(\langle g \rangle, \langle h \rangle)_p \in \simeq_p$ between configurations $\langle g \rangle$ and $\langle h \rangle$ for process $p$, the stalk is $\mathcal{F}_{\mathcal{S},T}((\langle g \rangle, \langle h \rangle)_p) = \{\pi_p(x) \mid x \in \mathcal{F}_{\mathcal{S},T}(\langle g \rangle) \cup \mathcal{F}_{\mathcal{S},T}(\langle h \rangle)\}$, i.e., the set of possible values that process $p$ can choose in either of the adjacent configurations.

3. **(restriction maps)** The restriction map from a configuration $\langle g \rangle$ to an edge $(\langle g \rangle, \langle h \rangle)_p$ is $\mathcal{F}_{\mathcal{S},T,\langle g \rangle} \subseteq (\langle g \rangle, \langle h \rangle)_p = \pi_p$, i.e., it projects an output configuration to its p'th entry.

The vertices of $\mathcal{F}_{\mathcal{S},T}$ are configurations, while the edges in $\simeq_p$ connect configurations where $p$ should have the same decision value.

**► Example 18 (Task sheaf after one iterations).** In Figure 4 we depict a cellular category (note, that it is also the system frame of the lossy link synchronous message adversary) with objects representing the possible task solving outputs. Indistinguishability edges are also

<figure><img src="image_6.png" /><figcaption>■ **Figure 4** Depiction of the system frame consisting of all configurations after one step of the lossy-link synchronous message adversary annotated with the binary consensus task stalks. For example when both inputs are 0, then the stalk is a singleton containing just the decision vector $\begin{pmatrix} 0 \\ 0 \end{pmatrix}$.</figcaption></figure>

assigned objects (in our case simply the union of both adjacent vertices' objects, i.e., all

<footnote n="1">¹ See [7] for a thorough treatment of cellular sheaves, and [20] for an overview of sheaf theory.</footnote>
possible task outputs of the specific agent that cannot distinguish both configurations) and are omitted for space except at two edges. The restriction maps go from vertices to edges and map the global task output to the non-distinguishing agents output.

This explicit construction captures the constraints imposed by the task on the decisions of the processes. In order to establish its mathematical properties, we provide now its equivalent formulation as a colimit of task sheaves defines for each process.

## 4.2 Categorical foundations

The task sheaf has an equivalent process-wise formulation using the chromatic semi-simplicial sets (csets) as data modeling the distributed tasks. Csets were introduced by Goubault et al. [12], and can be understood as sets of output values with enough structure to represent labeled configurations, a categorical generalization of the simplicial complexes used in Theorem 7.

For each process $p \in \Pi$, a sheaf $\mathcal{F}_{S,T}: \mathbf{Cell}(S) \to \mathbf{CSet}_{\Pi}$ is defined. Whenever the system slice $S$ and the task $T$ are clear from the context, we will write $\mathcal{F}$ and $\mathcal{F}_p$. $\mathcal{F}_p$ has the following structure:

- **Cell(S)** is the cellular category obtained by localizing the system slice $S$ to process $p$, i.e., from the poset $P_p$ induced by $\simeq_p$ over $C$. Note that a pair of configurations $(\langle g \rangle, \langle h \rangle) \in \simeq_p$ induces the relations $\langle g \rangle \preceq (\langle g \rangle, \langle h \rangle)$ and $\langle h \rangle \preceq (\langle g \rangle, \langle h \rangle)$.

- **CSet$_\Pi$** is the category of chromatic semi-simplicial sets.

In this formalism, configurations $\langle g \rangle$ become 0-cells and equivalence causal consistency become 1-cells. The sheaf $\mathcal{F}_p$ maps a set of configurations to the set of $n$-simplices $\Delta_n$ corresponding to its acceptable outputs, according to the task specification $T$, and maps an inclusion of configurations $\langle g \rangle \hookrightarrow (\langle g \rangle, \langle h \rangle)$ to face maps $\mathcal{F}_{\langle g \rangle} \preceq_{(\langle g \rangle, \langle h \rangle)} \mathcal{F}_{\Delta_n} \to \mathcal{F}_{\Delta_1}$, where a set of output decisions is sent to decisions process-wise, i.e. its $p$th colored faces, such that the following diagram commutes.

<figure><img src="image_7.png" /></figure>

The sheaves defined for all agents $\{\mathcal{F}_p\}_{p_i \in \Pi}$ are a set of functors with common codomain.

<figure><img src="image_8.png" /></figure>

These form a subcategory of the category of cellular sheaves, where each object is a cellular sheaf $\mathcal{F}: \mathbf{C}_p \to \mathbf{D}$ and morphisms are commutative squares

<figure><img src="image_9.png" /></figure>
where only all sheaves have a common codomain. The colimit of such cellular categories is well behaved and can be lifted for a colimit of cellular sheaves under those assumptions. The colimit of {$\mathcal{F}_p$}$_{p\in\Pi}$ then gives us a sheaf $\mathcal{F}$ that captures all of the information on the individual sheaves, where a global section exists iff there is a global section on the individual ones. The sheaf $\mathcal{F}$ is defined over each configuration $\langle g \rangle$ (resp. indistinguishability edge $(\langle g \rangle, \langle h \rangle)$) as the colimit of the individual sheaves localized at $\langle g \rangle$ (resp. $(\langle g \rangle, \langle h \rangle)$). The sheaf $\mathcal{F}$ coincides with the explicit definition given in Theorem 17.

The colimit of {$\mathcal{F}_p$}$_{p\in\Pi}$ coincides with the task sheaf $\mathcal{F}$ from Theorem 17. This categorical perspective ensures our construction is well-founded and enables the cohomology computations in Section 5.

## 4.3 Solvability as Sections

We now define sections, which capture globally consistent assignments of data across the cellular complex. They are a fundamental concept in sheaf theory and will complete the language needed for our analysis of distributed task solvability.

**► Definition 19 (Section).** Let $\mathcal{F}: \text{Cell}(P_X) \to \mathbf{D}$ be a cellular sheaf over $(X, P_X)$. A section of $\mathcal{F}$ is a choice of elements $s = \{s_\alpha \in \mathcal{F}(\alpha) \mid \alpha \in \text{Cell}(P_X)\}$ such that for every pair of cells with $\alpha \sqsubseteq \beta$ the values coincide through restriction maps, i.e., $\mathcal{F}_{\alpha \sqsubseteq \beta}(s_\beta) = s_\alpha$. The set of all global sections of $\mathcal{F}$ is denoted by $\Gamma(X, \mathcal{F})$.

A section is a choice of values, one per cell, such that the same value is obtained if we restrict to a cell from each of its incident neighbors. In the case of a task sheaf, it is a choice of data (i.e, output value) for each vertex (i.e, configuration) and each edge (i.e, causal consistency relation) such that they all agree under the restriction maps. Explicitly, it is an element of the direct sum of the stalks:

$$ \Gamma(\mathcal{F}; S) = \left( \bigoplus_{c \in C} \mathcal{F}_{S,T}(c) \right) \times \left( \bigoplus_{(c,c') \in \{\simeq\} \{p \in \Pi\}} \mathcal{F}_{S,T}((c, c')) \right). $$

We can now state our main characterization theorem, which establishes that task solvability is equivalent to the existence of sections in our task sheaf.

**► Theorem 20 (Terminating Task Solvability).** Let $T = \langle \mathcal{I}, \mathcal{O}, \Delta \rangle$ be a task and $\Sigma$ a system: there exists a terminating decision map $\delta$ solving $T$ iff there exists a execution cut $A$ such that its system slice, ccl($\mathcal{N}(A)$), together with it causal consistency relation {$\simeq_p$}$_{p\in\Pi}$, has a section over the task sheaf $\mathcal{F}_{A,\simeq}$.

**Proof.** Let us assume first that $\delta$, solves $T$. Therefore, for any run $\sigma$, there exists a configuration $\langle g \rangle_\sigma$ that is the earliest configuration of $\sigma$ where each process has decided $\delta(\langle g \rangle) \neq \perp$. Note that $A = \{\langle g \rangle_\sigma \mid \sigma \in \Sigma\}$ is a system cut.

Consider the system slice ccl($\mathcal{N}(A)$). By assumption $\delta_p$ assigns a $T$ solving, non-$\perp$ value to every configuration $\langle g \rangle \in ccl(\mathcal{N}(A))$, and satisfies Item 1, Item 3 and Item 2 making $\mathcal{F}_{A,\simeq}$ a sheaf. The section condition in Theorem 19 is satisfied as decisions are final, i.e., any successor configuration of a terminated configuration has the same decision, and $\delta_p$ is a function on local states, i.e., configurations $p$ cannot distinguish are mapped identically by $\delta_p$.

Now to prove the converse, assume that there exists an execution cut $A$ such that its system slice, ccl($\mathcal{N}(A)$), has a section $S$. We construct a terminating decision map by setting

$$ \delta_p(\pi_p(\langle g \rangle)) = \begin{cases} S(\phi(A, \langle h \rangle)) & \text{for any } \langle h \rangle \text{ where } \pi_p(\langle h \rangle) = \pi_p(\langle g \rangle) \text{ and } \langle h \rangle \in A \\ \perp & \text{else.} \end{cases} $$
Clearly $\delta_p$ terminates because $A$ is an execution cut and satisfies Theorem 8. $\delta_p$ solves $T$ because first, the only vectors in the stalks over the configurations are task solving vectors. And second, $\delta_p$ is well-behaved and maps identical inputs to identical outputs by Item 3 and the section condition in Theorem 19, i.e, per-processes outputs need to agree over indistinguishable configurations.

◀

See the following Theorem 21 for an application of Theorem 20.

**► Example 21 (Consensus on Task Sheaf).** In Figure 5 we depict a section over a task sheaf defined on a system slice. The vectors over the configurations in the system slice correspond to the valid choice of data that the sheaf took. Restriction maps and stalks are not depicted.

<figure><img src="image_10.png" /><figcaption>■ **Figure 5** We again consider the lossy link synchronous message adversary together with the epsilon agreement task. The configurations within the dashed polygon constitute a system slice solving the $\epsilon = 0.5$ agreement task in the case where the only allowed inputs are (0, 1) or (1, 2). The solid colored lines represent indistinguishabilities, the dashed lines represent the causal consistency relation. The system grows upwards.</figcaption></figure>

Now that we have characterized solvability of a task $T$ under a protocol $\mathcal{P}$ in terms of its task sheaf, $\mathcal{F}_{A,\simeq}$, we will also establish a relation between local cohomology of the task sheaf and the task solvability.

## 5 Computing Solutions

Given a communication adversary $K$ representing some adversarial entity together with a task $T$, we search for a protocol together with a decision map. As the full-information protocol provides the finest possible execution tree, its natural to start the search process there. Slices that are finite in size can be recursively enumerated and, although that's computationally inefficient, tested. If we find a finite slice $A$ that allows for a terminal decision map we can try to optimize the protocol inducing the execution tree. If we do not find a slice, but keep looking forever, then a finite slice does not exist and the task is not wait-free solvable, although it might be solvable given an **infinite slice**.

In this section we focus on wait-free solvability, so assume we have found a finite terminating slice $ccl(\mathcal{N}(A))$, we computationally determine the space of all sections and therefore the decision map $\delta$. We do this via *cohomology*, i.e., we turn our structure into an abelian group and extract from it all possible solutions.

Given a task sheaf $\mathcal{F}$, the process of obtaining the $n$th sheaf cohomology can be understood as an iteration of the following steps.

$$ H^n(\mathcal{F}) : \mathrm{Cell}(X) \xrightarrow{\mathcal{F}} \mathrm{CSet}_{\Pi} \xrightarrow{\mathbb{Z}} \mathrm{sAb} \xrightarrow{\delta^n} \mathrm{Ch}_{\mathbb{Z}} \xrightarrow{H^n} \mathrm{Ab} $$
Where sAb is the category of simplicial abelian groups, Ch$_{Z}$ is the category of (co)chain complexes with integer coefficients and Ab the category of Abelian groups, where our cohomology lives.

We provide a brief explanation, and illustrate it below in Theorem 25. Given a cset O containing the possible system output states, we can obtain a simplicial abelian group through the left adjoint of the forgetful functor that sends it to the underlying simplicial set<fnref n="2" />. The third map gets us a cochain complex with differentials defined from the alternating sum of the (co)face maps. Finally, we obtain the n-th cohomology group, which corresponds to a space of sections of our sheaf. This construction is well known in the literature of algebraic topology [15] and we adapt it as a tool for understanding distributed tasks.

**► Definition 22 (Space of Zero- and One- Cochains).** *Resembling Theorem 19, we define*

$$C^0(\mathcal{K}; \mathcal{F}) = \bigoplus_{v \in V(\mathcal{K})} \mathcal{F}(v)$$

as the space of zero cochains of the sheaf $\mathcal{F}$, i.e., the vector space of all possible assignments to vertices (configurations) in $\mathcal{F}$. Similarly

$$C^1(\mathcal{K}; \mathcal{F}) = \bigoplus_{e_p \in E(\mathcal{K})} \mathcal{F}(e_p)$$

is the space one one cochains, i.e., the space over possible output choices for processors.

The two cochain groups are connected via a linear coboundary map $\delta$. This maps a specific choice of output vectors to the individual choices along the indistinguishability edges defined by the restriction maps. To define $\delta$ we chose an arbitrary direction on each indistinguishability edge $e = \langle g \rangle \to \langle h \rangle$ just to facilitate an algebraic representation.

**► Definition 23 (Coboundary Map).** *We denote by $d: C^0 \to C^1$ the coboundary map, defined per edge $e = (\langle g \rangle, \langle h \rangle)_p$ in the sheaf as:*

$$d(x)_{e_p} = (\langle g \rangle, \langle h \rangle)_p = \pi_p(x_{\langle h \rangle}) - \pi_p(x_{\langle g \rangle}),$$

where we assume that the chosen direction goes from $\langle g \rangle \to \langle h \rangle$.

We can represent the coboundary map $d$ as a coboundary matrix $D$ where rows are indexed by edges and columns are indexed by configurations:

$$D_{\langle g \rangle, e = (\langle h \rangle, \langle h' \rangle)_{p_j}} = \begin{cases} d(e) & \text{if } \langle h \rangle = \langle g \rangle \text{ or } \langle h \rangle' = \langle g \rangle \\ 0 & \text{otherwise.} \end{cases}$$

One can think of $D$ simply as computing the difference between two indistinguishable configurations. A section on our sheaf is a 0-cochain that is mapped to 0 by $d$, so any assignment to configurations such that any process that cannot distinguish two configurations, decides the same thing. The set of all sections is then the kernel $ker(D)$.

**► Definition 24 (Zeroth Cohomology).** *The zero-th cohomology is $ker(D)$, i. e., the kernel of the coboundary map.*

<footnote n="2">² Here chromatic semi-simplicial sets are treated as simplicial sets for simplicity, as they only add the process labeling that would require extra bookkeeping.</footnote>
**► Example 25.** Let us consider the approximate agreement problem for 2 processes in the lossy link synchronous message adversary setting, illustrated in Figure 6. We are interested in whether given a full information protocol, the induced system execution graph allows for a terminal execution cut, such that by Theorem 20 we can find a section that gives us a decision map.

We set the possible input vectors to $I = \{(0), (1), (0), (1)\}$, the possible output vectors to $O = \{(x) | x, y \in \{0, 0.25, 0.5, 0.75, 1\}\}$ and define the validity map as

$$ \Delta(\begin{pmatrix} x \\ y \end{pmatrix}) = \begin{cases} (0) & \text{when } x = y = 0 \\ (1) & \text{when } x = y = 1 \\ O & \text{otherwise.} \end{cases} $$

Intuitively, in the initial configuration we cannot find a section, since both configurations, (0,0) and (1,1), force the respective connecting configurations (0,1) and (1,0) to choose an output vector that projects to 1 and 0, which does not exist in $O$. We can formalize this impossibility starting with the co-boundary matrix $D^0$, where we number the configurations by the initial values interpreted in binary, and edges are just tuples of configurations, with the direction following the written order. Note that this is the co-boundary matrix of the system slice consisting of all **initial configurations**, i.e., after 0 steps. The co-boundary matrix for all configurations after one step has the unreadable dimensions of $12 \times 12$.

$$ D^0 = \begin{pmatrix} 0 & 1 & 2 & 3 \\ -\pi_a(\cdot) & \pi_a(\cdot) & & \\ -\pi_b(\cdot) & & \pi_b(\cdot) & \\ \pi_a(\cdot) & & -\pi_a(\cdot) & \\ \pi_b(\cdot) & & & \pi_b(\cdot) \end{pmatrix} $$

In order to find the kernel of $D^0$, we can assume some arbitrary assignment vector to the configurations $x = ((0), x_1, x_2, (1))^T$ (as the configurations 1 and 3 have only one possible choice by validity) and solve $D^0 x = 0$:

$$ D^0 x = \begin{pmatrix} -0^a + x_1^a \\ -x_1^b + 1^b \\ x_2^a - 1^a \\ 0^b - x_2^b \end{pmatrix} \implies \begin{array}{l} x_1^a = 0^a, \\ x_1^b = 1^b, \\ x_2^a = 1^a, \\ x_2^b = 0^b \end{array} \implies x_1 = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \text{ and } x_2 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}. $$

This proves that epsilon agreement is impossible in 0 steps as the required solutions $x_1$ and $x_2$ are not possible solutions, the kernel is trivial. The impossibility itself does not come as a surprise. The novelty lies in the fact that that every step we took was purely deterministic and computable, meaning that such operations could have been done by a program.

We depict the system slice consisting of all configurations after **one step** in Figure 6. $(1, 1 \to)$ forces $(1, 0 \to)$ to choose an output that matches $a$'s decision, i.e., $(\frac{1}{75})$. This forces $b$'s decision in $(1, 0 \leftrightarrow)$ to be .75 a valid output could be $(\frac{.75}{.5})$. Again, this forces $a$'s hand in $(1, 0 \leftrightarrow)$ to .5, we could choose $(\frac{.5}{.25})$ here. But now we run into trouble, in configuration $(0, 0 \leftrightarrow)$ we cannot find an output vector that maps $b$'s value to .25 as the only possible choice here is $(\frac{0}{0})!$ Therefore this assignment is not a section!

Note that this example is not a proof that one cannot solve approximate agreement after one step, and is only meant to illustrate the role of cohomology in determining task solvability, as the co-boundary matrix after one step is already huge. But, as already illustrated, any step here is deterministic and computable, therefore we can find a section after two steps, implying the existence of a protocol solving epsilon agreement.
<figure><img src="image_11.png" /><figcaption>Figure 6 An example of the approximate agreement task (with $\epsilon = 0.25$) in the lossy-link synchronous communication adversary, as in Theorem 6. The system slice consists again of all configurations after **one round**, we depict a possible assignment of task solving vectors to the configurations. Starting from $(1, 1 \to)$ we then draw all the restriction maps and the following derived vectors until we arrive at an assignment where the restriction maps do not agree. Essentially this just shows that, this assignment is not a section.</figcaption></figure>

We formalize this intuition in Theorem 26.

**Theorem 26 (Computable Decision Maps).** Let $T$ be a task that can be solved in a finite system slice (i. e. finitely many terminal configurations) in a given execution graph $\mathcal{E}$, then its decision map is computable in finite time.

The idea is simple: compute the execution graph $\mathcal{E}$ layer by layer and check whether any system slice admits a non-trivial zeroth cohomology.

**Proof.** Assume the task $T$ can be solved in a finite system slice. We can iteratively build up the tree $\mathcal{E}(k)^3$, up to some $k$. For each $k$, chose any possible $A$ and corresponding system slice $ccl(\mathcal{N}(A)) \subseteq ccl(\mathcal{N}(A))$ and compute its zeroth cohomology. If it admits a non-trivial kernel on $ccl(\mathcal{N}(A))$, then derive a protocol as described in Theorem 20.

By assumption such a $\mathcal{N}(A)$ exists. By building the tree iteratively, eventually this $A$ will be found and the iterations terminates.

# 6 Conclusions

Our results, and in particular, our task sheaf construction, constitutes to the best of our knowledge, the first sheaf-theoretic characterization of general distributed computing tasks. Moreover, the generality of our model allows us to describe a wide range of systems that only need to satisfy minimal assumptions, namely, that the set of processes is finite, and that the communication is produced via messages.

By expressing tasks as a sheaf, we are able to incorporate cohomology theory as a powerful tool for distributed systems. For instance, the cohomology of a task sheaf is a group that represents the “obstructions” or “limitations” in the distributed system that prevent a specific task to be solved. Moreover, we show an impossibility result by simply looking at the cohomology group of its task sheaf. However, the cohomology of a task sheaf is not only restricted to determining impossibilities, but it may also be used for explicitly finding a protocol. Thus, sheaf-cohomology is shown to be a powerful, and promising tool for obtaining novel results and insights in distributed computing.

<footnote n="3">³ As any configuration has at most finitely directly causally dependent configurations, i. e., children in the execution graph, we can label any node by its depth. Then we iteratively build the tree up to depth $n$.</footnote>
Finally, the rigorous categorical foundation of our approach provides a solid starting point for further research, such as incorporating failure models or exploring the complexity of protocol synthesis for different task definitions.

References

1 Samson Abramsky and Adam Brandenburger. The sheaf-theoretic structure of non-locality and contextuality. *New Journal of Physics*, 13(11):113036, 2011. doi:10.1088/1367-2630/13/11/113036.

2 E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber. Some constraints and tradeoffs in the design of network communications. In *SOSP '75: Proceedings of the fifth ACM symposium on Operating systems principles*, pages 67–74, New York, NY, USA, 1975. ACM. doi:http://doi.acm.org/10.1145/800213.806523.

3 Manuel Alcántara, Armando Castañeda, David Flores-Peñaloza, and Sergio Rajsbaum. The topology of look-compute-move robot wait-free algorithms with hard termination. *Distrib. Comput.*, 32(3):235255, June 2019. doi:10.1007/s00446-018-0345-3.

4 Hagit Attiya, Armando Castañeda, and Thomas Nowak. Topological Characterization of Task Solvability in General Models of Computation. In Rotem Oshman, editor, *37th International Symposium on Distributed Computing (DISC 2023)*, volume 281 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 5:1–5:21, Dagstuhl, Germany, 2023. Schloss Dagstuhl Leibniz-Zentrum für Informatik. ISSN: 1868-8969. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.5, doi:10.4230/LIPIcs.DISC.2023.5.

5 Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. *International Journal of Parallel, Emergent and Distributed Systems*, 27(5):387–408, 2012. arXiv:https://doi.org/10.1080/17445760.2012.668546, doi:10.1080/17445760.2012.668546.

6 Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. *Distributed Computing*, 22(1):49–71, April 2009. doi:10.1007/s00446-009-0084-6.

7 Justin M Curry. Sheaves, cosheaves and applications, 2014.

8 Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi. *Reasoning About Knowledge*. MIT Press, 1995. doi:10.7551/mitpress/5803.001.0001.

9 Stephan Felber, Bernardo Hummes Flores, and Hugo Rincon Galeana. Brief announcement: A sheaf-theoretic characterization of tasks in distributed systems. In Ulrich Schmid and Roman Kuznets, editors, *Structural Information and Communication Complexity - 32nd International Colloquium, SIROCCO 2025, Delphi, Greece, June 2-4, 2025, Proceedings*, volume 15671 of *Lecture Notes in Computer Science*, pages 425–430. Springer, 2025. doi:10.1007/978-3-031-91736-3_26.

10 Faith E. Fich and Eric Ruppert. Hundreds of impossibility results for distributed computing. *Distributed Comput.*, 16(2-3):121–163, 2003. URL: https://doi.org/10.1007/s00446-003-0091-y, doi:10.1007/S00446-003-0091-Y.

11 Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. *J. ACM*, 32(2):374382, April 1985. doi:10.1145/3149.214121.

12 Éric Goubault, Roman Kniazev, Jérémy Ledent, and Sergio Rajsbaum. Semi-Simplicial Set Models for Distributed Knowledge. *2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)*, pages 1–13, 2023. doi:10.1109/LICS56636.2023.10175737.

13 Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. *J. ACM*, 37(3):549–587, 1990. doi:http://doi.acm.org/10.1145/79147.79161.

14 Jakob Hansen and Robert Ghrist. Opinion Dynamics on Discourse Sheaves. *SIAM Journal on Applied Mathematics*, 81(2):2033–2060, 2021. doi:10.1137/20M1341088.

15 Allen Hatcher. *Algebraic topology*. Cambridge University Press, Cambridge, 2002.
16 Maurice Herlihy, D. N. Kozlov, and Sergio Rajsbaum. *Distributed Computing through Combinatorial Topology*. Morgan Kaufmann, is an imprint of Elsevier, 2014.

17 Maurice Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In *STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing*, pages 111–120, New York, NY, USA, 1993. ACM. doi:http://doi.acm.org/10.1145/167088.167125.

18 Cliff A. Joslyn, Lauren Charles, Chris DePerno, Nicholas Gould, Kathleen Nowak, Brenda Praggastis, Emilie Purvine, Michael Robinson, Jennifer Strules, and Paul Whitney. A Sheaf Theoretical Approach to Uncertainty Quantification of Heterogeneous Geolocation Information. *Sensors*, 20(12):3418, 2020. doi:10.3390/s20123418.

19 Leslie Lamport. The weak byzantine generals problem. *Journal of the ACM (JACM)*, 30(3):668–676, 1983.

20 Saunders Mac Lane and Ieke Moerdijk. *Sheaves in Geometry and Logic: A First Introduction to Topos Theory*. Universitext. Springer New York, 1994. doi:10.1007/978-1-4612-0927-0.

21 M. Makkai and J. Rosický. Cellular categories. *Journal of Pure and Applied Algebra*, 218(9):1652–1664, 2014. doi:10.1016/j.jpaa.2014.01.005.

22 Yoram Moses and Sergio Rajsbaum. A Layered Analysis of Consensus. *SIAM Journal on Computing*, 31(4):989–1021, 2002. _eprint: https://doi.org/10.1137/S0097539799364006 doi:10.1137/S0097539799364006.

23 Thomas Nowak, Ulrich Schmid, and Kyrill Winkler. Topological characterization of consensus in distributed systems: Dedicated to the 2018 dijkstra prize winners bowen alpern and fred b. schneider. *J. ACM*, August 2024. Just Accepted. doi:10.1145/3687302.

24 Michel Raynal. *Concurrent Programming: Algorithms, Principles, and Foundations: Algorithms, Principles, and Foundations*. Springer, Berlin, Heidelberg, 2013. URL: https://link.springer.com/10.1007/978-3-642-32027-9, doi:10.1007/978-3-642-32027-9.

25 Michael Robinson. Sheaves are the canonical data structure for sensor integration. *Information Fusion*, 36:208–224, 2017. doi:10.1016/j.inffus.2016.12.002.

26 Nicola Santoro and Peter Widmayer. Time is not a healer. In *Proc. 6th Annual Symposium on Theor. Aspects of Computer Science (STACS'89)*, LNCS 349, pages 304–313, Paderborn, Germany, February 1989. Springer-Verlag.

27 Nicola Santoro and Peter Widmayer. Agreement in synchronous networks with ubiquitous faults. *Theoretical Computer Science*, 384(2):232–249, 2007. Structural Information and Communication Complexity (SIROCCO 2005). URL: https://www.sciencedirect.com/science/article/pii/S0304397507003350, doi:10.1016/j.tcs.2007.04.036.

28 Ulrich Schmid, Manfred Schwarz, and Kyrill Winkler. On the Strongest Message Adversary for Consensus in Directed Dynamic Networks. In *Structural Information and Communication Complexity*, Cham, 2018. Springer International Publishing. doi:10.1007/978-3-030-01325-7_13.