Carole Delporte-Gallet

Hugues Fauconnier

Sergio Rajsbaum
email: rajsbaum@math.unam.mx

Nayuta Yanagisawa
email: nayuta87@math.kyoto-u.ac.jp

A Characterization of t-Resilient Colorless Task Anonymous Solvability

Keywords: MWMR registers, Anonymity, Distributed task, Topology

One of the central questions in distributed computability is characterizing the tasks that are solvable in a given system model. In the anonymous case, where processes have no identifiers and communicate through multi-writer/multi-reader registers, there is a recent topological characterization (Yanagisawa 2017) of the colorless tasks that are solvable when any number of asynchronous processes may crash. In this paper, we consider the case where at most t asynchronous processes may crash, where 1 ≤ t < n. We prove that a colorless task is t-resilient solvable anonymously if and only if it is t-resilient solvable non-anonymously. We obtain our results through various reductions and simulations that explore how to extend techniques for non-anonymous computation to anonymous one.

Introduction

One of the central questions in distributed computability is characterizing the tasks which are solvable in a given system model. A task is the distributed equivalent of a function in sequential computing: each process starts with a private input value, communicates with other processes, and eventually decides an output value, such that the vector of output values is valid for the vector of input values according to the task specification.

The asynchronous computability theorem (ACT) [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF] is one of the central results in distributed computability. It characterizes the tasks that are solvable in shared-memory systems where n processes that may fail by crashing communicate by reading and writing shared registers. It is sometimes called the wait-free characterization, because any number of processes may crash and the processes are asynchronous (run at arbitrary speeds, independent from each other). The characterization is of an algebraic topological nature. In terms of algebraic topology, a task is represented as a relation ∆ between an input complex I and an output complex O. Each simplex σ in I is a set that specifies the initial inputs to the processes in some execution. The processes communicate with each other, and eventually decide output values that form a simplex τ in O. The computation is correct if τ is in ∆(σ). The complex I (resp. O) is chromatic because each simplex specifies not only input values, but also which process gets which input (resp. output) value. Roughly, the ACT characterization states that the task is solvable if and only if there is a chromatic simplicial map δ from a chromatic subdivision of I to O respecting ∆.

The ACT is the basis to obtain a characterization of distributed task computability in the case where at most t asynchronous processes may crash, where 1 ≤ t < n. It is also the basis to study other failure, timing, and communication models, and even mobile robot models [START_REF] Rajsbaum | Fault-tolerant robot gathering problems on graphs with arbitrary appearing times[END_REF]. There are basically two ways of extending the results from the wait-free model to other models. One is by directly generalizing the algorithmic and topological techniques, and the other is by reduction to other models using simulations (either algorithmic [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF] or topological [START_REF] Herlihy | Simulations and reductions for colorless tasks[END_REF]). An overview of results in this area can be found in the book [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF].

The theory of distributed computing presented in [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF] assumes that the processes, p 0 , . . . , p n-1 , communicate using single-writer/multi-reader (SWMR) registers, R 0 , . . . , R N -1 . Thus, p i knows that it is the i-th process and it can write exclusively to R i while the size of the namespace, N , is assumed to be much bigger than the number of the process, n. In this situation, preallocating a register for each identifier would lead to a distributed algorithm with a very large space complexity, namely N registers. Instead, it is shown in [START_REF] Delporte-Gallet | Linear space bootstrap communication schemes[END_REF] that n multi-writer/multi-reader (MWMR) registers are sufficient to solve any readwrite wait-free solvable task.

However, in some distributed systems, processes are anonymous; they have no ids at all or they cannot make use of their identifiers (e.g., due to privacy issues). In such a system, processes run identical programs, and the means by which processes access the shared memory are identical to all processes. A process cannot have a private register to which only this process may write, and hence the shared memory consists only of MWMR registers. This anonymous shared memory model of asynchronous distributed computing has been studied since early on [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF][START_REF] Jayanti | Wakeup under read/write atomicity[END_REF], in the case where processes do not fail.

In an anonymous system, colorless tasks are natural, because they are defined only in terms of input and output values without stating which process receives which input value or which process produces which output value. Furthermore, the class of colorless tasks includes various important tasks, such as consensus and set agreement, and is rich enough to be undecidable even for three processes [START_REF] Gafni | Three-processor tasks are undecidable[END_REF][START_REF] Herlihy | The decidability of distributed decision tasks (extended abstract)[END_REF].

Colorless tasks have been well studied in shared-memory and message passing models, where each process has a distinct identifier [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF], but less so in anonymous systems. Only recently, the ACT has been extended to the anonymous case [START_REF] Yanagisawa | Wait-free solvability of colorless tasks in anonymous sharedmemory model[END_REF], providing a characterization of wait-free anonymous computability of colorless tasks. The characterization implies that the anonymity does not reduce the computational power of the asynchronous shared-memory model as far as colorless tasks are concerned. In consequence, the topological characterization is in terms of input and output complexes which are not chromatic. Results Our main result is an extension of the wait-free characterization of [START_REF] Yanagisawa | Wait-free solvability of colorless tasks in anonymous sharedmemory model[END_REF] to the case where at most t processes may crash, where 1 ≤ t < n. We prove that a colorless task is t-resilient solvable anonymously if and only if it is tresilient solvable non-anonymously. This implies a complete characterization of tresilient, asynchronous, and anonymous computability of colorless tasks. The result is obtained through a series of reductions depicted in the figure below. First, we design an anonymous non-blocking implementation of an atomic weak set object with n registers. The construction is based on the non-blocking atomic snapshot of [START_REF] Ellen | The space complexity of unbounded timestamps[END_REF][START_REF] Guerraoui | Anonymous and fault-tolerant sharedmemory computing[END_REF]. Then, we build a wait-free implementation of a safe agreement object for an arbitrary value set V . Our implementation is a generalization of the anonymous consensus algorithm proposed in [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF]. We describe two ways of deriving the tresilient anonymous solvability characterization. One way is through a novel anonymous implementation of the BG-simulation [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF], which we use to simulate a non-anonymous system by an anonymous system, both t-resilient. The other way is to use the safe-agreement object to solve k-set agreement and then do the topological style of analysis [START_REF] Herlihy | Simulations and reductions for colorless tasks[END_REF][START_REF] Yanagisawa | Wait-free solvability of colorless tasks in anonymous sharedmemory model[END_REF].

Related work Colorless tasks were first identified in [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]. They include fundamental tasks such as consensus [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF], set agreement [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF], and loop agreement [START_REF] Herlihy | A classification of wait-free loop agreement tasks[END_REF], and have been widely studied in the non-anonymous setting. The first part of the book [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF] is devoted to colorless tasks. Not all tasks of interest are colorless though, and general tasks can be much harder to study, notably renaming [START_REF] Castañeda | The renaming problem in shared memory systems: An introduction[END_REF][START_REF] Castañeda | Generalized symmetry breaking tasks and nondeterminism in concurrent objects[END_REF].

A characterization of the colorless tasks that are solvable in the presence of processes that can crash in a dependent way is provided in [START_REF] Herlihy | The topology of shared-memory adversaries[END_REF], and a characterization when several processes can run solo is provided in [START_REF] Herlihy | From waitfree to arbitrary concurrent solo executions in colorless distributed computing[END_REF]. Both encompass the wait-free colorless task solvability characterization, and the former encompasses the t-resilient characterization that we use in this paper.

A certain kind of anonymity has been considered in [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF] to establish the anonymous computability theorem. However, they allow the use of SWMR registers while we assume a fully anonymous model with only MWMR registers.

Anonymous distributed computing remains an active research area since the shared-memory seminal papers [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF][START_REF] Jayanti | Wakeup under read/write atomicity[END_REF] and the message-passing paper [START_REF] Angluin | Local and global properties in networks of processors[END_REF]. For some recent papers and references therein see, e.g. [START_REF] Capdevielle | On the uncontended complexity of anonymous agreement[END_REF][START_REF] Gelashvili | On the Optimal Space Complexity of Consensus for Anonymous Processes[END_REF].

Closer to our paper is [START_REF] Guerraoui | Anonymous and fault-tolerant sharedmemory computing[END_REF] where the anonymous asynchronous MWMR faulttolerant shared-memory model is considered. Our weak set object uses n MWMR registers and is non-blocking; it provides an enhanced atomic implementation of the weak set object supporting non-atomic operations presented in [START_REF] Delporte | Two consensus algorithms with atomic registers and failure detector Ω[END_REF]. A waitfree implementation of a weak set object using 2n registers is in [START_REF] Delporte-Gallet | An anonymous wait-free weak-set object implementation[END_REF]. A set object that also supports a remove operation, but satisfies a weaker consistency condition, called per-element sequential consistency is presented in [START_REF] Baldoni | Value-based sequential consistency for set objects in dynamic distributed systems[END_REF][START_REF] Baldoni | Implementing set objects in dynamic distributed systems[END_REF].

Organization In Section 2 we briefly recall some of the notions used in this paper, about the model of computation and the topology tools, both of which are standard. In Section 3 we present the anonymous implementation of an atomic weak set object from MWMR registers. In Section 4 we present the safe agreement implementation. In Section 5 we derive our anonymous characterization of the t-resilient solvability of colorless tasks. Some proofs are omitted from this extended abstract for lack of space.

Preliminaries

We recall here briefly some standard notions of concurrent programming, for more precise definitions see [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF]. We assume a standard anonymous asynchronous shared-memory model e.g., [START_REF] Guerraoui | Anonymous and fault-tolerant sharedmemory computing[END_REF] consisting of n sequential processes that have no identifiers and execute an identical code. We assume that at most t of the processes may fail by crashing, where 1 ≤ t < n. Processes are asynchronous, i.e., they run at arbitrary speeds, independent from each other. We consider linearizable implementations where each operation appears to take effect instantaneously at some point between its invocation and response [START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF]. A non-blocking algorithm guarantees system-wide progress, while a wait-free also guarantees per-process progress. The processes communicate via multi-writer/multi-reader (MWMR) registers. Let R[0 . . . m -1] denote an array of m registers. The read operation, denoted by read(i), returns the state of R[i]. The write operation, denoted by write(i, v), changes the state of R[i] to v and returns ack. The registers are assumed to be atomic (linearizable). We sometimes refer to the processes by unique names p 0 , . . ., p n-1 for the convenience of exposition, but processes themselves have no means to access these names. Let Π = {p 0 , . . . , p n-1 }.

Atomic Weak Set

Here, we present an anonymous implementation of an atomic weak set object on an arbitrary value set V .

Specification and Algorithm

An atomic weak set object, denoted by SET , is an atomic object used for storing a set of values. The object supports only two operations, add() and get(), and has no remove operation, which is why it is called "weak." The add(v) operation takes an argument v ∈ V and returns ACK . The get() operation, takes no argument and returns the set of values that have appeared as arguments in all the add() operations preceding the get() operation. We assume that SET initially holds no values, i.e., it holds ∅.

We assume that a non-blocking n-component atomic snapshot object is available. An implementation in an anonymous setting with n registers is described in [START_REF] Ellen | The space complexity of unbounded timestamps[END_REF][START_REF] Guerraoui | Anonymous and fault-tolerant sharedmemory computing[END_REF]. The snapshot object exports two operations, update() and scan(). Informally, an update(i, v) updates the i-th component of the object with the value v and a scan() returns an array of n values, which are contained in the n components at some point in time between the invocation and the response of the scan() operation.

We present an anonymous non-blocking implementation of the atomic weak set object on an n-component atomic snapshot object. The pseudocode of the implementation appears in Fig. 1. If Snap is an array of n cells, we define vals(Snap) = ∪ i∈{0,...,n-1} Snap[i]. The idea of the algorithm is as follows. To execute an add(v) operation, the algorithm repeatedly tries to store the value v in each one of the n components of the snapshot object, using an update operation (line 5) until it detects that v appears in all the components. In each iteration, the algorithm deposits in the snapshot object not only v but V iew containing all the values known to be in the set so far. Once v is detected to be in all components of the snapshot object, the add(v) terminates. The get() operation is similar, except that now the V iew of the process has to appear in all the components of the snapshot for the operation to terminate. Intuitively, once a value v (or a set of values) appears in all n components of the snapshot object, it cannot be overwritten and cannot go unnoticed by other processes. This is because the other processes can be covering (about to overwrite) at most n -1 components.

Theorem 1. The algorithm of Fig. 1 is an anonymous non-blocking implementation of an atomic weak set object using n MWMR registers.

Here is a sketch of the proof. Given an operation op, invoc(op) denotes its invocation and resp(op) its response. Let H be a history of the algorithm as defined in [START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF]. Let H be the history H in which some of the operations that are invoked by a process that crashes during the operation and doesn't get a response are removed. H seq denotes the sequential history in which each operation of H appears as if it has been executed at a single point (the linearization) of the time line.

Shared variable :

n-component atomic snapshot object: R

Code for a process

Local variable: Safety For the safety part, we have to define linearization points and prove that the linearization point of each operation get() and add() appear between the beginning and the end of this operation; the sequential history that we get with these points respects the sequential specification of the weak set.

array of value sets Snap[0 . . . n -1] set of Values V iew init ∅ integer next Macro: vals(Snap) = ∪ n-1 i=0 Snap[i] add(v): 1 next = 0 2 Snap = R.scan() 3 V iew = V iew ∪ vals(Snap) ∪ {v} 4 while (#{r|v in Snap[r]} < n) 5 R.update(next, V iew) 6 next = (next + 1) mod n 7 Snap = R.scan() 8 V iew = vals(Snap) ∪ V iew
Consider a history H, let v be a value or a set of values. Define time τ v as the first time, if any, that v belongs to all components of R. When there is no such time, τ v is ⊥.

Lemma 1. If the operation add(v) terminates, then v belongs to all components of R at some time instance before the end of this operation. If the operation get() terminates and returns V , then V belongs to all components of R before the end of this operation.

By Lemma 1, τ v is not ⊥ for each operation add(v) that terminates and τ V is also not ⊥ for each operation get() that terminates and returns V .

It can be shown that the linearization points for operations add() and get() are as follows

-op = add(v): If τ v = ⊥, the linearization point τ op of an operation op = add(v) is max{τ v , invoc(op)}. If τ v = ⊥
, the operation op does not terminate and is not linearized. op = get(): The linearization point τ op of an operation op = get() that returns V is max{τ V , invoc(op)}. A get() operation that does not terminate is not linearized.

The main safety claim is the following.

Lemma 2. H seq satisfies the sequential specification of the weak set.

Liveness We prove that the algorithm is non-blocking; namely, if processes perform operations forever, an infinite number of operations terminate. By contradiction, assume that there is only a finite number of operations get() and add() that terminate and some operations made by correct processes do not terminate. Operations add() or get() may not terminate because the termination conditions of the while loop are not satisfied (Lines 4 or 13): for an add(v) operation, in each scan() made by the process, v is not in at least one of the components of R, and for a get() operation, in each snap, all the components are not equal to the view of the process.

There is a time τ 0 after which there is no new process crash and all processes that terminate get() or add() operations in the run have already terminated. Consider the set N of processes alive after time τ 0 that do not terminate operations in the run. Notice that after time τ 0 only processes in N take steps. Also, as no process in N may crash, each process in N takes an infinite number of steps.

Notice that all values in variables V iew have been proposed by some add(). If there is a finite number of operations, then all variables V iew are subsets of a finite set of values. The main idea of the liveness proof is to analyze stable views. That is, the sequence of views of each process is non-decreasing, each two consecutive views satisfy view ⊆ view . Thus, there is a time τ 1 > τ 0 after which the view of each process p in N converges to a stable view SV iew p : forever after time τ 1 the view of p is SV iew p . Let SV = {SV iew p |p ∈ N }, be the set of all stable views for processes in N . It can be shown that there is no minimal stable view, proving that SV = ∅ and also N = ∅, a contradiction.

Safe Agreement Object

A safe agreement object [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF] on a set V provides two operations, propose and resolve. A propose operation, denoted by propose(v), takes an argument v ∈ V and returns ACK . A resolve operation, denoted by resolve(), takes no argument and returns u ∈ V or ⊥, where ⊥ ∈ V . An execution is well-formed if each process invokes at most one propose operation and no process invokes a propose or resolve operation before its previous operation has terminated. In any well-formed execution, the object satisfies the following four conditions [START_REF] Attiya | Adapting to Point Contention with Long-Lived Safe Agreement[END_REF][START_REF] Bouzid | Anonymity-Preserving Failure Detectors[END_REF]:

Validity Any non-⊥ value returned by a resolve operation is an argument of some propose operation; Agreement If two resolve operations return non-⊥ values v and v , then v = v ; Termination Every operation invoked by a non-faulty process eventually terminates; Nontriviality If no process fails while performing its propose operations, every resolve operation started after some time instance returns a non-⊥ value.

An anonymous wait-free implementation of a safe agreement object for an arbitrary value set V is presented in Fig. 2. The implementation makes use of an array of n weak set objects, denoted by SET [0 . . . n -1]. To perform a propose operation, each process first assigns its input value to a local variable view. Then, the process repeats the following procedure for i = 0, . . . , n -1: it adds view to SET [i]; if SET [i] holds a set of cardinality more than one and view is the minimum value of the set, it returns ACK and immediately breaks the loop; otherwise, it assigns the minimum value of the set to view. To perform a resolve operation, each process checks the set held by SET [n -1]. If the set is not empty, the process returns the minimum value in the set. Otherwise, the process returns ⊥.

Our implementation is a generalization of the anonymous consensus algorithm proposed by Attiya et al. [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF]. Bouzid and Corentin [START_REF] Bouzid | Anonymity-Preserving Failure Detectors[END_REF] have proposed an anonymous implementation of a safe agreement object for the case of V = {0, 1}, also based on [START_REF] Attiya | Computing in totally anonymous asynchronous shared memory systems[END_REF]. However, their implementation does not (directly) extend to the case of an infinite value set.

We now sketch the correctness proof of the algorithm of Fig. 2. Recall that, although we refer to the processes by unique names p 0 , . . ., p n-1 , processes do not know these names and that Π = {p 0 , . . . , p n-1 }. Lemma 3. Fix a well-formed execution of the algorithm of Fig. 2. Let V i be the set of all the values that are added to SET [i] in the execution. Then, V i ⊇ V i+1 holds for all i = 0, . . . , n -2.

Lemma 4 (Validity). The algorithm of Fig. 2 satisfies the validity condition.

Π i = {p ∈ Π | p performs propose() and adds some v ∈ V i \ {min V i } to SET [i]}.
Then, Π i ⊇ Π i+1 holds for all i = 0, . . . , n -2.

Lemma 6 (Agreement). The algorithm of Fig. 2 satisfies the agreement condition. Lemma 8 (Nontriviality). The algorithm of Fig. 2 satisfies the nontriviality condition.

By Lemmas 4, 6, 7, and 8, we obtain the following theorem. Furthermore, notice that the algorithm uses n atomic registers, because an arbitrary finite number of atomic weak set objects can be simulated on top of a single atomic weak set object.

Theorem 2. The algorithm of Fig. 2 is an anonymous wait-free implementation of safe agreement object, using n atomic registers.

t-Resilient Solvable Colorless Tasks

We give a characterization of t-resilient solvable colorless tasks (see formal definitions below) in the anonymous shared-memory model. Theorem 3. A colorless task is t-resilient solvable in the anonymous sharedmemory model if and only if it is t-resilient solvable in the non-anonymous one. Moreover, if a colorless task is t-resilient solvable by n anonymous processes, it can be solved by n shared atomic registers.

The only if part of the theorem is immediate because every anonymous protocol can be executed by non-anonymous processes. We next describe the if part by two different approaches, a topological one and an operational one.

Topological Approach

We briefly recall some notions of combinatorial topology for distributed computing, additional details can be found in [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF].

Let I and O be complexes. A carrier map from I to O is a mapping ∆ :

I → 2 O such that, for each s ∈ I, ∆(s) is a subcomplex of O and s ⊆ s implies ∆(s ) ⊆ ∆(s). If a continuous map f : |I| → |O| satisfies f (|σ|) ⊆ |∆(σ)|
for all σ ∈ I, we say that f is carried by ∆. If a simplicial map δ : bary b I → O satisfies δ(bary b σ) ⊆ ∆(σ) for all σ ∈ I, we say that δ is carried by ∆. As an immediate consequence of Lemma 3.7.8. of [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF], the following lemma holds. To prove the if part of Theorem 3, we first show that the (t+1)-set agreement task is t-resilient solvable by n anonymous processes. An algorithm of Fig. 3 presents an anonymous t-resilient protocol for the (t + 1)-set agreement task. In the protocol, each process first proposes its input value to SA[i] for i = 0, . . . , t. Then, the process repeatedly performs a resolve() operation to all SA[i] in the round-robin manner until it gets non-⊥ value. Once the process gets non-⊥ value, the process returns the value. Theorem 4. The algorithm of Fig. 3 is a t-resilient anonymous protocol for the (t + 1)-set agreement task.

Proof. Termination: It suffices to show that the while loop of Line 4-6 eventually terminates. In the protocol, each process performs propose() operations to Note that the protocol in the proof of Lemma 10 only makes use of a finite number of atomic weak set objects, which are constructed on top of a single atomic weak set object. Thus, every colorless task that is t-resilient solvable by n anonymous processes is solved with n atomic registers. The space complexity upper bound of Theorem 3 follows.

Simulation-Based Approach

We now prove the if part of Theorem 3 by a simulation, which is an anonymous variant of the BG-simulation [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]. More precisely, we show that n anonymous tresilient processes with atomic weak set objects can simulate n non-anonymous t-resilient processes with atomic snapshot objects. We denote the anonymous simulators by p 0 , . . ., p n-1 and the non-anonymous simulated processes by P 0 , . . ., P n-1 . Without loss of generality, we may assume that non-anonymous processes communicate via a single n-ary atomic snapshot object and execute a full-information protocol. In the protocol, the process P i repeatedly writes its local state to the i-th component of the array, takes a snapshot of the whole array and updates its state by the result of the snapshot until it reaches a termination state. When the process reaches the termination state, it decides on the value obtained by applying some predefined function f to the state.

Our simulation algorithm for each simulator is presented in Fig. 4. The algorithm makes use of a two dimensional array of safe agreement objects SA[0 . . .][0 . . . n-1], where the column SA[0 . . .][i] is for storing simulated states of the process P i . The local variables view i and round i stand for the current simulated state and the current simulated round of P i respectively. The function latest_views maps a set of tuples consisting of a process name, its simulated state, and its simulated round to the array whose i-th component is the simulated view of P i associated with the largest simulated round number of P i . The function latest_round i maps a set of the same kind to the latest round number of P i .

In the algorithm, each simulator first proposes its input value to SA[0][i] for all P 0 , . . . , P n-1 . Then, a simulator repeats the following procedure for P 0 , . . . , P n-1 in the round-robin manner until one of P 0 , . . . , P n-1 reach a termination state: it performs resolve() operation on SA[round i ][i]; if the return value of the resolve() operation is not ⊥, the simulator adds the return value, with the name P i and its current simulated round, to SET , updates simulated state and round, and proposes the new simulated state of

P i to SA[round i ][i].
By the use of safe agreement objects, simulators can agree on the return value of each simulated snapshot. Note that there is no need to use a safe agreement object on each simulated update because each value to be updated is deterministically determined by the return value of the preceding simulated snapshot. In the algorithm of Fig. 4, each simulator performs propose() operations sequentially. Thus, even though t simulators crash, they block at most t simulated processes by the nontriviality property of the safe agreement object. By these observations, we establish the following lemma: Lemma 11. If a colorless task is t-resilient solvable by n non-anonymous processes with atomic snapshot objects, it is also t-resilient solvable by n anonymous processes with atomic weak set objects.

The proof of the lemma is similar to the proof of Theorem 5 in [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF], while we omit the proof.

The space complexity of the simulation of Fig. 4 is exactly n atomic registers because a single atomic weak set object can simulate, in the non-blocking manner, an arbitrary finite number of atomic weak set objects and safe agreement objects. This establishes the space complexity upper bound of Theorem 3.

Conclusion

In this paper, we have extended the wait-free colorless task solvability of [START_REF] Yanagisawa | Wait-free solvability of colorless tasks in anonymous sharedmemory model[END_REF] to the case where at most t processes may crash, where 1 ≤ t < n. Furthermore, we have shown that any t-resilient solvable colorless task can be t-resilient solvable anonymously using only n MWMR registers. We have derived our result through a series of reductions that seem interesting in themselves, to study anonymous computability. We hope they are useful to study further long-lived objects (as opposed to tasks), perhaps using a wait-free implementation of the weak set object [START_REF] Delporte-Gallet | An anonymous wait-free weak-set object implementation[END_REF], and uniform solvability (instead of a fixed number of processes n). Also, it would be interesting to look for lower bounds on the number of MWMR registers needed to solve specific colorless tasks.

12 VFig. 1 .

 121 Fig. 1. Non-blocking implementation of atomic weak set for n processes.

Lemma 5 .

 5 Fix a well-formed execution of the algorithm of Fig 2. Let V i be the set of the all values that are added to SET [i] in the execution. Let us define

1 ] 1 view = v 2 for 3 SET 4 Snap 10 Snap 11 if Snap = ∅ then 12 returnFig. 2 .

 112341011122 Fig. 2. Anonymous implementation of safe agreement object

Lemma 9 .

 9 If ∆ : I → 2 O is a carrier map and f : |I| → |O| is a continuous map carried by ∆, then there is a non-negative integer b and a simplicial map δ : bary b I → O carried by ∆.A colorless task is a triple T = (I, O, ∆), where I and O are simplicial complexes and ∆ is a carrier map. A colorless task T is solvable, if for each input simplex s ∈ I, whenever each process p i starts with input value v i ∈ s (different processes may start with the same value), eventually it decides an output value v i , such that the set of output values form a simplex s ∈ ∆(s). The colorless tasks that are fundamental to the present paper are b-iterated barycentric agreement and k-set agreement. The b-iterated barycentric agreement task is a colorless task T = (I, bary b I, bary b ), where we write by bary b the carrier map that maps s ∈ I to bary b s for an abuse of notation. The k-set agreement task is a colorless task T k = (I, skel k I, skel k ), where skel k denotes the carrier map that maps a simplex s ∈ I to the subcomplex skel k I.

Fig. 4 .

 4 Fig. 4. n anonymous processes simulates n non-anonymous processes

Supported by LiDiCo. Supported by UNAM-PAPIIT IN109917. Part of this work was done while visiting Université Paris-Diderot.

Shared variable :

array of safe agreement objects : SA[0 . .

. t]

Code for a process

Local variable:

Integer i init 0 Value result init ⊥ setagree(v):

sequentially. Thus, even if t processes fail, there is at least one safe agreement object such that no process fails while performing a propose() operation on the object. By the nontriviality property of safe agreement objects, after some time instance, resolve() operations on some safe agreement object return non-⊥ value and thus the while loop eventually terminates.

Validity: Every argument of a propose() operation is a proposed value. Because of the validity property of safe agreement objects, a non-⊥ value returned by some resolve() operation is one of the arguments of propose() operations. Thus, the validity condition holds.

k-Agreement: There are t + 1 distinct safe agreement objects. Thus, by the agreement property of safe agreement objects, at most t + 1 distinct values are decided.

As the b-iterated barycentric agreement task is wait-free solvable by anonymous processes [START_REF] Yanagisawa | Wait-free solvability of colorless tasks in anonymous sharedmemory model[END_REF], the following lemma holds. Lemma 10. Let T = (I, O, ∆) be a colorless task. If there exists a continuous map f : |skel t I| → |O| carried by ∆, T is t-resilient solvable by n anonymous processes.

Proof. By Lemma 9, there is an integer b and a simplicial map δ : bary b skel t I → O that satisfies δ(bary b σ) ⊆ ∆(σ) for every σ ∈ skel t I.

The following anonymous protocol solves the colorless task. Suppose that the set of all inputs to the processes is s ∈ I. Execute first the anonymous (t + 1)-set agreement protocol so that the processes all choose vertices that form a simplex sigma in skel t I, and then the b-iterated barycentric agreement protocol (for a sufficiently large value of b). Each process chooses a vertex of a common simplex of bary b skel t σ. Finally, each process determines its output by applying δ to the vertex it chose.


D Gontier

A Levitt

S Siraj-Dine

Numerical construction of Wannier functions through homotopy

We provide a mathematically proven, simple and efficient algorithm to build localised Wannier functions, with the only requirement that the system has vanishing Chern numbers. Our algorithm is able to build localised Wannier for topological insulators such as the Kane-Mele model. It is based on an explicit and constructive proof of homotopies for the unitary group. We provide numerical tests validating the methods for several systems, including the Kane-Mele model.

Introduction

The occupied states of a periodic model of independent electrons are described by Bloch waves, which are (delocalised) modulated plane waves. Wannier functions are localised combinations of Bloch waves that span the occupied space. Due to the gauge freedom for the Bloch waves, Wannier functions are non-unique, and their localisation properties depend strongly on the choice of gauge. A specific gauge choice ensuring localisation was made in [START_REF] Marzari | Maximally localized generalized wannier functions for composite energy bands[END_REF]. These maximallylocalised Wannier functions (MLWF) are useful as a conceptual tool, to interpret bonding and polarisation in crystals [START_REF] King-Smith | Theory of polarization of crystalline solids[END_REF], as well as a numerical tool, to construct effective tight-binding models [START_REF] Marzari | Maximally localized generalized wannier functions for composite energy bands[END_REF] and compute exact exchange terms [START_REF] Wu | Order-n implementation of exact exchange in extended insulating systems[END_REF]. Methods to construct these ML-WFs enable their routine use as a post-processing of density functional theory computations in solids. We refer to [MMY + 12] for a review on applications.

The existence of localised Wannier functions for insulators is not guaranteed. Through the Bloch transform, it is equivalent to the following problem: given a smooth family of rank-N projectors P (k) defined on the d-dimensional torus T d , can we find a smooth Bloch frame representing the range of P (k), i.e. a set of N orthogonal smooth functions u(k) := (u1(k), . . . , uN (k)) on T d such that Ran P (k) = Vect u(k) for all k ∈ T d . If it is indeed possible, then the inverse Bloch transform of u(•, x) yields localised Wannier functions.

In dimensions d ≥ 2, such problems involve a competition between local smoothness and global periodicity. This is because the space Ran P (k) might twist with k, analogous to the twisting of the tangent space of a Möbius strip. Accordingly, there might be topological obstructions to finding such a Bloch frame. These obstructions are characterised by Chern numbers (one number in d = 2, three numbers in d = 3). In dimension 2 and 3, it is possible to construct localised Wannier functions if and only if the Chern numbers vanish [BPC + 07, Pan07]. In systems with time-reversal symmetry, one has the additional property that (TRS) P (-k) = θP (k)θ -1 , where θ is an anti-unitary operator.

This implies that all Chern numbers vanish, and it is therefore possible to construct Wannier functions for such systems. By constrast, Chern insulators (a simple model of which is the Haldane model [START_REF] Haldane | Model for a quantum hall effect without landau levels: Condensedmatter realization of the" parity anomaly[END_REF]), characterised by a broken time-reversal symmetry and non-trivial Chern invariants, can not support localised Wannier functions.

A further distinction appears depending on the type of time-reversal symmetry: bosonic (BTRS, occuring for instance in electrons whose spin degrees of freedom are neglected) or fermionic (FTRS, when spin-orbit coupling is present). Mathematically, these different types are characterised by θ 2 = 1 (BTRS) or θ 2 = -1 (FTRS). In the FTRS case, but not in the BTRS case, a further topological obstruction appears when trying to find Wannier functions respecting the natural symmetry of the problem [START_REF] Fiorenza | Z 2 invariants of topological insulators as geometric obstructions[END_REF]. In d = 2, there are two classes of systems: those for which one can find localised symmetric Wannier functions and those for which this is not possible. This is reflected by the Z2-valued Fu-Kane-Mele invariant [START_REF] Fu | Topological insulators in three dimensions[END_REF]. Physically, this appears as symmetry-protected edge states.

In the common case of BTRS (when spin-orbit coupling is ignored and electrons pairs can be considered as spinless particles), several algorithms exist to compute localised Wannier functions. The most popular one was introduced by Marzari and Vanderbilt [START_REF] Marzari | Maximally localized generalized wannier functions for composite energy bands[END_REF]. This optimises the locality of Wannier functions, starting from an initial guess. This algorithm is able to yield exponentially localised Wannier functions [START_REF] Panati | Bloch bundles, Marzari-Vanderbilt functional and maximally localized Wannier functions[END_REF], but depends strongly on the choice of the initial guess. Recent advances, based on the use of matrix logarithms [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF], selected columns of the density matrix (SCDM [START_REF] Damle | Compressed representation of kohn-sham orbitals via selected columns of the density matrix[END_REF][START_REF] Damle | Scdm-k: Localized orbitals for solids via selected columns of the density matrix[END_REF]) or an extended set of projections [START_REF] Mustafa | Automated construction of maximally localized wannier functions: Optimized projection functions method[END_REF], provide ways to automatically construct initial projections, without any specific physical input.

However, in the topologically non-trivial FTRS case, such as the Kane-Mele model of topological insulators, substantial difficulties appear. Since no symmetric Bloch frame can exist, algorithms that do not explicitly break this symmetry fail. This means that the initial guess for the method of [START_REF] Marzari | Maximally localized generalized wannier functions for composite energy bands[END_REF] has to break this symmetry manually, which often proves challenging in practice. In the method of [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF], this manifests as a crossing of eigenvalues, making the logarithm ill-defined (see Appendix of [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF]). In the SCDM method, this appears as a loss of rank, unless a system-specific choice of columns is imposed [Lin18].

The goal of this paper is to provide an automatic method that constructs localised Wannier functions even in the FTRS case. Our method is based on a standard reduction of the problem of finding Wannier functions to that of finding homotopies in the unitary group U(N ). This problem was solved using matrix logarithms in [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF], and using a multi-step logarithm based on a perturbation argument in [START_REF] Cornean | On the construction of composite Wannier functions[END_REF][START_REF] Cornean | On the construction of Wannier functions in topological insulators: the 3D case[END_REF]. In this paper, we instead use a iterative method where the columns of the unitaries are contracted one by one. This method, which is natural and robust, implements an idea hinted at, but not detailed, in [START_REF] Fiorenza | Construction of real-valued localized composite Wannier functions for insulators[END_REF]p.81]. Unlike the similar method of [CHN16, CM17], it does not exploit the eigenstructure, which proves unstable in practice.

We emphasise that methods to construct Wannier functions specifically for the case of Z2 insulators were proposed in [START_REF] Soluyanov | Wannier representation of 2 topological insulators[END_REF], [START_REF] Soluyanov | Smooth gauge for topological insulators[END_REF], [START_REF] Winkler | Smooth gauge and wannier functions for topological band structures in arbitrary dimensions[END_REF] and [START_REF] Mustafa | Automated construction of maximally localized Wannier functions for bands with nontrivial topology[END_REF]. These methods however require model-specific information, while our method is completely automatic.

The paper is organised as follows. We present in Section 2 the definition of Wannier functions, and the equivalence between localised Wannier functions and smooth Bloch frames. Then, we recall in Section 3 the standard reduction from the problem of finding smooth Bloch frames to that of finding homotopies of unitary matrices. We explain in Section 4 the difficulties of this problem and our solution, which we illustrate numerically in Section 5.

2 From Wannier functions to Bloch frames

The Schrödinger equation in crystals

The goal of Wannier functions is to represent the subspace of occupied orbitals of a d-dimensional periodic Hamiltonian H with localised functions. More specifically, we consider a d-dimensional periodic crystal described by a lattice R ∼ (2πZ) d . We denote by A ∼ R d /(2πZ) d its unit cell, by R * ∼ Z d its reciprocal lattice, and by B ∼ R d /Z d the reciprocal unit cell, also called the Brillouin zone. The behaviour of independent electrons (or electrons in mean-field approaches such as Kohn-Sham density functional theory) is described by the linear Schrödinger operator H, given by

H = - 1 2 ∆ + V, acting on L 2 (R d , C),
where V is a (sufficiently well-behaved) R-periodic potential modelling the external (mean-field) potential. Here, we dropped the spin variable for simplicity, as it plays no role in the argument.

As H commutes with R-translations, it follows from Bloch-Floquet theory [START_REF] Reed | IV: Analysis of Operators[END_REF] that H is described with its fibers H(k), which, in our case, are operators acting on R-periodic functions, and given by

H(k) = 1 2 (-i∇ + k) 2 + V acting on L 2 (A, C).
For all k ∈ B and K ∈ R , the operators H(k) and H(k + K) are unitarily equivalent:

H(k + K) = τK H(k)τ * K with τK (u)(x) := e -iK•x u(x). (1)
The operators H k have a compact resolvent, with eigenvalues

ε 1,k ≤ ε 2,k ≤ • • • going to infinity.
The functions k → ε n,k are continuous and R -periodic. We assume in the sequel that there is a gap g > 0 such that ∀k ∈ B,

ε N +1,k -ε N,k ≥ g
where N ∈ N * is the number of electrons per unit cell. In this case, the operators H(k) have a spectral gap, and we can define the projector P (k) := 1(H(k) ≤ ε N,k + g/2). This projector is of rank N , it is smooth with respect to k and satisfies the quasi-periodic conditions

P (k + K) = τK P (k)τ * K .
The projector on the occupied states P is the operator acting on L 2 (C d , C), whose Bloch fibers are P (k).

Bloch frames and localisation of Wannier functions

We say that u(k

) := (u1(k), • • • , uN (k)) ∈ L 2 (A, C) N is a Bloch frame for P (k) if, for all k ∈ R d , u(k)
is an orthonormal family spanning the range of P (k), and if u(k + K) = τK u(k) for all K ∈ R * . The Wannier functions are then defined for 1 ≤ n ≤ N and R ∈ R as

wn,R(x) := 1 |B| B e ik•(x-R) un(k, x)dk. (2)
We have wn,R(x) = wn,0(x-R). Moreover, as the family {un(k)} 1≤n≤N is an orthonormal basis of Ran P (k), the family {wn,R} 1≤n≤N,R∈R is orthonormal in L 2 (R d , C), and spans the range of P . Finally, if furthermore the map k → un(k) is smooth, then the functions wn,R are localised, as can be seen by integrating by part (2). We deduce that the existence of localised Wannier functions is equivalent to the existence of a smooth frame u for P . In other words, we have reduced the problem of constructing localised Wannier functions to that of the following problem: given a smooth map of rank-N projectors k ∈ R d → P (k) satisfying P (k + K) = τK P (k)τ * K for K ∈ R * , can we find a smooth frame u(k) for P (k) which satisfies u(k + K) = τK u(k)?

Symmetries and topology

The existence of smooth Bloch frames (and therefore, of localised Wannier functions) in dimension d ≥ 2 is not automatic, and depends on the topological properties of the Bloch bundle [BPC + 07]. In dimension 2 and 3, the existence of localised Wannier functions is equivalent to the vanishing of topological invariants known as Chern numbers (one number in dimension d = 2, and three numbers in dimension d = 3).

In the important case where the map k → P (k) satisfies the extra time-reversal symmetry (TRS), that is

P (-k) = θP (k)θ -1 , with θ antiunitary, (3)
then these Chern numbers always vanish, and a smooth frame, together with its corresponding localised Wannier functions, always exists [START_REF] Nenciu | Existence of the exponentially localised Wannier functions[END_REF][START_REF] Panati | Triviality of Bloch and Bloch-Dirac bundles[END_REF].

In the context of Schrödinger operators, condition (3) is satisfied with θu := u the complex conjugation operator. This operator is of bosonic type, squaring to 1. If we start instead of H = -1 2 ∆ + V with a Hamiltonian including spin-orbit coupling, we obtain a TRS of fermionic type, with an operator θ squaring to -1. In the case of FTRS, it is not always possible to build localised Wannier functions that additionally respect a natural symmetry condition [START_REF] Fiorenza | Z 2 invariants of topological insulators as geometric obstructions[END_REF], causing many natural algorithms to fail.

Remark 1. The existence of a smooth and quasi-periodic Bloch frame is a topological property. A consequence of the topological nature of the problem for our purposes is that, provided sufficient regularity on k → H(k), if a continuous and quasi-periodic Bloch frame exists, then it can be lifted to a smooth and quasi-periodic one. Hence, in what follows, we will restrict ourselves to constructing continuous frames, as this can be regularised later, theoretically by the arguments in [START_REF] Fiorenza | Construction of real-valued localized composite Wannier functions for insulators[END_REF] and numerically by using the Marzari-Vanderbilt procedure [MMY + 12].

3 From Bloch frames to homotopies

Parallel transport

An important notion that we use throughout the proof is parallel transport. We recall in this section the main properties of parallel transport, and explain how to solve it numerically.

Consider a smooth family of orthogonal projectors [0, 1] t → P (t), where P (t) is a rank-N projector acting on some Hilbert space H. Let u(0) = (u1(0), . . . , um(0)) ∈ H m be any set of m vectors in Ran P (0), with m ≤ N . Then the solution to the ordinary differential equation where we used the fact that P (t)u(t) = u(t), and again the equality P (t)P (t)P (t) = 0. This gives the following orthogonality-preserving discretisation scheme. We assume that we are given P (ti) for 0 = t0 ≤ t1 ≤ • • • ≤ tI = 1, and u(0) an orthonormal family in the range of P (0). Then we set ut i+1 = P (ti+1)ut i ,

u (t) = P (t), P (t) u(t), with u(t = 0) = u(0) (4) satisfies (u * u) (t) = (u * ) (t)u(t) + u * (t)u (t) = u * -P (t
ut i+1 = ut i+1 u * t i+1 ut i+1 -1/2 . ( 5
)
This is a convergent discretisation of (4), in the sense that when the spacing sup i ti+1 -ti converges to zero, ut i converges to u(ti).

Obstruction matrices and homotopy

In this section, we explain how to reduce the problem of constructing a smooth Bloch frame in d dimensions to that of finding a (d -1)-homotopy of unitary matrices in U (N ). This is a standard construction that was used in several articles (for instance, [CLPS17, SV12] and references therein). We proceed by induction on the dimension d = 1, 2, 3.

Construction for d = 1

In dimension d = 1, we are given a smooth family of projectors P (k1) with k1 ∈ [0, 1], which satisfies the quasi-periodic condition P (1) = τ1P (0)τ * 1 . We choose an arbitrary orthonormal basis u(0) of Ran P (0). We then use parallel transport (4) to construct a smooth frame u(k1) for P (k1), for all k1 ∈ [0, 1]. The problem is that u(1) is not equal to τ1 u(0) a priori. Still, they both form an orthonormal basis of Ran P (1) = Ran P (0), and therefore are related by a unitary matrix V obs ∈ U(N ), called the obstruction matrix:

u(1) = (τ1 u(0))V obs Since V obs ∈ U (N )
, there is a anti-hermitian matrix L such that V obs = exp(L). We then set u(k1) := u(k1) exp(-k1L).

By construction, k1 → u(k1) is smooth on [0, 1], and satisfies u(1) = τ1u(0) as wanted. The continuous map k1 → u(k1) can be smoothed out following Remark 1. This gives the desired Bloch frame for d = 1.

Construction for d = 2

The construction in two dimensions relies on the previous one-dimensional construction. We assume that we are given a smooth family [0, 1] 2 (k1, k2) → P (k1, k2) of operators satisfying P (k + K) = τK P (k)τ * K for all K ∈ R * . First, we use the previous d = 1 construction on the segment k2 = 0, and get a smooth and quasi-periodic frame u(k1, 0) for the family of projectors [0, 1] k1 → P (k1, 0). Now for every k1 ∈ [0, 1], we parallel transport the frame u(k1, 0) along the second direction, to produce a frame u(k1, k2) on [0, 1] 2 . The frame is continuous, and satisfies u(1, k2) = τ (1,0) u(0, k2) for all k2 ∈ [0, 1]. However, there may be a mismatch on the k2-boundary: for all k1 ∈ [0, 1], there is

V obs (k1) so that u(k1, 1) = (τ (0,1) u(k1, 0))V obs (k1) In addition, since u(1, 0) = τ (1,0) u(0, 0) and = u(1, 1) = τ (1,0) u(0, 1), we have V obs (0) = V obs (1).
The map k → V obs (k) is periodic, continuous and piecewise smooth on R, and can be seen as a loop T 1 → U(N ). We recall the following well-known fact.

Proposition 1. Let T 1 k → V (k) ∈ U(N )
be a continuous and piecewise smooth loop in U(N ). The two following assertions are equivalent:

1. The winding number W (det V ) of the determinant of V vanishes, where

W (det V ) := 1 2π 1 0 1 det(V (k)) det(V (k)) dk = 1 2π 1 0 Tr V * (k)V (k) dk. (6)
2. There is a homotopy from

V (•) to IN , that is a piecewise smooth map T 1 × [0, 1] (k, t) → V (k, t) ∈ U(N ) which satisfies ∀k ∈ T 1 , V (k, 0) = V (k) and V (k, 1) = IN .
In the next section, we give a constructive proof of this fact, in the sense that if the winding number vanishes, we construct algorithmically the homotopy V . In our case, it can be further shown (see [START_REF] Fiorenza | Construction of real-valued localized composite Wannier functions for insulators[END_REF]) that W (det V obs ) equals the Chern number of P (k1, k2). According to this proposition, and assuming that W (det V obs ) = 0, there is a homotopy V obs (k1, t) from V obs to IN . We finally set u(k1, k2) := u(k1, k2)V obs (k1, k2).

By construction, this Bloch frame is continuous and satisfies the quasi-periodic boundary condition. It can be smoothed out following Remark 1.

Construction for d = 3

The extension to the third dimension is identical. First, use the d = 2 procedure on the face k3 = 0, i.e. on {(k1, k2, 0) , (k1, k2) ∈ [0, 1] 2 }, to obtain a Bloch frame u(k1, k2, 0) on this face. According to the previous section, this is possible if and only if the winding number of the obstruction on this face vanishes. Then, we parallel transport this frame along the third dimension and get u(k1, k2, k3). We obtain another obstruction matrix V obs (k1, k2) ∈ U(N ), such that ∀k1, k2 ∈ [0, 1] 2 , u(k1, k2, 1) = (τ (0,0,1) u(k1, k2, 0))V obs (k1, k2).

As before, we have V obs (0, k2) = V obs (1, k2) and V obs (k1, 0) = V obs (k1, 1), and so V obs can be seen as a map from T 2 to U(N ). In the sequel, we prove the following classical result, which is the 2-dimensional counterpart of Proposition 1

Proposition 2. Let T 2 (k1, k2) → V (k1, k2) ∈ U(N ) be a continuous and piecewise smooth surface in U(N ). The two following assertions are equivalent:

1. The winding numbers W (det V (•, 0)) and W (det V (0, •)) both vanish;

2. There is a 2-homotopy from V to IN , that is a smooth map

T 2 × [0, 1] (k1, k2, t) → V (k1, k2, t) ∈ U(N ) which satisfies ∀k1, k2 ∈ T 2 , V (k1, k2, 0) = V (k1, k2) and V (k1, k2, 1) = IN .
If the assertions are satisfied for our map V obs (k1, k2), there is a 2-homotopy V obs (k1, k2, t) that contracts V obs to IN , and we set u(k1, k2, k3) := u(k1, k2, k3)V obs (k1, k2, k3) to obtain the final Bloch frame.

As in the d = 2 case, the three winding numbers appearing in the construction correspond to the three Chern numbers.

Remark 2. This construction process extends trivially to dimensions d > 3, but the analogue of Propositions 1 and 2 are no longer true, and an additional obstruction (the second Chern class) appears.

It remains to explain our constructive proof of Propositions 1 and 2. This is the topic of the next section.

Constructive homotopies in the unitary group

In this section, we describe a simple and efficient algorithm to construct 1-homotopies and 2-homotopies in U(N ). We first examine how the logarithm algorithm in [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF] fails for simple systems such as the Kane-Mele model. We then explain our algorithm in the context of 1-homotopies, and then extend our result for 2-homotopies.

Logarithm algorithm

Let T 1 k → V (k) ∈ U(N ) be a smooth loop. A very natural approach, that was used in [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF], is to find a global logarithm for V (k), that is a smooth loop L(k) of anti-hermitian matrices such that

V (k) = exp (L(k)) , ∀k ∈ [0, 1].
If such a logarithm exists, then a homotopy from V (k) to IN is given by

∀k ∈ T 1 , ∀t ∈ [0, 1], V (k, t) = exp ((1 -t)L(k)) .
The authors of [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF] then proposed to work with the eigenvalues of U (k), to find a continuous phase for each on. However, even if the winding number W (det V ) vanishes, this approach can fail, as shown by this simple example

Example 1. Consider the analytic and periodic matrix path

V (k) = exp(2iπk) 0 0 exp(-2iπk)
Here, it is impossible to find a logarithm of the path that is continuous and periodic on [0, 1], since each eigenvalue has a winding number, hence receives a phase increment of ±2π respectively when going from 0 to 1.

The case of eigenvalues having a winding number appears in practice for systems with fermionic time-reversal symmetry such as the Kane-Mele model in its QSH phase (see Section 5.1). In Figure 1, we display the eigenvalues of the obstruction matrix for a representative set of parameters. Here, the determinant is identically 1. Hence, we know that a homotopy does exist, but the logarithm method fails to construct it. A similar method, proposed in [START_REF] Cornean | On the construction of Wannier functions in topological insulators: the 3D case[END_REF], is to introduce a small perturbation in order to avoid eigenvalue crossings, which makes each winding number trivial, and look for a family of logarithms satisfying

k1 0 1 2 1 R e ( 1 ) 1 1 2 0 1 2 1 Im( 2 ) 1 1 2 0 1 2 1 1 2 (a)
V (k) = e L 1 (k) e L 2 (k) . . . e L N (k) ,
where Li(s), i ∈ 1 . . . N are anti-Hermitian. However, small perturbations of eigenvalues can introduce large changes in the eigenvectors, and hence produce a continuous but irregular path, which makes this method algorithmically difficult to implement.

Column interpolation method

From the counter-example given in Example 1, we see that constructing a homotopy of unitary matrices based from their eigenvalues may fail, as these can wind. In our method, instead of contracting eigenvalues, we rather contract the columns of V (k) one by one. Algebraically, this corresponds to exploiting the fibration

U(N -1) → U(N ) → S 2N -1 ,
which was suggested (but not explored further) in [FMP16a, p.81]. let T 1 k → V (k) ∈ U(N ) be a smooth map. We write V (k) = (v1(k), . . . , vN (k)) where vn(k) ∈ S 2N -1 is the n-th column of V (k). Our strategy is to first contract the columns vn(k) iteratively to a fixed column vn, ensuring that they stay orthonormal, and then homotopise V = (v1, . . . , vN ) to the identity.

Let us assume that at step 1 ≤ n ≤ N , we have found how to contract the first n -1 columns to some fixed vectors: we have constructed n -1 smooth maps of orthonormal vectors v1(k, t), . . . , vn-1(k, t) such that vj(k, t = 0) = vj(k) and vj(k, t = 1) = vj. We denote by

Pn-1(k, t) := IN - n-1 j=1 |vj(k, t) vj(k, t)|,
the projection on the orthogonal of this family, of rank N -n + 1. By hypothesis, at t = 1, the projectors Pn-1(k, t = 1) are equal to a constant projector Pn-1.

We now contract the n-th column vn(k, t) to a fixed column vn ∈ Ran Pn-1 while satisfying vn(k, t) ∈ Ran Pn-1(k, t) for all k, t ∈ T 1 ∪ [0, 1]. This ensures that the constructed map for the n-th column is orthogonal to the previously constructed ones. First, for all fixed k ∈ T 1 , we parallel transport the orthogonal family (vn(k), • • • , vN (k)) with respect to Pn-1(k, •), and obtain a smooth family of orthonormal frames ( vn(k, t), • • • , vN (k, t)) for k, t ∈ T 1 × [0, 1]. At this point, vn(k, t = 1) forms a non-trivial loop in Ran Pn-1. We now contract this to a single vector vn, distinguishing two cases, depending on whether vn(k, t = 1) can or cannot cover the whole of the unit sphere in Ran Pn-1.

Case n < N . When n < N , the unit sphere in Ran Pn-1 is a manifold of real dimension 2(N -n) + 1 ≥ 3. The family { vn(k, t = 1)} k∈T 1 describes a piecewise smooth loop on that manifold, and from Sard's lemma it follows that there exists a vector vn ∈ S 2N -1 ∩ Ran Pn-1 such that -vn does not belong to the loop { vn(k, t = 1)} k∈T 1 (see Remark 3).

For all k ∈ T 1 , the family ( vn(k, 1), • • • , vN (k, 1)) is a basis of Pn-1, so there exist (smooth) coefficients c(k

) := (cn(k), . . . , cN (k)) ∈ C N -n+1 with |c(k)| = 1 such that ∀k ∈ T 1 , vn = N j=n cj(k) vj(k, 1). The map T 1 k → c(k)
is a loop on the sphere S 2(N -n)+1 . In addition, since -vn never touches the loop { vn(k, t = 1)} k∈T 1 , c(k) never touches the vector -e1 := (-1, 0, • • • , 0). We can therefore contract the loop c(k) to e1 on S 2(N -n)+1 with the explicit contraction

c(k, t) := (1 -t)c(k) + te1 (1 -s)c(k) + te1 , (7)
which is a well-defined smooth map from

T 1 ×[0, 1] to S 2(N -n)+1
. This contraction of coefficients directly translates into a contraction of vn(k) to vn by setting

vn(k, t) := N j=n cj(k, t) vj(k, t).
By construction, vn(k, t) is a normalised vector which is orthogonal to (v1(k, t), . . . , vn-1(k, t)) for all k, t ∈ T 1 × [0, 1]. This concludes the construction in this case.

Remark 3. In practice, in order to find numerically vn, we draw several random or well-chosen points pj ∈ S 2N -1 , which we project on Pn-1 and normalise. We then pick vn := arg max j min k∈T 1 vn(k, 1) + pj .

This ensures that the denominator in (7) is not too close to zero.

Case n = N . For the last vector, i.e. when n = N , the previous construction can fail because vN (k, t = 1) can cover the whole of the unit sphere in Ran Pn-1. We therefore follow a different route. For all k ∈ T 1 , the vector vN (k, t = 1) always lies in the same one-dimensional subspace.

In particular, there is a smooth phase φ : k) with vN := vN (0) (for instance).

[0, 1] → R so that ∀k ∈ [0, 1], vN (k) = vN e iφ(
By periodicity, one must have φ(1) = φ(0) + 2πm with m ∈ Z. This gives

m = 1 2π (φ(1) -φ(0)) = 1 2π 1 0 φ (k)dk = 1 2πi 1 0 vN (k), d dk vN (k) dk. We set V (k, t) := (v1(k, t), . . . vN-1(k, t), vN (k, t)) ∈ U(N )
. This is a smooth deformation between V (k) at t = 0 and V (k, 1) = (v1, . . . vN-1, vN (k, 1)) at t = 1. Also, we have

vN (k), d dk vN (k) = Tr V (k, 1) * d dk V (k, 1) dk.
This leads to

m = 1 2πi 1 0 Tr V (k, 1) * d dk V (k, 1) dk = W det V (•, 1) = W (det V (•)), ( 8
)
where we recall that W (•) was defined in (6), and where we used the fact that the winding number is not affected by a smooth deformation: W V (•, t) does not depend on t. We conclude that can contract the vector vN to vN if and only if m = 0, or equivalently if W (det V ) = 0. In this case, an explicit contraction is given by

vN (k, t) = vN (k, t)e -itφ(k) .
Last step. At this point, we have algorithmically constructed a smooth map

T 1 × [0, 1] (k, t) → V (k, t) ∈ U(N ) such that V (k, t = 0) = V (k) and V (k, t = 1) = V := (v1, • • • , vN ).
To get a contraction to the identity matrix IN , we write V = exp(L), where L is anti-hermitian, and we take as our final homotopy

(k, t) → V (k, t)e -tL .
This concludes our constructive proof for Proposition 1.

Remark 4. In our algorithm, we have tried to make the homotopy as smooth as possible. This means that we avoid composing homotopies sequentially, which is inefficient numerically, and that we wish that the method reduces to the logarithm method in the case where V (k) is constant (where we know that the logarithm gives the geodesic in U(N ) and therefore the most efficient path). If that is not a concern, then a simpler version of the algorithm can be given. After the first column is homotopised to a column v1, this vector can further be deformed to e1, and therefore we can assume that v1 = e1. This implies that the homotopy

V (k, t) := (v1(k, t), v2(k, t), . . . , vN (k, t))) satisfies V (k, 0) = V (k) and V (k, 1) =      1 v1,2(k, 1) • • • v1,N (k, 1) 0 v2,2(k, 1) • • • v2,N (k, 1) . . . . . . • • • . . . 0 v2,N (k, 1) • • • vN,N (k, 1)      =: 1 0 0 V1(k) ,
where we used the fact that V (k, 1) is unitary, so that v1,2(k, 1) = • • • = v1,N (k, 1) = 0. We have reduced the homotopy problem in U(N ) to the homotopy problem in U(N -1), and therefore solve the problem by induction on N , using the case n = N above to treat the base step.

Remark 5 (Parallelisability of the sphere). In the case N = 2, we can use the identification of SU(2) with S(3) given by

a -b * b a * → a b
to simplify the algorithm, as done in [START_REF] Fiorenza | Construction of real-valued localized composite Wannier functions for insulators[END_REF]. More generally, if given a vector x ∈ {z ∈ C N , |z| = 1} we had a systematic way to build an orthogonal basis of the (complex-)orthogonal x ⊥ in a way that is smooth with respect to x, we could exploit that in our algorithm. This is easily achieved in dimension 2 by the mapping (a, b) → (-b * , a * ). However, this is impossible when N = 3 (because this would imply the parallelisability of the 5-dimensional sphere, which is false). We therefore have to follow a different route, using parallel transport to build this basis incrementally.

Extension for 2-homotopies

We now consider the case of 2-homotopies, and we want to contract a map T 2 (k1, k2) → V (k1, k2) ∈ U(N ). Following the same iterations as in the previous section, we see that at step n < N , the n-th column v(k1, k2, t = 1) defines a 2-dimensional sub-manifold on S 2N -1 ∩ Ran Pn-1 of dimension 2(N -n) + 1 ≥ 3, and we can find vn so that vn does not belong to this sub-manifold. We then follow the same steps.

For the last step n = N , there is a smooth phase function T 2 (k1, k2) → φ(k1, k2) such that ∀k1, k2 ∈ [0, 1] 2 , vN (k1, k2, 1) = vN exp(iφ(k1, k2)) with vN := vN (0, 0, 1) for instance.

By periodicity and continuity, there is m1, m2 ∈ Z such that φ(k1 + 1, k2) = φ(k1, k2) + 2πm1 and φ(k1, k2 + 1) = φ(k1, k2) + 2πm2. As in (8), we find

∀k2 ∈ T 1 , m1 = W (det V (•, k2)) and ∀k2 ∈ T 1 , m2 = W (det V (k1, •)).
If both number vanish, then a contraction is given by vn(k1, k2, t) := vn(k1, k2, t) exp(-itφ(k1, k2)). The constructive proof of Proposition 2 follows.

Remark 6. This proof fails for 3-homotopies. The reason is that with N = 2, the first vector of T 3 (k1, k2, t3) → V (k1, k2, t3) ∈ U(2) is now a 3-dimensional sub-manifold in S 3 , hence can wrap the whole sphere S 3 . This is a manifestation of the second Chern class.

Numerical results

In this section, we apply the constructive method outlined above to the case of the Kane-Mele model (d = 2), and silicon (d = 3). We discretise the Brillouin zone with equispaced points (the Monkhorst-Pack grid). At each discrete point k, we diagonalise H(k) and obtain the eigenvectors (u n,k ) 1≤n≤N corresponding to the N lowest eigenvalues of H(k). We then seek a unitary matrix Um,n(k) that makes u n (k) = 1≤m≤N u mk Umn(k) as smooth as possible. The quantities needed by our algorithm are the overlaps u mk , u n,k+b between neighbouring points k and k + b, similar to other methods such as Wannier90 [MYP + 14]. More information on this methodology can be found in [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF].

The Kane-Mele model

The Kane-Mele model, first proposed in [START_REF] Kane | Z2 topological order and the quantum spin Hall effect[END_REF], is a toy model of a Z 2 topological insulator. It is a tight-binding model on a 2D hexagonal lattice, with four degrees of freedom per site (two orbitals and two spins), two of which are occupied (H(k) is a 4 × 4 matrix, and N = 2).

Description of the model

The Bloch representation of this model can be written as follows.

H k = 5 a=1 da(k)Γ a + 5 a,b=1 a<b d ab (k)Γ ab , (9)
where Γ ab := 1 2i [Γ a , Γ b ], and Γ a are the Dirac matrices (σ x ⊗IN , σ z ⊗IN , σ y ⊗s x , σ y ⊗s y , σ y ⊗s z ), σ j and s j being the Pauli matrices of sublattice and spin respectively.

The functions da(k) and d ab (k) in ( 9) are chosen as in [START_REF] Kane | Z2 topological order and the quantum spin Hall effect[END_REF]. In particular, da is even and d ab odd, and the model satisfies a fermionic time-reversal symmetry. The model has 4 free parameters: t, λS0, λν and λR. Here, we fix the parameters t = 1, λSO = 1, and only vary λν and λR < 2 √ 3. For every value of λR < 2 √ 3, the system undergoes a phase transition at the critical value λν = 3 √ 3 ≈ 5.2:

• For λν > 3 √ 3, the material is in a regular insulating phase.

• For λν = 3 √ 3, the material is in a transitional metallic phase: the gap closes, which means that the material is conducting.

• For λν < 3 √ 3, the material is in the Quantum Spin Hall (QSH) phase.

Numerical construction of Wannier functions for the Kane-Mele model

In order to construct localised Wannier functions for the Kane-Mele model, one needs to provide a Bloch frame that is regular enough on the Brillouin zone. In the QSH phase, no continuous and symmetric frame exists, but since the Chern number is trivial for any time-reversal symmetric Bloch bundle, there exists a non-symmetric continuous frame. Moreover, in this case, the eigenvalues of the obstruction have a non-trivial winding number, so the logarithm method of [CLPS17] cannot provide a homotopy of the obstruction.

In this section, we use the algorithm described above to construct a continuous initial guess of the Bloch frame, which can then be refined to a more regular one by a smoothing method, thus providing a well-localised Wannier function. The Brillouin zone was discretised with a 200 × 200 grid. In the topologically trivial case, both methods produce a reasonable output (Figures 2a and2b).

In order to measure localisation, we follow [START_REF] Marzari | Maximally localized generalized wannier functions for composite energy bands[END_REF], and measure the spread of the Wannier functions Ω. We also measure the quantity ∇ k u k , estimated using finite differences. Localised Wannier functions correspond to smooth gauge, and singularities in this quantity is therefore a sign of delocalisation.

In Figure 3a, the log interpolation method fails at constructing a continuous map in the topologically non-trivial QSH phase, as the measure of regularity ∇ k u exhibits lines of discontinuity, with very high maximal values. In contrast, in Figure 3b, the column interpolation produces a smoother output, which also yields a lower maximal value of the regularity ∇ k u .

The (dis)continuity of the resulting Bloch frame after each method is further demonstrated by the convergence with respect to k point discretisation, displayed in Figure 4. In the log interpolation method, the discrete Bloch frames converge to a discontinuous one, as we see from the divergence of the norm of the gradient (estimated with finite differences). In contrast, the column interpolation produces a frame that has a smooth limit.

Figures 5a and 5b display selected components of k1 → V obs (k1, k2) for k2 = 1, 2 3 , 1 3 . In Figure 5a, we see how the obstruction path is contracted into the null path by our algorithm, in the QSH phase, with no Rashba term. In this case, the system decomposes into two independent V21 = 0. Notice also that the diagonality of the obstruction, as well as time reversal symmetry, implying that k → Re V21(k) is odd (which is verified up to rounding errors in the horizontal path), is broken by the method, as expected.

In Figure 5b, for a Rashba term λR = 1, the obstruction (the largest path, in green) is no longer diagonal (it has non-zero off-diagonal elements), but it still satisfies time-reversal symmetry, since k → Re V21(k) is odd. The method breaks time-reversal symmetry to construct the continuous interpolation to the trivial path.

Numerical results for Silicon

Using Quantum Espresso, [GSB + 09], the Bloch waves of Silicon for various discretisations of the Brillouin zone were provided to the homotopy constructing methods, in order to compare the numerical results of our column interpolation algorithm with the ones provided by the logarithm method of [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF]. In Table 1, we can see that the value of the localisation functional Ω is better for the logarithm method than for ours, but, after optimisation of the Marzari-Vanderbilt procedure [MMY + 12], both methods agree.

In Figure 6, we display some Wannier functions computed by both methods, before optimisation. The representation was done through Wannier90 [MYP + 14] and VESTA [START_REF] Momma | VESTA3 for three-dimensional visualization of crystal, volumetric and morphology data[END_REF]. The localisation of both is not optimal, which is expected, but the Wannier functions are still localised, and physically relevant.

Conclusion

We presented a new method to construct localised Wannier functions. It is proven to work even in the case of topological insulators which causes most published algorithms to fail. In the "easy" cases, it works similarly to the method of [START_REF] Cancès | Robust determination of maximally localized Wannier functions[END_REF]. As that method, it only localises Wannier functions across unit cells, and does not attempt to localise the functions inside the unit cell. This is problematic in the case of large unit cells, which is the case of many real

Figure 1 :

 1 Figure 1: Eigenvalues of the obstruction for the Kane-Mele model

Figure 2 :

 2 Figure 2: Local regularity ∇ k u , λ ν = 6 and λ R = 1 (regular insulating phase).

Figure 3 :

 3 Figure 3: Local regularity ∇ k u , λ ν = 0 and λ R = 1 (QSH phase).

Figure 4 :Figure 5 :

 45 Figure 4: Convergence of Ω obtained by both methods, in the QSH phase (λ ν = 0, λ R = 1)

  (a) Logarithm method (b) Column interpolation method

Figure 6 :

 6 Figure 6: One of the four Wannier functions of silicon, isosurface plot at 20% of maximal value.

Table 1 :

 1 Value of the Marzari-Vanderbilt localisation functional Ω (in Bohr 2 ) for frames on various discretisations of the Brillouin zone Discretisation of the BZ 5 × 5 × 5 10 × 10 × 10 15 × 15 × 15 20 × 20 × 20

	After logarithm method	25.72	29.70	30.62	30.94
	After column interpolation	40.88	35.31	53.68	46.80
	After MV optimisation
	(log initial guess)	19.30	22.06	22.71	22.95
	After MV optimisation
	(col initial guess)	19.30	22.06	22.71	22.95

The PhD of Sami Siraj-Dine is supported by the Labex Bézout.