A General Input-Dependent Colorless Computability Theorem and Applications to Core-Dependent Adversaries

Since the initial work of Herlihy and Shavit [15], Saks and Zaharoglou [24], and Borowsky and Gafni [4], showing that distributed computability questions are amenable to topological methods, many important applications have been demonstrated. This framework describes distributed problems as tasks $(ℐ,𝒪,\mathrm{\Delta })$. $ℐ$ is a colored simplicial complex of all the input configurations, $𝒪$ is a colored simplicial complex with all the output configurations and $\mathrm{\Delta }$ is a relation that specifies, for any input, which outputs can be accepted. Simplicial complexes proved to be a convenient mathematical tool to represent distributed situations. In this setting, the most used model of communication is the Iterated Immediate Snapshot ($IIS$) model, since one round of computation is simply represented by a Standard Chromatic Subdivision (see [11] for a detailed presentation). One of the biggest computability results around these methods is the Asynchronous Computation Theorem (ACT) which says that a task $(ℐ,𝒪,\mathrm{\Delta })$ is solvable if and only if there is a simplicial map from an iterated Standard Chromatic Subdivision of $ℐ$ to $𝒪$. There also exists a simpler, and more powerful, version for colorless tasks (tasks where the specification doesn’t need the name of processes), which states [11, Th. 4.3.1]: a colorless task $(ℐ,𝒪,\mathrm{\Delta })$ is solvable on the $IIS$ model if and only if there is a continuous map from $|ℐ|$ to $|𝒪|$ respecting $\mathrm{\Delta }$. Such computability theorems aim to provide tight characterization for general tasks and allow proofs leveraging simplicial or topological arguments for particular tasks. One major line of research extends this colorless computability theorem to many other models of communication.

For this paper, we restrict our attention to the message adversary setting where the communication model has a round structure, and each round corresponds to a communication graph between the processes involved. Moreover, the set of possible graphs can vary between each round, making this a very flexible setting. In particular, the $IIS$ model can be expressed in this setting, as well as any subset of executions of the $IIS$ model. A lot of work has been done to obtain simplicial understanding of many models, from oblivious message adversaries to core adversaries. The failure pattern has become more refined. For some examples see [14], [12] or [23, 18] Recently, an extension called general message adversary has been proposed (see [9], [21], [6], [3], [7]). This approach can investigate any subset of executions of IIS. In particular, “non-compact” sets of executions can be considered. A natural example is the $t$-resilient adversary: one will eventually get a message from $n-t$ processes, but the time where a process might be silent can get arbitrarily long.

The “non-compact problem” was uncovered with [9] where they obtained a combinatorial and topological characterization of the consensus for 2-processes that observe that, for computability, some executions seem to work in (special) pairs. This was generalized for any number of processes in [6] with the introduction of the geometrization topology that interprets special pairs as a non-separable point, in the classical topological meaning. Another direction is [21] that provides a characterization of the solvability of Consensus for any number of processes for the general model of computation using an abstract topology on the set of executions. Then [3] provides a colored version of an ACT-like theorem for general message adversaries, using terminating subdivision and another ACT-like theorem for general models of computation, using the abstract topology. Later, [7] came with a colorless computability theorem for general message adversaries, using again terminating subdivision and the geometrization topology.

This article is built upon [7], mostly because this approach to geometrization enables to consider a simple execution space that is mostly like a ${ℝ}^N$ space. This makes possible simple geometric reasoning as is demonstrated here. The main Theorem of [7] is the following. Given $(ℐ,𝒪,\mathrm{\Delta })$ a colorless task, it is solvable on $M\subseteq II{S}_n$ if and only if there is a continuous function $f:geo(ske{l}^{n}I\times ℳ)\to |O|$ carried by $\mathrm{\Delta }$, where $geo$ is the geometrization mapping. We can remark that, in this statement, the message adversary is independent of the input values. In this paper we introduce the input-dependent setting of general message adversary of $IIS$ and provide a similar computability theorem for such model in Th. 16. An input-dependent adversary can present executions that are different depending on the input configuration, it is a subset $𝒜$ of $ℐ\times II{S}_n$. The characterization is as follows, a colorless task $(ℐ,𝒪,\mathrm{\Delta })$ is solvable under $𝒜$ if and only if there is a continuous function $f:geo(𝒜)\to |O|$ carried by $\mathrm{\Delta }$,

This new computability theorem on general message adversaries is an interesting extension in itself, we also provide applications. A contribution of this paper answers an open question from [19] about condition-based adversaries that were introduced by Mostéfaoui, Rajsbaum, Raynal, and Roy. This setting considers the solvability only for a subset of input configurations. In [19], the authors investigated the $k$-set agreement problem within a $t$-resilient model. They prove that if $C\subseteq ℐ$ enables to solve the task, there is a simplicial function from a specific complex, denoted $𝒦in(C,f,k)$, to $𝒪$. Also, two conditions are proposed on the set of inputs that make $k$-Set Agreement solvable for a $t$-resilient model. Here, we propose an alternate simplicial construction $𝒰(𝒞)$ (that is actually geometrically related to $𝒦in(C,f,k)$) such that $k$-Set Agreement is solvable on a core-dependent model $\mathscr{H}$ if and only if there is a simplicial map from $𝒰(\mathscr{H}(𝒞))$ to $𝒪$. Moreover, we show that knowing if a set of inputs makes $k$-Set Agreement task solvable for a given adversary is computable. While doing so, we show that the computability power of the core-resilient adversary is the same as the situation where crashes happen only before any communication.

Let $n\in \mathbb{N}$, we consider systems with $n+1$ processes and denote ${\mathrm{\Pi }}_n=[0,..,n]$ the set of processes. Sending a message is an asymmetric action, so we use directed graphs with the standard notations: let $G$, $V(G)$ is the set of vertices, $A(G)\subset V(G)\times V(G)$ is the arcs.

Since $n$ will be mostly fixed through the paper, we write $\mathrm{\Pi }$ and $𝒢$ when there is no ambiguity. We use classical vocabulary on infinite words. Let $U\subseteq 𝒢$, $U^{\ast }$ is the set of finite sequences in $U$ and $U^{\omega }$ be the set of infinite ones. For a word $u$, $u_{|r}$ is the prefix of size $r$ and $u(r)$ is the $r$-th letter of the word. The distributed intuition behind such a graph is that $G_r$ describes whether there will be transmission of some messages between each pair of processes at the round $r$. To highlight the distributed nature of such a graph, we can use communication scenario to describe a word on $𝒢$ and instant graph for a letter in a word.

Given a message adversary $ℳ$ and a set of initial configurations $ℐ$, we define execution as an initialization step and a communication scenario. This corresponds to a (possibly infinite) sequence of rounds of message exchanges and corresponding local state updates. When the initialization is clear from the context, we will use scenario and execution interchangeably.

With more details, an execution of an algorithm $𝒜$ under scenario $w\in ℳ$ and initialization $\iota \in ℐ$ is denoted as $\iota .w$ and is composed by following steps. First, $\iota$ affects the initial state to all processes of $\mathrm{\Pi }$. Then the system progresses in rounds. A round is decomposed into 3 sub-steps: sending, receiving, and updating the local state. At round $r\in \mathbb{N}$, the processes use the SendAll() primitive to send messages. The fact that the corresponding receive actions, using the Receive() primitive, will be successful depends on the instant graph $G$.

Let $p,q\in \mathrm{\Pi }$. The message sent by $p$ is received by $q$ on the condition that the arc $(p,q)\in A(G)$. Then, all processes update their state according to the received values and $𝒜$. Note that it is assumed that $p$ always receives its own value, which is $(p,p)\in A(G)$ for all $p$ and $G$. However, this might be implicit for clarity and brevity. We denote the local state of a process $p$ in an execution $w=\iota .u$ at the round $r$ of the algorithm as ${𝐬}_p(\iota .u[r])$. ${𝐬}_p(\iota .\epsilon )=\iota (p)$ represents the initial state of $p$ in $\iota$, where $\epsilon$ is the empty word. Note that in our framework, processes have identities (“colors”) and can therefore distinguish identical values sent by different processes. This model is denoted as the colored model of computation.

The message adversary framework allows us to describe a wide array of communication models. Like many other distributed computing papers that adopt a topological approach, the central model in this one is the Iterated Immediate Snapshot ($IIS$) model. It was first introduced as a (shared) memory model, which has been proved equivalent to the message adversary below first as tournaments and iterated tournaments [5, 2], then as this message adversary [11, 13]. See also [22] for a survey of the reductions involved in these layered models. Given a graph $G$, we denote by $I{n}_G(a)=\{b\in V(G)\mid (b,a)\in A(G)\}$ the set of incoming vertices of $a$ in $V(G)$. A graph $G$ has the containment Property if for all $a,b\in V(G)$, $I{n}_G(a)\subset I{n}_G(b)$ or $I{n}_G(b)\subset I{n}_G(a)$. We say that a graph $G$ has the Immediacy Property if for all $a,b,c\in V(G)$, $(a,b),(b,c)\in A(G)$ implies that $(a,c)\in A(G)$.

The setting of this paper is the general sub-message adversaries of the $IIS$ model, which is $ℳ\subseteq II{S}_n$. Many studied adversaries in the literature can be represented as such, like oblivious adversary, t-resilient adversary or core-resilient adversary or any ’situation-specific’ adversary. We also use the terminology crash (which is, strictly speaking, irrelevant for messages adversaries) for a process that is not heard of by all other processes for an infinite amount of time.

As an example with two processes $\circ$ and $\bullet$, we can define the message adversary $II{S}_1={\{\circ \leftrightarrow \bullet ,\circ \leftarrow \bullet ,\circ \to \bullet \}}^{\omega }$. In the execution $\circ \leftrightarrow \bullet \circ \leftarrow {\bullet }^{\omega }$, process $\circ$ is considered crashed starting from the second round. In the execution $\circ \leftrightarrow \bullet {(\circ \leftarrow \bullet \circ \to \bullet )}^{\omega }$, no process is crashed. A message adversary like ${ℳ}_1=\{\circ \leftrightarrow {\bullet }^{\omega }\}\cup {\{\circ \leftrightarrow \bullet \}}^{\ast }(\{\circ \leftarrow {\bullet }^{\omega },\circ \to {\bullet }^{\omega }\})$, that represent a system with two synchronized processes, where at most one of the processes may crash is a strict sub-adversary of $II{S}_1$ since ${ℳ}_1⊊II{S}_1$.
An iterated $t$-resilient adversary is a set of executions where at most $t$ processes may “crash” during the execution.
Let $Q(w)$ the set of processes that are seen by all processes an infinite number of times in $w$

Core-resilient adversaries are a generalization of $t$-resilient adversaries.

Even though we consider only colorless tasks, our model of computation is colored (see Section 2). In the colored computation model, the input configurations of a given colorless task are usually all the possible assignments of the initial values of the processes, so an initial value could be assigned many times. This means that the colored initial complex is not exactly $ℐ$. Since we will consider the very general input-dependent model, and a colored model of computation, we need a clear representation of the state of each process.

Consider a colorless task $(ℐ,𝒪,\mathrm{\Delta })$, and set $V_{in}=V(ℐ)$ and $V_{out}=V(𝒪)$. We assume wlog that there exists a total order $\prec$ on $V_{in}$ and that we can describe $V_{in}$ as $\{v_0,v_1,\mathrm{\cdots },v_n\}$, where $v_i\prec v_j$ when . The first setting is called unique-value. From a set of processes $\mathrm{\Pi }=[0,n]$, there is only one process that can have a given initial value, and each process has exactly one value initially. This yields a colored simplicial complex $𝒱(ℐ)$ with vertices $\{(i,v_i)\mid i\in [n]\}$ and simplices $((i_0,v_{i_0}),\mathrm{\dots },(i_d,v_{i_d}))$ whenever $\{v_{i_0},\mathrm{\dots },v_{i_d}\}$ is a simplex of $ℐ$. This colored simplicial complex is actually $ℐ$, adding colours in the enumeration order $\prec$. The second setting is called multi-value, which allows different processes to have the same initial value, including in the same initial configuration. This forms a pseudosphere of $ℐ$, which is the following colored simplicial complex ${𝒫}_n(ℐ)$. The set of vertices is $\mathrm{\Pi }\times V(ℐ)$. A set $\{(i_0,v_{i_0}),\mathrm{\dots },(i_d,v_{i_d})\}$, with for , is a simplex of ${𝒫}_n(ℐ)$ whenever $\{v_{i_0},\mathrm{\dots },v_{i_d}\}$ is a simplex of $ℐ$. Note that here $\{(i_0,v_{i_0}),\mathrm{\dots },(i_d,v_{i_d})\}$ is a simplex of dimension $d$ whereas $\{v_{i_0},\mathrm{\dots },v_{i_d}\}$ could be a simplex of dimensions less than $d$. Fig. 1 illustrates the Binary Consensus task as encoded by a relation between input and output complexes.

Fig. 2 gives two representations of the encoding of Binary Consensus in the colored model of computation (with $\circ$ as color $0$ and $\bullet$ as color $1$), one in the unique value setting, and the other one in the multi-value setting.

Moving from one setting to another can be done using the function $GIV:{ℐ}_P\to {ℐ}_V$ (as Get Input Value) to associate a colored simplex to a colorless simplex that contains the same input values: $GIV(\{(p_0,v_0),(p_1,v_1),\mathrm{\dots },(p_n,v_n)\})=\{v_0,v_1,\mathrm{\dots }{v}_n\}$. Moreover, the carrier map for the multi-value setting ${\mathrm{\Delta }}_p$ needs some adjustments, $\forall \sigma \in {𝒫}_n(ℐ),{\mathrm{\Delta }}_p(\sigma )=\mathrm{\Delta }(GIV(\sigma ))$. Which makes sense, in a colorless task the value of a simplex decides its possible output.

This paper considers 4 classes of adversaries that can be applied to a colorless task $(ℐ,𝒪,\mathrm{\Delta })$. The standard setting has a message adversary ${ℳ}_1=II{S}_n$ while the sub-model setting has a message adversary ${ℳ}_1\subseteq IIS$. Both can apply to a unique value context ($ℳ=𝒱(ℐ)\times {ℳ}_1)$ or a multi-value context ($ℳ={𝒫}_n(ℐ)\times {ℳ}_1$). These two contexts are considered interchangeable in the literature, since in the standard setting, they are simply equivalent, as we will prove on Prop. 10. In the input-dependent submodel setting, one has to be more careful. The results of [7] were presented in the unique-value setting. The condition-based setting has a message adversary ${ℳ}_1\subseteq II{S}_n$ and $C\subseteq {𝒫}_n(ℐ)$ to form executions on $ℳ=C\times {ℳ}_1$. This corresponds to adding a condition of distribution of initial values that are not valid. This is the setting of [19] with ${ℳ}_1={ℛ}_n^t$ (the $t$-resilient model). Finally, the input-dependent setting considers execution in $ℳ\subseteq ℐ\times II{S}_n$, which adds the possibility of changing the message adversary depending on the input configuration. This setting encompasses all previously described settings.

In Figure 3, we present examples of our various setting for the Binary Consensus. In Fig. 3(a), for condition ${𝒞}_1$, we remove the possibility of $\bullet$ and $\circ$ to have different initial values. On Fig. 3(b), for condition ${𝒞}_2$, we remove all input configurations where $\bullet$ starts with the value $1$. We denote ${ℳ}_1=II{S}_1\setminus \{\circ \leftrightarrow {\bullet }^{\omega }\}$. Fig. 3(c) presents the geometrization of sub-model condition-based adversaries ${𝒞}_2\times {ℳ}_1$. Intuitively, the red cross represents the missing execution $\circ \leftrightarrow {\bullet }^{\omega }$, see later in Section 5.2. We define ${ℳ}_2$ to be the input dependent model where the possible inputs are from ${𝒞}_2$, and the possible executions are $II{S}_1$ when the two initial values are $0$, and where the possible executions are ${ℳ}_1$ when the two initial values are different. The geometrization of ${ℳ}_2$ is given in Fig. 3(d).

The unique-value setting and the multi-value setting are equivalent on IIS from a computability point of view.

We present here classical definitions of geometric complexes and provide a link between distributed computability and such geometric setting, as our general computability setting could need infinite complexesWe fix $N\in \mathbb{N}$ and denote $𝐁(x,r)=\{y\in X|d(x,y)\le r\}$ with $x\in {ℝ}^N,r\in ℝ$ and $d(x,y)$ the Euclidean distance on ${ℝ}^N$.

Let $|\sigma |$ be the convex hull of $\sigma$ and $Int(\sigma )$ is the interior of $|\sigma |$. The open star of $\sigma \in C_1:$ $S{t}^{\circ }(\sigma ,C_1)={\bigcup }_{\tau \in C_1,\sigma \subseteq \tau }Int(\tau )$. Let ${𝕊}^n$ be “the” simplex of dimension $n$: through this paper we assume a fixed embedding in ${ℝ}^N$ for ${𝕊}^n=(x_0^{\ast },\mathrm{\dots },x_n^{\ast })$ and a diameter $diam({𝕊}^n)$ at 1.

For any simplicial complex $C$, we can associate a set of geometric points $geo(C)={\bigcup }_{\sigma \in C}|\sigma |$. We will use $geo(C)$ or $|C|$ interchangeably for finite complexes¹¹1As a set of points $geo(C)$ corresponds to the points of the topological space $|C|$ that is classically called the geometric realization. When $C$ is finite, $geo(C)$ has the same topology (in ${ℝ}^N$) as the geometric realization $|C|$. It could not be the case if $C$ is infinite, see [7]. . Let $A$, $B$ be finite simplicial complexes and $\delta$ a simplicial map from $A$ to $B$. It can be extended to $f:|A|\to |B|$ using barycentric extension. Let $\sigma =\{x_0,\mathrm{\dots },x_n\}$ a simplex of $A$. Since any $y\in |\sigma |$ could be obtained as $y={\sum }_{i=0}^d{t}_i.x_i$ with $t_i\in [0,1]$ and ${\sum }_{i=0}^d{t}_i=1$, we set $f(y)={\sum }_{i=0}^d{t}_i.\delta (x_i)$. Let $X\subset {ℝ}^N$, a function $f:X\to |C_2|$ respects a carrier map $\mathrm{\Delta }:C_1\to 2^{C_2}$ with $X\subseteq |C_1|$, if $\forall \sigma \in C_1,f(|\sigma |\cap X)\subseteq \mathrm{\Delta }(\sigma )$.

In distributed computing there are two subdivisions that are used, the barycentric Subdivision and the Standard Chromatic Subdivision. In this paper, the barycentric is useful for another reason than being the subdivision used to represent colorless computability (see section 7.1). A complete presentation of the second one is in Section A.

Here, we present the connection between executions of the Iterated Immediate Snapshot and simplicial complexes. To achieve this, we employ an algorithm called the Chromatic Average algorithm. It accepts an execution $w$ in the $IIS$ model and produces a geometrical simplex. This has been introduced in [6], for a detailed presentation refer to [6, 7].

A given loop of this algorithm corresponds to one execution of the Immediate Snapshot protocol. Geometrically, this algorithm associates with every possible view of processes and initial configuration $\sigma \in ℐ$ in the $ImS$ protocol to a given vertex in the Standard Chromatic Subdivision of $\sigma$. We present in more detail this subdivision in the Appendix Section A. The equivalence between this subdivision and the $ImS$ model can be seen in [17].

On Fig. 4(a), we represent the mapping of one instant graph $G$ from an execution in $IIS$ to a simplex in $\mathrm{Chr}({𝕊}^2)$. On Fig. 4(b), these associations are presented for every possible instant graph of $Im{S}_2$. The mapping of a prefix of size $t$ of an execution $w\in II{S}_n$ to $\sigma \in {\mathrm{Chr}}^t{𝕊}^n$ is called the geometrization of $w_{|t}$, denoted as $geo(w_{|t})({𝕊}^n)$.

Since [6] the geometrization approach has been shown to be a fruitful way to handle (the limit of) iterated executions. From $geo(w_{|t})({𝕊}^n)$ that work on prefixes of execution, we can take the limit on the size of prefixes, $geo(w)=li{m}_{t\to \mathrm{\infty }}geo(w_{|t})({𝕊}^n)$. This operation is well defined, as it makes every execution converge to a geometric point (see [6] for more detail).

The geometrization topology is defined on $II{S}_n$ by considering as open sets the sets $ge{o}^{-1}(\mathrm{\Omega })$ where $\mathrm{\Omega }$ is an open set of ${ℝ}^N$. A collection of sets can define a topology when any union of sets of the collection is in the collection, and when any finite intersection of sets of the collection is in the collection. This is straightforward for a collection of inverse images of a collection that satisfies these properties. Note this also makes $geo$ continuous by definition.

The previous construction took ${𝕊}^n$ as input, we extend the previous definition to any input simplices. For $ℳ\subseteq II{S}_n$ and $\sigma \in ℐ$ with $dim(\sigma )=n$ we can define $\forall w\in ℳ,geo(w)(\sigma )$ by using a mapping from ${𝕊}^n$ to $\sigma$ which maps a vertex $i$ of ${𝕊}^n$ to $v_i$ with color $i$ in $V(\sigma )$ (this is called the characteristic map of $\sigma$). Hence, $geo(ℐ\times ℳ)$ is defined as ${\bigcup }_{w\in ℳ,\sigma \in ℐ}{\phi }_{\sigma }(geo(w))$. This construction associates to any set of executions $ℐ\times ℳ$ a topological subspace of ${ℝ}^N$.

Executions in non-compact sub-models of IIS may not terminate at the same round. The well-known correspondence between terminating algorithms and complexes could therefore yield infinite complexes. In this iterated subdivision framework, such (possibly infinite) complexes are called terminating subdivisions and were first introduced in [8]. For this article, we use the combinatorial definition of $IIS$-terminating subdivision from [7]. Given a complex $C$, let $C(T)={\bigcup }_{\sigma \in C,V(\sigma )\subseteq T}\sigma$ with $T\subseteq V(C)$ to represent the sub-complex of $C$ formed by the vertices in $T$. Let $JOIN(C_1,C_2)=\{|\sigma \cup \tau ||\sigma \in C_1,\tau \in C_2\}$. We define $EChr$ as the following operator:

Intuitively, the vertices marked as terminated are in $T$. We note $U=V(C)\setminus T$. The operator $EChr$ subdivides with the standard chromatic subdivision the facets that are fully in $U$, does not modify the ones that are fully in $T$ and subdivides in an adequate way the facets containing both.

We say that $\bigcup C_i(T_i)$ is an $IIS$-terminating subdivision complex. This is indeed an actual geometric simplicial complex, see [7].

When working with a specific model of computation, a natural question may be, “What the geometrization of such model looks like?” The geometrization of $t$-resilient and core-resilient adversaries is not easy to grasp. Hence, one goal of this paper is to provide computability equivalence with a model that has much nicer geometrization.

Geometrically, we can construct the $t$-resilient adversary by removing all simplices of dimension $n-t$ for every round of computation. In other words, $geo(R_n^t)={\bigcap }_{i\in \mathbb{N}}|ℐ|\setminus geo(ske{l}^{n-t-1}Ch{r}^iℐ)$. This yields a fractal-like geometrization of $R_n^t$. A detailed presentation of the geometrization of $R_t^n$ is in the Appendix, section A.2 for example for $3$ processes and one crash. For core-resilient adversaries, any set of the core corresponds to a simplex $\sigma$ in an input complex $ℐ$. Then $\forall \tau ⊊\sigma$, their images through the iterated subdivisions are removed from $|ℐ|$, since it corresponds to a subset of processes that can crash altogether starting from that particular initial configuration. As for $R_n^t$ the processes can crash at any moment of the computation; hence, simplices in all steps of the geometrization are to be removed, which also yield a fractal-like space.

These two models have a “quite complicated” geometrization space thanks to the “fractal”-part. In order to have simpler spaces, we will consider similar models where crashes only happened before a given round. The $r-$restricted $t$-resilient model is defined as ${𝒮}_r^t=\{w\in IIS|K_r(w)\le t\}$ with $K_r(w)$ the set of processes that are never seen by some process starting from round $r$ excluded, e.g. $K_0(w)$ is the set of processes that are crashed at the start of the computation. We have simply $geo({𝒮}_0^t)=|ℐ|\setminus |ske{l}^{n-t-1}ℐ|$.

Similarly, let $\mathscr{H}$ a core-resilient adversary, we denote by ${\mathscr{H}}_r$ the $r-$restricted associated core-adversary, where crashes happen at round $r$. Then, $geo(ℐ\times {\mathscr{H}}_0)=ℐ\setminus \{\sigma \in ℐ||\sigma |\cap geo(ℐ\times \mathscr{H})=\mathrm{\varnothing }\}$.

Let $\mathscr{H}$ an input-dependent core adversary(core-dependent in short) on simplicial complex $ℐ$, we denote by $𝒞(\mathscr{H})$ the condition for $\mathscr{H}$, that is $𝒞(\mathscr{H})=\{\sigma \in ℐ\mid |\sigma |\cap geo({\mathscr{H}}_0)\ne \mathrm{\varnothing }\}$. By extension of notation, we note $𝒰(\mathscr{H})$ as the part of the barycentric subdivision of $ℐ$ that intersects in $geo({\mathscr{H}}_0)$. More formally: $V(𝒰(\mathscr{H}))=\{iso(\tau )|\tau \in 𝒞(\mathscr{H})\}$, where $iso(\tau )$ is the isobarycenter of simplex $|\tau |$. The simplices of $𝒰(\mathscr{H})$ corresponds to sets of isobarycenters of simplices that can be ordered by inclusion.

This first theorem shows that models ${\mathscr{H}}_0$ associated with core-dependent model $\mathscr{H}$, ie when crashes happen before the first round, have the same computability power as $𝒰(\mathscr{H})$, which corresponds to a subset of the barycentric subdivision of $ℐ$.

Presenting a distributed task as triple $(ℐ,𝒪,\mathrm{\Delta })$ creates the possibility of having tasks that have equivalent computability, which is, they are solvable on the same message adversaries. In this section, we propose multiple propositions/lemmas showing how to transform a task to another one that is simpler to analyze but has the same computability.

The carrier map of a task describes where some simplex in the input complex can be mapped in the output complex. Then a task is solvable if we are able to construct a simplicial map from a terminating subdivision of the input complex to the output complex. This first lemma leverages the fact that a simplicial function cannot map a simplex to another one of greater dimensions.

Let $T=(ℐ,𝒪,\mathrm{\Delta })$ a task is Non-Expanding if $\forall \sigma \in ℐ,dim(\mathrm{\Delta }(\sigma ))\le dim(\sigma )$. Lemma 27 implies that any task is equivalent to a non-expanding one. Let $(ℐ,𝒪,\mathrm{\Delta })$ a task, let $\sigma \in ℐ$, we set $\overline{\mathrm{\Delta }}(\sigma )=\{\tau \in \mathrm{\Delta }(\sigma )|dim(\tau )\le dim(\sigma )\}$.

In this section we look at the solvability of the $k$-set Agreement in a condition based context against core-dependent adversaries. This problem was introduced in [19] for $t$-resilient models, and the answer can be directly inferred for $k+1\le t$ from classical result on $t$-resilient model [14]. For $k+1>t$, from [19], we have some conditions that can solve the $k$-set Agreement for $t$-resilient model. In this section, we show that deciding if some condition-based adversary can solve the $k$-set Agreement for a given $t$ is computable.

Let $𝒞$ a condition for task $(ℐ,𝒪,\mathrm{\Delta }).$ If this task is solvable on $𝒞\times ℳ$ then, $\forall {𝒞}^{\prime }\subseteq 𝒞$, this is also solvable. Hence, we say that $𝒞$ is maximal for the task $T=(ℐ,𝒪,\mathrm{\Delta })$ if $𝒞$ solves the task $T$ and $\forall {𝒞}^{\prime },𝒞⊊{𝒞}^{\prime }$, $T$ is not solvable on ${𝒞}^{\prime }$. Given a condition $𝒞$ on $𝒫({𝕊}^k)$, we call $𝒞$-core-dependent adversary a core-dependent adversary with support $𝒞$.

The [19] paper introduced the condition-based setting against a $t$-resilient model and asked which conditions solve the $k$-set agreement.

Given a condition $𝒞\subseteq 𝒫(ℐ)$, they consider every set of values of size at least $n-t+1$ that is present in $𝒞$ as a vector of size $n+1$ with at most $t$ values that are unset. They consider an associated simplicial complex that is called $𝒦in(C,f,k)$ and an example can be found in the Appendix, section A.1, Figure 6.

With this construction, it is proved in [19] that if there is a simplicial function from $𝒦in(C,f,k)$ to $ske{l}^kℐ$, then a condition $𝒞$ can solve the $k$-set Agreement for the $t$-resilient model.

Looking at $𝒦in(C,f,k)$, we can see that it is the $k$-skeleton of $𝒰(C)$ since the barycentric subdivision corresponds to using inclusion-ordered initial simplexes as new simplices. Hence, Theorem 24 shows that the sufficient condition from [19] is actually necessary.

Theorem 24 provides several improvements: we have a necessary and sufficient characterization that works for a larger class of adversaries, the core-dependent adversaries.

Another contribution of [19] is that they provide two example conditions that generate a set of input configurations that make the $k$-set agreement solvable.

The first condition ($C_1$) uses an order on the input value. For any proper simplex $\sigma \in 𝒫(ℐ)$, we write $a_1\mathrm{\dots }{a}_{\mathrm{\ell }}$ the input value arranged from the biggest to the lowest, $a_1\ge a_2\mathrm{\cdots }\ge a_{\mathrm{\ell }}$. Moreover, $\mathrm{\#}{a}_i$ denotes the number of occurrences of the value $a_i$. If ${\sum }_1^k\mathrm{\#}{a}_i>t$, then $\sigma \in C_1$.

The second condition ($C_2$) works directly on the number of occurrences for each input value in a proper simplex $\sigma \in 𝒫(ℐ)$. Now $a_1$ denotes the number of occurrences of the most occurring value, $a_2$ the number of the second most occurring value etc… Then $\sigma \in C_2$ if ${\sum }_1^k\mathrm{\#}{a}_i-\mathrm{\#}{a}_{k+1}\ast k>t$.