Pierre Fraigniaud
email: pierre.fraigniaud@liafa.jussieu.fr

Sergio Rajsbaum
email: rajsbaum@math.unam.mx

Corentin Travers
email: travers@labri.fr

Locality and Checkability in Wait-free Computing *

Keywords: distributed verification, local computing, wait-free, decision task

A task T is described by a triple (I, O, ∆) where I is the set of input configurations, O is the set of output configurations, and ∆ is the specification of the task mapping every input to a set of possible outputs. We consider notions of locality that are inherent to the task specification, independently from the computational model. We observe that tasks as different as (d + 1)coloring for degree-d graphs, in the network setting, and consensus, in the wait-free setting, both satisfy the local condition ∆(π(s)) ⊆ π(∆(s)) stating that any output ∆(π(s)) for a partial input π(s) is a partial output π(∆(s)) for the full input s. This property, called monotony, captures locality in a very general sense, independent of the computing environment, by expressing the relationship between the various scales of computation, from the individual processes to the whole system. Unfortunately, monotony is not sufficient to ensure efficient computation in the network setting, neither it is sufficient to ensure solvability in the wait-free setting. This paper thus investigates other notions of locality which, in the framework of wait-free computing, open up to new, rich classes of tasks.

First, we define a task to be projection-closed if π(∆(s)) ⊆ ∆(π(s)), and prove the perhaps surprising fact that projection-closed tasks are precisely those tasks that are wait-free checkable, that is tasks T = (I, O, ∆) for which there exists a wait-free distributed algorithm enabling, given a pair (s, t), s ∈ I, t ∈ O, to check whether t ∈ ∆(s), i.e., to decide whether t is a valid output for s.

Our second main contribution is dealing with a stronger notion of locality, where ∆(π(s)) = π(∆(s)). A task T = (I, O, ∆) is said to be locality-preserving if and only if O is a covering complex of I, that is there exists a map p : O → I which agrees with ∆ (i.e., t ∈ ∆(p(t)) for every t ∈ O). This topological property yields obstacles for wait-free solvability different in nature from the classical agreement impossibility results. Apart from the identity task, locality-preserving tasks are not wait-free solvable. On the other hand, locality-preserving tasks are projection-closed, and therefore they are wait-free checkable. We provide a classification of locality-preserving tasks in term of their computational power, by establishing a correspondence between locality-preserving tasks and subgroups of the edgepath group of a complex. Using this correspondence, we prove the existence of hierarchies of locality-preserving tasks, each one

Introduction

A task is a distributed coordination problem in which each process starts with a private input value, communicates with the other processes by applying operations to shared objects, and eventually decides a private output value. It can be described by a triple (I, O, ∆) where I is the set of input configurations, O is the set of output configurations, and ∆ is the specification of the task mapping every input configuration to a set of possible output configurations. A protocol is a distributed program that solves a task.

Often it is useful to consider (input or output) configurations where the states of only a subset of the processes are specified. If s is an input configuration, π(s) denotes the configuration obtained by projecting out the processes specified by π. Then, the map ∆ of a task specifies with ∆(π(s)) the valid output configurations for π(s). For instance, let G be a network of processes, with one process per node, exchanging information along their incident edges. Assume one wants to color the nodes of G in such a way that two adjacent nodes are assigned different colors. The literature tackling this task (see, e.g., [START_REF] Barenboim | Deterministic distributed vertex coloring in polylogarithmic time[END_REF][START_REF] Kuhn | On the complexity of distributed graph coloring[END_REF]) generally assumes that d + 1 colors are available, where d denotes the maximum degree of G. The main motivation for this assumption is that every graph is (d + 1)-colorable, whereas there are graphs that are not d-colorable, like, e.g., the complete graphs, or the cycles of odd length. A more careful look at the specification ∆ of the (d + 1)-coloring task enables to identify a stronger property: any partial (d + 1)-coloring ∆(π(s)) for a subgraph π(s) induced by any set of processes specified by π, can be extended to a (d + 1)-coloring ∆(s) for s. In other words, the (d + 1)-coloring specification ∆ satisfies the monotony condition ∆(π(s)) ⊆ π(∆(s))

for every set of processes s, and every projection π. Instead, the specification of the d-coloring task does not satisfy this inclusion, even in networks that are d-colorable. For instance, if s denotes the four nodes of a 4-cycle, and π(s) denotes two antipodal nodes in this cycle, then the output consisting in coloring the nodes of π(s) with distinct colors cannot be extended to a valid output for the whole set s. It may thus be not coincidental that 3-coloring the n-node ring can be achieved in O(log * n) rounds (see [START_REF] Cole | Deterministic coin tossing with applications to optimal parallel list ranking Information and[END_REF]) whereas 2-coloring rings (of even size) requires Ω(n) rounds (see [START_REF] Linial | Locality in distributed graph algorithms[END_REF]).

The monotony condition expresses a notion of locality satisfied by the task, that can be phrased as: any output for a partial input is a partial output for the full input. It is important to observe that this notion expresses a form of locality that is inherent to the specification of a task, and independent of the distributed computing model. For instance, at the other extremity of the wide spectrum of distributed computing models, previous work in wait-free computing, where asynchronous processes subject to crash failures communicate via a read/write shared memory, often assumes tasks satisfying the monotony condition. Typically, consensus satisfies it. (Note that the inclusion is strict for consensus, whereas equality holds for (d + 1)-coloring). Monotony captures locality in a general sense, independent of the computing environment, by expressing the relationship between the various scales of computation. Indeed, monotony relates the specification for subsets of processes to the specification for larger sets. Thus, it relates the individual behavior of Figure 1: An intersection-closed task, which is not monotone, and not wait-free solvable. The projection π depicted is for the black process. The black process always starts with 0. When both run, they must agree on the input of the white process, either 1 or 2. If the white process runs solo, it must decide its own input.

If the black process runs solo, it can decide 1 or 2.

each process with the behavior of small group of processes, which in turn is related to the behavior of larger and larger groups, until one reaches the scale of the whole system. A weaker form of locality results from putting the burden on the protocol to find a right output in ∆(π(s)) for π(s), that can be extended to an output ∆(s) for s. In other words, instead of imposing a task to satisfy Eq. 1, it might be sufficient to assume the intersection-closeness condition

∆(π(s)) ∩ π(∆(s)) = ∅.
(

) 2
This weaker condition is an obvious requirement for a task to be wait-free solvable 1 whereas monotony is not a necessary condition for wait-free solvability. However, putting this burden on the shoulders of the protocol may be too much. Indeed, for s = s ′ with π(s) = π(s ′ ), it may be the case that π(∆(s)) ∩ π(∆(s ′ )) = ∅ even if Eq. 2 is satisfied for all s, s ′ , and π. See Fig. 1 for an example. In this case, the processes in π(s) running alone have no clue whether they have to output a solution extendable to an output for s or for s ′ . This is why tasks are usually assumed to satisfy the monotony condition instead of the weaker intersection-closeness condition.

Unfortunately, neither the intersection-closeness condition nor even the monotony condition provide sufficient constraints for solvability, or for efficient computation. For instance, in the network setting, monotony is not a guaranty for a task to be solved by having every node merely inspecting nodes at a constant distance (cf. the Ω(log * n) lower bound for (d + 1)-coloring [START_REF] Linial | Locality in distributed graph algorithms[END_REF]). Neither it is, in the wait-free setting, a guaranty for a task to be solvable (cf. the FLP impossibility result for consensus [START_REF] Fischer | Impossibility of Distributed Consensus with One Faulty Process[END_REF]). This paper investigates two other notions of locality, namely the projection-closeness condition, obtained by simply reversing the monotony condition,

π(∆(s)) ⊆ ∆(π(s)) (3)
and the one resulting from combining monotony with projection-closeness. These latter two notions are shown to be rich concepts, enabling to capture important features of the computational nature of tasks, at least as far as wait-free computing is concerned.

1 Assume it is not satisfied for some s and π. Consider the scenario in which all processes in s participate, but those in s \ π(s) are very slow, and do not take any step for some time. The wait-free requirement forces the processes in π(s) to decide values alone. Assume they decide values t ∈ ∆(π(s)). Now, the processes in s \ π(s) wake up, and start taking their steps. They have to decide some values, so that the processes in s collectively produce an output t ′ ∈ ∆(s). This output must satisfy π(t ′ ) = t because all processes in π(s) have already terminated with output t. This t ′ does not exist whenever ∆(π(s)) ∩ π(∆(s)) = ∅.

Our results

The objective of this paper is to investigate the ability of a shared memory system to solve tasks satisfying various forms of locality. Our investigation is performed in the wait-free setting where computation tolerates the halting failures or delays by n -1 out of n processes. In this context, it is convenient to view I and O as complexes (including configurations for any number of processes, between 1 and n), with the specification ∆ mapping every simplex s ∈ I to a sub-complex ∆(s) of O. See Figure 2 for a graphical representation of our results.

First, we show that the projection-closeness condition of Eq. 3 is closely related to the ability of checking a task. Informally, for checking a task T = (I, O, ∆), every process i ∈ [n] is given a pair (s i , t i ), and the participating processes must check that the simplex t with decision values t i , i = 1, . . . , n, is a valid output simplex according to ∆, for an input simplex s with values s i . Deciding the latter is performed according to the (informal) specifications:

• if t ∈ ∆(s) then all participating processes must output "yes",

• otherwise at least one participating process must output "no".

Hence checking the task T corresponds to solving a checking task, where the input entry of the ith process is a pair (i, (s i , t i )), and where each process must return either "yes" or "no". We prove that a task is wait-free checkable if and only if it is projection-closed (cf. Theorem 3.3). It is remarkable that the locality notion expressed by Eq. 3 captures precisely the ability to wait-free verify the results of a computation, even if these results have been obtained using more resources (e.g., oracles) or stronger models (e.g., t-resilience). Moreover, we show that the set of projectionclosed tasks is large by proving that determining whether a projection-close task is wait-free solvable remains undecidable (cf. Theorem 3.4). This latter result is obtained by proving that every task is equivalent to a wait-free checkable task (via implementations that preserve step-complexity).

Next, we turn our attention to tasks that are both projection-closed and monotone. As for monotony alone, the two conditions combined do not seem to provide sufficient structural constraints for relating them to wait-free computability. Nevertheless, we were able to identify a

We show that, indeed, locality-preserving form a subclass of the monotone and projection-closed tasks (cf. Theorem 4.3). The notion of locality captured by locality-preserving tasks is made explicit topologically. Informally, locality-preserving tasks are tasks where, from the perspective of a subset π(s) of processes with given input values, the possible inputs to the other processes look identically in structure to their possible outputs (see Figure 3 for an example). We show that locality-preserving tasks form a wide and rich class of tasks. We classify localitypreserving tasks in terms of their computational power. By identifying a correspondence between locality-preserving tasks and covering complexes (the classic algebraic topology notion used to study locality), we prove that locality-preserving task T implements locality-preserving task T ′ if and only if H ⊆ H ′ , where H, H ′ are groups associated to each of the tasks. This result demonstrates the existence of an infinite set of partial orders of locality preserving tasks. Each of these partial orders contains a hierarchy of locality-preserving tasks between the trivial identity task, and a universal task for this partial order. Some of these partial orders are finite, while others are infinite. As in [START_REF] Herlihy | A Classification of Wait-Free Loop Agreement Tasks[END_REF], we use topology techniques both to prove impossibility results, and to show when one task can implement another.

Related work

The locality notions considered in this paper, are local in the sense that they can be checked individually for pairs (s, t), s ∈ I, t ∈ O. The main obstacles to wait-free solvability studied in the past, most notably for set agreement and renaming [START_REF] Attiya | Renaming in Asynchronous Environment[END_REF], are of a different nature. Indeed, any wait-free protocol is actually a mapping from a subdivision of the input complex to the output complex [START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF]. Hence, topological properties must be preserved by a wait-free protocol. Checking these properties is hard, and, in fact, determining whether a task is wait-free solvable is not decidable [START_REF] Gafni | Three-Processor Tasks Are Undecidable[END_REF][START_REF] Herlihy | The Decidability of Distributed Decision Tasks[END_REF].

A different notion of locality has received lots of attention in the framework of network computing. Specifically, the so-called LOCAL and CON GEST models [START_REF] Peleg | Distributed Computing: A Locality-Sensitive Approach[END_REF] have been designed to study communication locality issues. One prominent result in this framework is the Ω(log * n) lower bound [START_REF] Linial | Locality in distributed graph algorithms[END_REF] for the number of rounds required to 3-color the nodes of the n-node ring network. In several papers in this framework, the main focus is on whether randomization helps [START_REF] Naor | What can be Computed Locally?[END_REF], on the impact of non-determinism [START_REF] Fraigniaud | Local Distributed Decision[END_REF], and on the power of oracles providing nodes with information about their environment [START_REF] Fraigniaud | Communication algorithms with advice[END_REF]. The impact on the design of efficient protocols of the absence of a priori knowledge on the global environment has been recently addressed in [START_REF] Korman | Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge[END_REF].

Starting with the pioneering work by Angluin [START_REF] Angluin | Local and Global Properties in Networks of Processors[END_REF], covering spaces have been used to derive impossibility results in anonymous networks, but only in the 1-dimensional case of graph coverings. Sufficient and sometimes necessary conditions on the communication graph and on the initial common knowledge for solving fundamental distributed problems such as leader election or termination detection are given in, e.g., [START_REF] Angluin | Local and Global Properties in Networks of Processors[END_REF][START_REF] Chalopin | On the Power of Synchronization Between two Adjacent Processes[END_REF][START_REF] Mazurkiewicz | Distributed Enumeration[END_REF][START_REF] Chalopin | Local Terminations and Distributed Computability in Anonymous Networks[END_REF], under several models of local computation. See [START_REF] Chalopin | On the Power of Synchronization Between two Adjacent Processes[END_REF] for an introduction to local computation in anonymous networks.

One can roughly classify the methods for ensuring the correctness of a program as either verifying, testing, or checking. Unlike verifying and testing, checking is performed at run time. A sequential checker [START_REF] Blum | Designing Programs that Check Their Work[END_REF] consists of a battery of tests (performed at run time) which compare the output of the program with either a predetermined value, or with a function of the outputs of the same program corresponding to different inputs. A similar idea is spot-checking [START_REF] Ergün | Spot-Checkers[END_REF] where the goal it to know if the output is reasonably correct, i.e., close in some problem-specific distance to the correct output. Related areas may be learning, where samples of outputs are used to infer the task it is being solved, as in [START_REF] Freund | Efficient Learning of Typical Finite Automata from Random Walks[END_REF] and property testing [START_REF] Goldreich | Property Testing and its Connection to Learning and Approximation[END_REF]. Blum et al. [START_REF] Blum | Self-Testing/Correcting with Applications to Numerical Problems[END_REF] introduced the notion of program testers and correctors, see also [START_REF] Goldwasser | A (De)constructive Approach to Program Checking[END_REF][START_REF] Lipton | New Directions in Testing[END_REF].

In the parallel and/or distributed computing context, the results are not so advanced as in the sequential setting. Parallel program checking has been studied in the PRAM model [START_REF] Rubinfeld | Designing Checkers for Programs that Run in Parallel[END_REF]. In the synchronous model, distributed self-testing and correcting protocols that tolerate crash failures are presented for the byzantine generals task in [START_REF] Franklin | Self-Testing/Correcting Protocols[END_REF]. Self-testing/correcting is reminiscent of the notion of checking as a means of making a distributed algorithm self-stabilizing, as explored in [START_REF] Awerbuch | Self-stabilization by Local Checking and Correction[END_REF][START_REF] Awerbuch | Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols[END_REF] in the synchronous setting. In the framework of network computing, distributed verification has been addressed only recently (see, e.g., [START_REF] Sarma | Distributed Verification and Hardness of Distributed Approximation 43rd[END_REF]), though previous research on proof labeling schemes [START_REF] Korman | Proof Labeling Schemes[END_REF] already gave some insights on the ability of checking global predicates locally (see also the recent paper [START_REF] Goos | Locally checkable proofs[END_REF]).

Organization

The paper is made up of 4 sections. Section 2 presents the wait-free distributed computing model computing, and recalls the notion of tasks. Our first locality condition, namely projection-closeness, and its relation with wait-free checking is explored in Section 3. Our structural results on the computational power of locality-preserving tasks are presented in Section 4.

Model

We consider a standard read/write shared memory wait-free model. The system consists of n asynchronous processes, denoted by the integers in [n] = {1, . . . , n}. The processes can fail by crashing (a crashed process never recovers). Any number of processes can crash, at any time. We recall here the main features of this model, and refer to [START_REF] Attiya | Distributed Computing: Fundamentals, Simulations, and Advanced Topics[END_REF][START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF][START_REF] Lynch | Distributed Algorithms[END_REF] for a more detailed and accurate description.

The processes that take an infinite number of steps in a run are correct, the others crashed. If a process crashes initially, it does not take any step, and we say it does not participate in the run. A process participates in a run if it takes at least one step. At the core of the model is the following assumption. We enforce protocols to be wait-free, that is to avoid all instructions that would cause a process to wait for the result of the action of another process. In particular, in a wait-free protocol, a process i cannot check whether another process has crashed, or is just very slow.

When solving a task, in each run of a protocol, processes start with private input values. A process i ∈ [n] is not aware of the inputs of other processes. The initial states of the processes differ only in their input values. Each process i has to eventually decide irrevocably on a value. Consider a run r where only a subset of k processes participate, 1 ≤ k ≤ n. These processes have distinct identities {id 1 , . . . , id k }, where for every

i ∈ [k], id i ∈ [n]. A set s = {(id 1 , x 1 ), . . . , (id k , x k )},
is used to denote the input values or decision values in the run, where x i denotes the value of the process with identity id i (either an input value, or a decision value). We denote by ID(s) the set of identities of the processes in s, i.e., ID(s) = {id 1 , . . . , id k }. The input values of processes not in ID(s) are irrelevant, as they do not participate in the run, so they are not included in s.

Let s ′ be a subset of s = {(1, x 1 ), . . . , (n, x n )}, ID(s) = [n]. We say that π(s) = s ′ , for a projection π, that eliminates processes in ID(s) \ ID(s ′ ). Because any number of processes can crash, all such subsets s ′ of s are of interest, to consider runs where only processes in ID(s ′ ) may participate. That is, the set of possible input sets forms a complex because its sets are closed under containment. Similarly, the set of possible output sets also form a complex. Following the topology notation, the sets of a complex are called simplexes.

More formally, a complex K is a set of vertices V (K), and a family of finite, nonempty subsets of V (K), called simplexes, satisfying: (i) if v ∈ V (K) then {v} is a simplex, and (ii) if s is a simplex, so is every nonempty subset of s. The dimension of a simplex s is |s| -1, the dimension of K is the largest dimension of its simplexes, and K is pure of dimension k if every simplex belongs to a k-dimensional simplex. A 1-dimensional complex K is thus simply a graph2 . In distributed computing, one refers to colored simplexes (and complexes), since each vertex v of a simplex is labeled with a distinct process identity i ∈ [n].

We denote by I the input complex, and by O the output complex. An input-output pair is a pair (s, t) made of a simplex s ∈ I and a simplex t ∈ O, with ID(t) ⊆ ID(s). The strict inclusion ID(t) ⊂ ID(s) takes into account the case when the processes in ID(s) \ ID(t) fail, and do not decide, which, in the wait-free model, should not prevent the participating non-failing processes to decide. A task T is described by a triple (I, O, ∆) where I and O are pure (n -1)-dimensional complexes, and ∆ is a map from I to the set of non-empty sub-complexes of O, satisfying (s, t) is an input-output pair for every t ∈ ∆(s). Intuitively, ∆ specifies, for every simplex s ∈ I, the valid outputs for the processes in ID(s) that may participate in the computation. We assume that ∆ is (sequentially) computable.

A protocol A solves task T = (I, O, ∆) if, for every simplex s ∈ I, and every run r of A on s, every correct process decides, and the simplex t corresponding to these decisions belongs to ∆(s).

Projection-closeness and wait-free checkability

This section addresses the first of the two notions of locality tackled in this paper. The locality considered here is obtained by simply reversing the direction of the inclusion in the monotony condition of Eq. 1.

Definition 3.1 A task T = (I, O, ∆) is projection-closed if and only if for every s ∈ I and every projection π, we have π(∆(s)) ⊆ ∆(π(s)).

Projection-closeness is as poorly related to wait-free solvability as is the intersection-closeness notion of Eq. 2. Consider for example, approximate agreement [START_REF] Dolev | Reaching Approximate Agreement in the Presence of Faults[END_REF] for two processes, illustrated in Fig. 4a. While it is wait-free solvable, it is not projection-closed. Intuitively, because the validity requirement in dimension 0 "if a process runs solo, has to decide its own value" conflicts with the agreement requirement in dimension 1 "when processes start with different values, they can decide any values, as long as they are at most 1/2 apart from each other." More precisely, take the input simplex s = {(1, 0), (2, 1)} (top edge labeled a in the figure), and apply the projection π that eliminates process 2, to obtain π(∆(s)) which consists of all vertices for process 1 in the output complex, while ∆(π(s)) consists of only vertex t = {(1, 0)}. Notice that for the same reason, consensus is also not projection-closed; in contrast, consensus is not wait-free solvable. Instead, projection-closeness is well related to checking the result of a computation supposedly solving a task T = (I, O, ∆). Intuitively, processes get as inputs the vertices of s, t, s ∈ I, t ∈ O, and want to decide if indeed the computation of t for s was correct, namely, if t ∈ ∆(s). That is, each process i gets as input a pair (x i , y i ), such that the x i values define s, while the y i values define t. Then, checking T corresponds to solving a checking task T c :

• If t ∈ ∆(s) then all processes that decide must output 1, interpreted as "yes".

• If t / ∈ ∆(s) then whenever all participating processes decide, one of them must output 0, interpreted as "no". When not all participating processes decide, then some may decide 1 and others 0. Formally, T c = (I × O, S n , ∆ c ). The input complex I × O consists of all simplexes s × t, s ∈ I, t ∈ O, ID(s) = ID(t), where, for every i ∈

[n], (i, (x i , y i )) ∈ s × t ⇐⇒ (i, x i ) ∈ s (i, y i ) ∈ t
The output complex S n consists of all simplexes where processes decide values in {0, 1}. Now, to define ∆ c , let S J be the sub-complex of S n induced by the processes in J, for J ⊆ [n]. In other words, S J = π(S n ) where π is the projection from [n] to J. Also, for J ⊆ [n], let Y [J] = {(i, 1), i ∈ J} be the simplex corresponding to all processes in J outputting "yes", and let Y [J] be the complex induced by Y [J]. We have now all the ingredients to define ∆ c . For any s × t ∈ I × O with ID(s) = ID(t) = J,

∆ c s × t = Y [J] if t ∈ ∆(s) S J \ Y [J] otherwise.
We now define wait-free checkability as follows:

Definition 3.2 A task T is wait-free checkable if and only if its corresponding task T c is wait-free solvable.

The following states the exact correspondence between projection-closeness and wait-free checkability.

Theorem 3.3 A task T is wait-free checkable if and only if it is projection-closed.

Proof. Let T = (I, O, ∆) be a task, and assume that T is projection-closed. We describe a wait-free algorithm that checks T . The algorithm starts with input s × t ∈ I × O and decides whether t ∈ ∆(s). More precisely, each participating process i ∈ J = ID(s) is given a pair (s i , t i ), and the algorithm proceeds at each process i in three atomic steps:

1. write (i, (s i , t i )) in memory; 2. read memory, to get s ′ × t ′ ; 3. if t ′ ∈ ∆(s ′ ) then output "yes", otherwise output "no".

Before proving the correctness of this algorithm, notice that the simplex s ′ × t ′ obtained by process i after the read instruction is a subset of s × t; namely the union of all the inputs of processes which wrote in memory before the read of process i occurs. So, s ′ × t ′ = π(s) × π(t) for some projection π. Also, observe that the third instruction of the algorithm is computable: process i can decide whether t ′ ∈ ∆(s ′ ) as we are dealing solely with input-output relations ∆ that are sequentially computable.

We now prove the correctness of the algorithm. Assume first that t ∈ ∆(s). Then

t ′ = π(t) ∈ π(∆(s)) ⊆ ∆(π(s)) = ∆(s ′ )
where the inclusion is due to the fact that T is projection-closed. Therefore, process i outputs "yes". Hence, all participating processes which decide output "yes", that is, the global output of the set of non-faulty participating processes belongs to Y [J], as desired. Assume now that t / ∈ ∆(s). If k < |J| processes decide, then whatever are the outputs of these processes, the corresponding output simplex is in S J \ Y [J], as desired. If all the processes in J decide, that is if all participating processes experienced no crashes, then let i be the identity of the process that reads memory the last among all participating processes. Process i reads the entire input (s, t), that is (s ′ , t ′ ) = (s, t). Therefore, this process detects that s ′ / ∈ ∆(t ′ ), and thus it outputs "no", as desired. Therefore, a projection-closed task is wait-free checkable.

Let us now consider a wait-free checkable task T = (I, O, ∆), and assume, for the purpose of contradiction, that T is not projection-closed. So, there must exist a simplex s ∈ I, and a projection π such that π(∆(s)) ⊆ ∆(π(s)). Hence, let t ′ ∈ π(∆(s)) \ ∆(π(s)), and let t ∈ ∆(s) such that π(t) = t ′ . Let s ′ = π(s). We have s ′ × t ′ = π(s × t) in the complex I × O. Let J = ID(s × t), and J ′ = ID(s ′ × t ′ ). On the one hand, we have

∆ c (π(s × t)) = ∆ c (s ′ × t ′ ) = S J ′ \ Y [J ′ ] because t ′ / ∈ ∆(s ′ ).
On the other hand, we have

∆ c (s × t) = Y [J] because t ∈ ∆(s). Therefore, ∆ c (π(s × t)) ⊆ ∆ c (s × t), and thus ∆ c (π(s × t)) ⊆ π(∆ c (s × t)). We do not necessarily have ∆ c (π(s × t)) ∩ π(∆ c (s × t)) = ∅ though, because S J ′ \ Y [J ′ ] contains (|J ′ | -2)-
dimensional simplexes with values 1. Nevertheless, if one restricts our consideration to the skeleton

Q of S J ′ \ Y [J ′ ] consisting of all its simplexes of dimension |J ′ | -1, we do have Q ∩ Y [J] = ∅.
Thus, by a reasoning identical to the one showing that the intersection-closeness property is a necessary condition for wait-free solvability, we get that T c is not wait-free solvable, which contradicts the fact that T is wait-free checkable.

We now prove that the set of wait-free checkable tasks, or, equivalently, the set of projectionclosed tasks, forms a large class of tasks.

Theorem 3.4 Determining whether a wait-free checkable task is wait-free solvable is undecidable.

To establish the theorem, we show that every task is essentially equivalent to a wait-free checkable task, under a very strong notion of equivalence. Following [START_REF] Herlihy | A Classification of Wait-Free Loop Agreement Tasks[END_REF], a task T ′ implements task T (both defined on n processes) if one can construct a wait-free protocol for T by calling one instance of a black box for T ′ followed by any number of operations on read-write registers 3 . We write T ≤ T ′ to emphasize that T ′ is at least as powerful as T . In Section 4.3 we use this implementation, while for the theorem here, it suffices to use its particular case where no operations on read-write registers are used; namely, if there exists a wait-free protocol A that solves T , in which processes can call one instance of a black box that solves T ′ , and do not execute any read-write operations: Definition 3.5 We say T ≤ T ′ if task T ′ implements task T , and T T ′ if there is an implementation without executing any read-write operations.

Based on Definition 3.5, one can define the following equivalence relation ∼ between tasks T ∼ T ′ ⇐⇒ (T T ′ and T ′ T ) . This equivalence notion is the key ingredient in the proof of Theorem 3.4 below. First consider as an example consensus, which as mentioned above, is not wait-free checkable. However, consensus is equivalent to the checkable consensus task, depicted in Figure 4b for two processes. This task is obtained from consensus, by adding new input and output values 2, 3, 4, 5, and then allowing for processes running solo on inputs 0, 1, to decide any value (but when a process starts with 2, 3, 4 or 5 it decides its own input always). Proof of Theorem 3.4 We first show that, for every task T , there exists a task T ′ that is waitfree checkable and T ′ ∼ T . Let T = (I, O, ∆) be a task. We construct a wait-free checkable task T ′ = (I ′ , O ′ , ∆ ′ ) and show that T ∼ T ′ . The construction proceeds in two phases, the completion phase and the projection phase.

The completion phase proceeds as follows. We constructs two intermediate sets I med , O med and a relation ∆ med ⊆ I med ×O med . Let V a set of values such that each element of v is not a valid input for T and |V | = |I|. More formally, for each s ∈ I and each (i,

x i ) ∈ s, x i / ∈ V . Let v * : I → V a one-to-one function. For s ∈ I (resp. O) and v ∈ V , let c(s, v) = s ∪ {(i, v), i ∈ [n] \ ID(s)
} the set obtained by replacing each missing entry of s with the value v. We first "complete" each input set s ∈ I with the value v * (s). Two distinct input sets s, s ′ ∈ I are thus completed with distinct values v * (s) = v * (s ′ ). Let I med be the set of input sets completed in this way, i.e.,

I med = {c(s, v * (s)), s ∈ I}.
Output sets are completed in a similar way. Given an output set t ∈ O, multiple completed sets may however be formed. More precisely, for each input set s ∈ I such that t ∈ ∆(s), O med includes the completed set c(t, v * (s)) whenever t is a valid output for input s and ID(s) = ID(t):

O med = {c(t, v * (s)), t ∈ ∆(s) and ID(s) = ID(t)}.
Let σ, τ two completed input and output sets respectively. We set τ ∈ ∆ med (σ) if and only if their respective antecedent s and t before completion form an input-output pair for T . That is, for every σ × τ ∈ I med × O med we set τ ∈ ∆ med (σ) if and only if:

∃s × t ∈ I × O with t ∈ ∆(s) and ID(s) = ID(t) such that σ × τ = c(s, v * (s)) × c(t, v * (s)).
We now describe the projection phase. The task (I med , O med , ∆ med ) defined so far is clearly not wait-free solvable as it is even not defined when not every process participates. For each input set σ ∈ I med (resp. ∈ O med ), and each projection map π, the set π(σ) is included in I ′ (resp. O ′ ):

I ′ = π π(I med ) and O ′ = π π(O med )
Similarly, ∆ ′ is the union over every projection map of the relation ∆ med . For every

s ′ ∈ I ′ , we define ∆ ′ (s ′ ) = π,σ:π(σ)⊆s ′ π(∆ med (σ)).
Let us show that T ′ = (I ′ , O ′ , ∆ ′ ) is wait-free checkable. Let s ∈ I ′ and µ a projection. By definition of ∆ ′ , we get

µ(∆ ′ (s)) = π,σ:π(σ)⊆s µ(π(∆ med (σ))) = π ′ ,σ:π ′ (σ)⊆µ(s) π ′ (∆ med (σ)) = ∆ ′ (µ(s)).
Therefore, T ′ is projection-closed, and thus it is wait-free checkable in view of Theorem 3.3. We now prove that T ∼ T ′ . Let us first prove that T ′ T . Suppose that a black box A that solves T is given. We describe a wait-free algorithm A ′ to solve T ′ . A process p i that wakes up with input x i first checks whether there exists an input set s ∈ I such that (i, x i ) ∈ s. If such an input set is found, p i invokes A with input x i and decides the value returned. Otherwise, p i decides x i . Consider an execution of A ′ with input s ′ ∈ I ′ and output t ′ . s ′ is the projection of a set s ∈ I after it has been completed, i.e., s ′ = π(c(s, v * (s))) where π is a projection map. As the value v * (s) is not included in any input set of I, the inputs of the processes that invoke algorithm A form a set s 1 ⊆ s. Each other process fails or has v * (s) as input. As I is closed under containment, s 1 ∈ I. Therefore, as A solves T , the outputs of the processes that invoke A form a set t 1 ∈ ∆(s 1 ). By the monotony condition, there exits an output set t ⊇ t 1 such that t ∈ ∆(s) and ID(s) = ID(t). Therefore, in the completing phase of the construction, σ × τ , with σ = c(s, v * (s)), τ = c(t, v * (s)) is added as an input-output pair for ∆ med . Let p i be a process that decides and y i its decided value. If p i decides after invoking A, (i, y i ) ∈ t. Otherwise, p i decides v * (s) and (i, y i ) / ∈ t. Therefore, t ′ = µ(τ ) for some projection map µ. Recall that we also have s ′ = π(σ), where π is a projection map. Clearly, ID(t ′ ) ⊆ ID(s ′ ), and thus µ(σ) ⊆ s ′ . To summarize, τ ∈ ∆ med (σ) and hence

t ′ = µ(τ ) ∈ µ(∆ med (σ)). As µ(σ) ⊆ s ′ , it follows from the definition of ∆ ′ that t ′ ∈ ∆ ′ (s ′ ).
We now prove that T T ′ . Suppose now that we are given a black box algorithm A ′ that solves T ′ . We show that A ′ also solves T . Fix an execution e of A ′ with input s ∈ I. Let t ∈ ∆ ′ (s) the output set of this execution. Let e 1 a finite prefix of e in which every process that decides in e has decided. Note that the identities of these processes is ID(t). Execution e 2 extends e 1 . The input set of e 2 is σ = c(s, v * (s)): after each process p i , i ∈ ID(t) has decided, every process p j , j ∈ [n] \ ID(t) wakes up with input v * (s). Moreover, every process decides in e 2 . Let τ ∈ ∆ ′ (σ) the output set. e 2 is a legal extension of e 1 , as processes may be arbitrarily slow. Also, when the processes p j , j ∈ ID(t) decide in e 2 , the execution is indistinguishable from e, which implies that τ ⊇ t. As τ ∈ ∆ ′ (σ) and ID(σ) = ID(τ ) = [n], σ × τ is an input-output pair of ∆ med . Therefore, τ is the completion of some set t ′ ∈ O with value v * (s) (τ = c(t ′ , v * (s))) and we have ID(t ′ ) = ID(s) and t ′ ∈ ∆(s). To conclude, we note that t ′ ⊇ t. Since t ∈ ∆(s), this implies that t ′ ∈ ∆(s).

This completes the proof of the fact that for every task, there exists an equivalent task that is wait-free checkable. Since determining whether a task is wait-free solvable is undecidable [START_REF] Gafni | Three-Processor Tasks Are Undecidable[END_REF][START_REF] Herlihy | The Decidability of Distributed Decision Tasks[END_REF], the theorem follows.

Preliminaries

For two complexes K and K ′ , a map f : K → K ′ is a function f : V (K) → V (K ′ ) such that whenever s = {v 0 , . . . , v q } is a simplex in K, then f (s) = {f (v 0 ), . . . , f (v q )} is a simplex in K ′ . The map is color-preserving if it preserves ids, that is, for each v ∈ V (K), ID(f (v)) = id(v). Hence, if the map is color preserving, and f (s) = s ′ , then dim(s) = dim(s ′ ). An edge e in a complex K is an ordered pair of (not necessarily) distinct vertices e = (u, v), where {u, v} is a simplex in K. The origin and end of e = (u, v) are respectively denoted orig(e) = u and end(e) = v. A path α in K is a finite sequence of edges α = e 1 • e 2 • • • • • e k , where end(e i ) = orig(e i+1 ). The path α is closed at u if orig(α) = orig(e 1 ) = u = end(e k ) = end(α). A complex K is connected if for every pair of vertices u, v in K, there is a path from u to v. A covering complex [START_REF] Rotman | Covering Complexes with Applications to Algebra[END_REF] is the discrete analogue of a covering space. The notion of covering complex formalizes the idea of one complex looking identically to another locally. Its definition is recalled below (see [START_REF] Rotman | Covering Complexes with Applications to Algebra[END_REF]): Definition 4.1 A pair ( K, p) is a covering complex of a complex K if and only if the following three properties are satisfied:

1. p : K → K is a map; 2. K is connected;
3. for every simplex s in K, p -1 (s) is a union of pairwise disjoint simplexes, p -1 (s) = ∪s i , with p|s i : si → s a one-one correspondence for each i.

The simplexes si are called the sheets over s. We often refer to p as a covering map. Next observations easily follow from the definition of covering complexes: K = im(p), and hence, K is connected. If s is a q-simplex in K, each sheet si over s is also a q-simplex. For each vertex v in K, the complex star(v) consists of all simplexes that contain v. One can check that K and K are locally isomorphic in the sense that if ṽ is such that p(ṽ) = v, then star(v) is isomorphic to star(ṽ).

Let T = (I, O, ∆) be a task. In the following, we assume that the output complex is connected (otherwise, our analysis can be done on each connected component), and that O does not contain irrelevant simplexes. That is, for each t ∈ O, there exists s ∈ I such that t ∈ ∆(s). Let p : O → I covering map. We say that p agrees with ∆ if p(s) = s ⇐⇒ ID(s) = ID(s) ∧ s ∈ ∆(s), for every s ∈ I, s ∈ O. In particular, p is color-preserving. Definition 4.2 A task T = (I, O, ∆) is locality-preserving if and only if there exists a covering complex (O, p) of I, with a map p that agrees with ∆.

Examples of locality-preserving tasks are depicted in Figures 3,5 and6, where the color of a vertex (black or white) represents its identity. Instead of adding input and output values to vertexes, labels are added to edges, which is sufficient to specify ∆, as the tasks are both monotone and projection-closed. For example, in Figure 3, the edge labeled a on the left side represents an input simplex. This input simplex is mapped by ∆ to a set of two output simplexes, namely the two edges labeled a on the right side of the picture. In these tasks, the outputs look like the inputs, locally. For example, in Figure 3, the top left corner formed by the white vertex (with the two edges labeled a and b) is mapped by ∆ to the two opposite corners that look the same locally.

Characterization

Recall that task T = (I, O, ∆) is said to be monotone when ∆(π(s)) ⊆ π(∆(s)) for every s ∈ I, and any projection π. In other words, for any t ′ ∈ ∆(π(s)), there exists t ∈ ∆(s) such that π(t) = t ′ . We say that T is strongly monotone if, for every s ∈ I, any projection π, and any t ′ ∈ ∆(π(s)), there exists a unique t ∈ ∆(s) such that π(t) = t ′ . So, intuitively, a task that is strongly monotone permits to extend any partial output in a unique manner. In order to characterize locality-preserving, we say that a task T is one-to-one if and only if, for every pair (s, s ′ ), s = s ′ of 0-dimensional simplexes in I, we have ∆(s) ∩ ∆(s ′ ) = ∅.

Theorem 4.3 A task T is locality-preserving if and only if T is projection-closed, one-to-one, and strongly monotone.

Proof. Let T = (I, O, ∆) be a projection-closed, one-to-one and strongly monotone task. We define a map p : O → I and show that p is a covering map. Let ṽ ∈ V (O). As we assume that O has no irrelevant simplex, there exists v ∈ V (I) such that {ṽ} ∈ ∆({v}). Moreover, v is unique. Indeed, if {ṽ} ∈ ∆({v ′ }) for some v ′ ∈ V (I), we get ∆({v}) ∩ ∆({v ′ }) ⊇ {ṽ} = ∅, which contradicts the hypothesis that T is one-to-one. Therefore, we define for each ṽ ∈ O p(ṽ) = v, where v is the unique vertex in V (I) such that {ṽ} ∈ ∆({v}).

To see that p is a map, let s = {ṽ 1 , . . . , ṽm } ∈ O. By the no irrelevant output simplex assumption, s ∈ ∆(s) for some simplex s = {v 1 , . . . , v m } ∈ I. Since task T is projection-closed, {ṽ i } ∈ ∆({v i }). We know however that for every ṽ ∈ V (O), there is a unique v = p(ṽ) ∈ I such that {ṽ} ∈ ∆({v}). Therefore, p(s) = {p(ṽ 1 ), . . . , p(ṽ m )} = s ∈ I and p is a map. This also shows that p agrees with ∆, since s ∈ ∆(p(s)). This establishes that p satisfies Definition 4.1 [START_REF] Angluin | Local and Global Properties in Networks of Processors[END_REF]. As O is connected by assumption, Definition 4.1(2) is satisfied as well.

If s = p(s) for some simplex s ∈ O, clearly p|s : s → s is a one-one correspondence because p, agreeing with ∆, preserves colors. To prove that the inverse p -1 (s) is a union of pairwise disjoint simplexes, let s1 , s2 two simplexes ∈ p -1 (s). Assume that s1 and s2 have one vertex ṽ in common. Let v = p(ṽ) and π a projection such that π(s) = {v}. By definition of p, {ṽ} ∈ ∆({v}). Because T is strongly monotone, there exists a unique s ∈ ∆(s) such that π(s) = {ṽ}. As p agrees with ∆, and p( s1 ) = s, s1 ∈ ∆(s). Hence, as π(s 1 ) = {ṽ}, s1 = s. Similarly, s2 = s. Therefore s2 = s1 and we conclude that p -1 (s) is a disjoint union of pairwise simplexes, as required by Definition 4.1(3).

Reciprocally, assume T is locality-preserving. Let p : O → I be a covering map that agrees with ∆. The fact that T is one-to-one, strongly monotone and projection-closed mechanically follows from the properties of the covering map p. Let t ∈ O and s ∈ I.

• Projection-closed. Let π be a projection map, and suppose that t ∈ ∆(s). As p agrees with ∆, p(t) = s, and thus p(π(t))) = π(s). Using again the fact that p agrees with ∆, we have π(t) ∈ ∆(π(s)). Therefore π(∆(s)) ⊆ ∆(π(s)).

• T is one-to-one. Let v ∈ V (I). The fact that p agrees with ∆ implies that ∆({v}) = p -1 (v). Therefore, for every v = v ′ ∈ V (I), ∆({v}) ∩ ∆({v ′ }) = ∅.

• Strong monotony. Let t, t 1 , t 2 ∈ O and π a projection satisfying t = π(t 1 ) = π(t 2 ). Assume that t ∈ ∆(π(s)) and t 1 , t 2 ∈ ∆(s). As p agrees with ∆, p(t 1 ) = p(t 2 ) = s. Therefore, as p -1 (s) is a disjoint union of simplexes, and t 1 ∩ t 2 = ∅, t 1 = t 2 . So there exists a unique t ′ , π(t ′ ) = t and t ′ ∈ ∆(s).

The fact that T satisfies the above three properties completes the proof.

As every projection-closed task is wait-free checkable (Theorem 3.3), we get the following.

Corollary 4.4 Every locality-preserving task is wait-free checkable.

As demonstrated by the next corollary, few locality-preserving tasks are wait-free solvable. For an input complex I, the identity task T Id,I = (I, I, ∆) over I simply requires that each process decides its input in every execution: ∀s ∈ I, ∆(s) = {s}. More generally, we say that a task is an identity task by having each process output a function of its input, without any shared memory operations. Identity tasks with input I are the tasks equivalent to T Id,I for the ∼ relation. Proof. Let T be a wait-free solvable and locality-preserving task, with covering map p. By the Asynchronous Computability Theorem [START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF], there exists subdivision I * of I and a color preserving map δ : I * → O that agrees with ∆. More precisely, a simplex s * ∈ I * is obtained by subdividing a simplex s ∈ I with ID(s) = ID(s * ), called the carrier of s * . δ agrees with ∆ means that for every s * ∈ I * , δ(s * ) ∈ ∆(carrier(s * )).

We show that every simplex in I * with the same carrier are mapped by δ to the same simplex. Let s * , s * ′ ∈ I * two intersecting simplexes with the same carrier s. We have δ(s * ) ∩ δ(s * ′ ) = ∅. As δ agrees with ∆, and s * , s * ′ have the same carrier s, δ(s * ) and δ(s * ′ ) ∈ ∆(s). Moreover, the set of simplexes t ∈ ∆(s) with ID(t) = ID(s) coincides with p -1 (s). This is because the covering map p of T agrees with ∆. By definition 4.1(3), p -1 (s) is a disjoint union of simplexes. Therefore, δ(s * ) = δ(s * ′ ) since they intersect. Two non-intersecting simplexes s * and s * ′ with the same carrier s are connected by a chain s * 1 (= s * ), . . . , s * m (= s * ′ ) where carrier(s * i ) = s and every two consecutive simplexes intersect. By repeating the same reasoning over the chain, we obtain also that δ(s * ) = δ(s * ′ ).

Consequently, we can consider without loss of generality that the subdivision is trivial and δ is thus a map from I to O that agrees with ∆: for each s ∈ I, δ(s) ∈ ∆(s). Therefore, the trivial algorithm in which each process decides the value return by applying δ to its output solves T , which proves that T is an identity task.

Figure 2 :

 2 Figure 2: The universe of tasks

Figure 3 :

 3 Figure 3: Two-cover task. The task is for two processes, which start with binary inputs. On the left side

Figure 4 :

 4 Figure 4: Two tasks for 2 processes.

Figure 5 :

 5 Figure 5: Four cover task

Corollary 4 . 5

 45 The identity tasks are the only locality-preserving task that are wait-free solvable.

Figure 6 Figure 7 :

 67 Figure 6: Locality-preserving tasks

  The task is for two processes, which start with binary inputs. On the left side of the figure, the specification of the task says that if both start with the same value, they must decide the same value: if they start with 0, decide either 0 or 2; if they start with 1, decide 1 or 3. If they start with different values, the valid outputs are defined in the figure, via edge labels a, b, c, or d. The relation ∆ defines also the possible outputs when only one process runs solo: e.g., when the white process starts with 0, it can decide 0 or 2, while if it starts with 1, it can decide 1 or 3. Notice that O, a cycle of length 8, locally looks like I, a cycle of length 4, in the sense that the 1-neighborhood of each vertex v in I is identical to the 1-neighborhood of a corresponding vertex in ∆(v). In the right side of the figure it is shown how O covers I, by wrapping around it twice, where p identifies edges with the same label.

	subclass of these tasks, that offers a stronger notion of locality expressible in the framework of
	algebraic topology. A task T = (I, O, ∆) is said to be locality-preserving if and only if O is a
	covering complex of I, that is there exists a map p : O → I which agrees with ∆, i.e.,
	∃p : O → I | ∀t ∈ O, t ∈ ∆(p(t)).

It is the graph whose nodes are the vertices of K, and whose edges and nodes are the simplexes of K. More generally, the concept of complexes is, in some sense, a natural extension of the concept of graphs, to higher dimensions. They can also be viewed as forming a subclass of hypergraphs, in which every non-empty subset of an hyperedge must be an hyperedge.

A more general notion of implementation allows read-write operations before calling the black box, and calling the black box more than once.

Locality-preserving tasksIn this section, we turn our attention to locality-preserving tasks, which are both monotone and projection-closed (see Fig.2) and preserve locality in a strong, topological sense. Before defining the class, we need to recall some simple topology facts.

Acknowledgments. We thank Marcelo Aguilar and Javier Bracho for helpful discussions on covering spaces.

* Supported in part by a CONACYT-CNRS grant † Additional supports from the ANR projects ALADDIN and PROSE, and from the INRIA project GANG. ‡ Additional supports from UNAM-PAPIIT and PAPIME. § Work done in part in U. Pierre et Marie Curie. Additional supports from ANR project SPREAD.

Hierarchies of locality-preserving tasks

In this section we classify the locality-preserving tasks in term of their relative computing power, that is in their capacity of mutual implementation (Definition 3.5). For the remaining of this section, we fix an arbitrary input complex I and study the relative power of locality-preserving tasks with input I. We establish that each such locality-preserving task induces subgroups of a group defined from the closed paths in I. Moreover, the relative power of locality-preserving tasks with input I directly depends on the subgroups they induce.

Edgepath groups and locality-preserving tasks

Our exposition follows Rotman [START_REF] Rotman | Covering Complexes with Applications to Algebra[END_REF]. Let K a complex and v * ∈ V (K). The edgepath group of K with basepoint v * is G(K, v * ) = {[α] : α is a closed path at v * }. [α] consists of the equivalence class of closed paths α ′ that can be deformed to α along 2-simplexes. More precisely, the paths α ′ and α are equivalent if one can be obtained from the other by applying the following rule a finite number of times: replace (u, v)

1 and each e -1 i is the edge obtained by reversing the end and origin of e i . The identity element is [(v * , v * )]. If K is connected, changing the basepoint results in an isomorphic group ([38], Theorem 1.4).

Covering complexes of K induce subgroups of the edgepath group of K. Conversely, every subgroup of the edgepath group is induced by a covering complex. Formally, the notation of a covering complex is extended to pointed complexes. p : ( K, ṽ * ) → (K, v * ) is a covering complex when ( K, p) is a covering complex of K, and p(ṽ * ) = v * . Each covering complex p : ( K, ṽ * ) → (K, v * ) determines a subgroup of G(K, v * ), namely, p # (G( K, ṽ * )), where p # is the homomorphism induced by p, which is one-to-one ( [START_REF] Rotman | Covering Complexes with Applications to Algebra[END_REF], Theorem 2.3). Let H = p # (G( K, ṽ * )). Keeping p unchanged but choosing a different basepoint ṽ′ * ∈ K such that p(ṽ ′ * ) = p(ṽ * ) = v * may induce a different subgroup H ′ = p # (G( K, ṽ′ * )). H and H ′ are however conjugate subgroups of G(K, v * ). Conversely, if H ′ is conjugate to H then H ′ = p # (G( K, ũ)) for some ũ ∈ V ( K) ( [START_REF] Rotman | Covering Complexes with Applications to Algebra[END_REF], Theorem 2.4). Finally, let p : ( K, ṽ * ) → (K, v * ) and q : ( J, w * ) → (K, v * ) two covering complexes of (K, v * ) and H(= p # (G( K, ṽ * ))), H ′ (= q # (G( J, w * ))) the induced subgroups. If H ′ ⊆ H, there exists a unique map r : ( J, w * ) → ( K, ṽ * ) such that pr = q. Moreover, r : ( J, w * ) → ( K, ṽ * ) is a covering complex ( [START_REF] Rotman | Covering Complexes with Applications to Algebra[END_REF], Theorem 3.3). In particular, when H = H ′ , r is an isomorphism.

On the other hand, for every subgroup H of G(K, v * ) there exists a connected complex K H and a map p such that p : (K H , ṽ * ) → (K, v * ) is a covering complex for some ṽ * ∈ V (K H ) and p # (K H , ṽ * ) = H ([38], Theorem 2.8). In particular, the trivial group {[(v * , v * )]} that consists in the identity element is a subgroup of any subgroup, and the corresponding covering complex p : (K u , ṽ * ) → (K, v * ) is called the universal covering of K, because it covers any other covering of K. For example, Figure 6b depicts the universal covering for the complex on the left. A simplex of the complex on the right is sent to the simplex with the same label in the left complex by the universal covering map. The universal covering complex is simply connected since p # is one-to-one and p # (G(K u , ṽ * )) = {1}.

By definition, each locality-preserving task T = (I, O, ∆) determines a covering complex p : O → I and conversely, a covering complex p : O → I defines a locality-preserving task with input I. It thus follows from the discussion above that every locality-preserving task with input I induces subgroups of the edgepath group of I, and reciprocally each subgroup induces a locality-preserving task. This is captured by the next lemma. for some ṽ * ∈ V (O), where p is the covering map associated with T .

Then, Theorem 3.3 in [START_REF] Rotman | Covering Complexes with Applications to Algebra[END_REF] discussed earlier implies the following result.

Group-based hierarchies of locality-preserving tasks

We consider locality-preserving tasks that can be defined over a given input complex I. The following result explicits the existence of a hierarchy of locality-preserving tasks, using the implementation relation "≤" of Definition By Lemma 4.6(2), every locality-preserving task induces a conjugacy class.

Theorem 4.8 Let I be a connected complex. Let T K = (I, K, ∆ K ) and T L = (I, L, ∆ L ) be two locality-preserving tasks with input complex I. Let v * ∈ V (I) and C K and C L the conjugacy classes of subgroups of G(I, v * ) induced by T K and T L respectively.

Proof. We denote p : K → I (resp. q : L → I) the covering map corresponding to T K (resp. T L ). Let us assume that H K = p # (G(K, ũ)) ⊆ q # (G(L, ṽ)) = H L for some vertexes ũ ∈ V (K), ṽ ∈ V (L). We show that T L T K . By applying Lemma 4.7, we get that there exists a covering map r : K → L such that qr = p. Given a black box A K that solves T K , T L can be solved by the following protocol. Each process p i first invokes A K on its input and gets back an output o i . p i then decides r(o i ). Fix an execution of the protocol. Let s 1 , s 2 and s 3 the simplexes formed by the initial inputs of the process, the outputs resulting of the invocation of A K and the decision values respectively. As A K solves the locality-preserving task T K , p(s 2 ) = s 1 . Note that we also have s 3 = r(s 2 ), and hence q(s 3 ) = q(r(s 2 )) . Therefore, as qr = p, q(s 3 ) = p(s 2 ) = s 1 . By definition of locality-preserving tasks, q agrees with ∆ L , from which we conclude that the output simplex in the execution s 3 ∈ ∆ L (s 1 ) as desired.

Reciprocally, let us assume that T L ≤ T K . Thus, there is a wait-free protocol that solves T L invoking a black box that solves T K once, and then executing read-write operations. That is, starting with any input simplex s 1 ∈ I, processes invoke the protocol for T K , and get back as output a simplex s 2 ∈ K such that s 2 ∈ ∆ K (s 1 ), or equivalently p(s 2 ) = s 1 . Then the processes performs read/write operations, with s 2 as input before deciding on some output simplex s 3 ∈ L.

By the Asynchronous Computability Theorem [START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF], the read/write operations subdivide the input complex K, and the decisions define a map that goes from the subdivided complex to L.

More precisely, T K ≤ T L implies the existence of a chromatic subdivision σ of K and a colorpreserving map µ : σ(K) → L. Moreover, for every simplex s ∈ σ(s 2 ) with ID(s) = ID(s 2 ), we have µ(s) ∈ ∆ L (s 1 ) whenever s 2 ∈ ∆ K (s 1 ).

We prove that we can assume without loss of generality that the subdivision σ is trivial. Let s 2 ∈ K. By the no irrelevant output simplex assumption, s 2 ∈ ∆ K (s 1 ) for some simplex s 1 ∈ I. We show that there exists s 3 ∈ L such that for every s ∈ σ(s 2 ) with ID(s 2 ) = ID(s), µ(s) = s 3 . Therefore, we can assume that µ maps directly each simplex in K to simplexes in L. Let s, s ′ ∈ σ(s 2 ) with ID(s) = ID(s ′ ) = ID(s 2 ). Assume that s ∩ s ′ = ∅. Because µ is a map, µ(s) ∩ µ(s ′ ) = ∅. Moreover, µ(s), µ(s ′ ) ∈ ∆ L (s 1 ), or equivalently, µ(s), µ(s ′ ) ∈ q -1 (s 1 ). However, q -1 (s 1 ) is a disjoint union of simplexes (Definition 4.1(3)). Therefore, µ(s) = µ(s ′ ). If s, s ′ do not intersect, they are connected by a chain s 1 (= s), . . . , s m (= s ′ ) of simplexes in σ(s 2 ) in which every two consecutive simplexes intersect. Therefore, the same reasoning repeated over the chain implies that µ(s) = µ(s ′ ).

So let us assume that σ is the trivial subdivision. Let s 2 ∈ K. As mentioned above, s 2 ∈ ∆ K (s 1 ), or equivalently, p(s 2 ) = s 1 . Also, applying µ to s 2 results in a simplex ∈ ∆ L (s 1 ). Hence, q(µ(s 2 )) = s 1 = p(s 2 ), from which we have qµ = p.

We now prove that tasks T K and T L induce two subgroups related by containment. Let ũ ∈ K such that p(ũ) = v * and µ(ũ) = ṽ ∈ L. Note that q(ṽ) = q(µ(ũ)) = p(ũ) = v * . Let H K and H L the subgroups of G(I, v * ) defined by H K = p # (G(K, ũ)) and H L = q # (G(L, ṽ)). H K and H L are thus induced by T K and T L in the sense of Lemma 4.6. Let

We say that a task is universal for some set of tasks if it implements any task in that set (in the sense of "≤" in Definition 3.5). Theorem 4.8 implies that the set of locality-preserving tasks with input complex I has a universal task, which is the locality-preserving task defined by the universal covering of I. More generally, it shows that every locality-preserving task T = (I, O, ∆) lies in between the trivial task (I, O, ∆) and the task defined by the universal covering complex of I. This is illustrated in Figure 7, where the double cycle at the bottom represents the input complex I and the universal covering at the top defines a universal locality-preserving task T from the covering map p. The covering map p ′′ on the left defines another locality-preserving task T ′′ with input I. The trivial subgroup is induced by T , which is a subgroup of every subgroup induced by T ′′ . Therefore, we have T ′′ ≤ T . The complex at the top is also a covering of the complex on the left, with covering map p ′ , which in turn defines another locality-preserving task T ′ .