Dan Alistarh

Seth Gilbert

Rachid Guerraoui

Corentin Travers

Generating Fast Indulgent Algorithms

, which induces only a constant overhead in terms of time complexity in well-behaved executions. Our technique is based on a new abstraction we call an asynchrony detector, which the participating processes implement collectively. The resulting transformation works for a large class of colorless tasks, including consensus and set agreement. Interestingly, we also show that our technique is relevant for colored tasks, by applying it to the renaming problem, to obtain the first indulgent renaming algorithm.

Introduction

The feasibility and complexity of distributed tasks has been thoroughly studied both in the synchronous and asynchronous models. To better capture the properties of realworld systems, Dwork, Lynch, and Stockmeyer [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] proposed the partially synchronous model, in which the distributed system may alternate between synchronous to asynchronous periods. This line of research inspired the introduction of indulgent algorithms [START_REF] Guerraoui | Indulgent algorithms[END_REF], i.e. algorithms that guarantee correctness and efficiency when the system is synchronous, and maintain safety even when the system is asynchronous. Several indulgent algorithms have been designed for specific distributed problems, such as consensus (e.g., [START_REF] Dutta | The inherent price of indulgence[END_REF][START_REF] Lamport | Fast paxos[END_REF]). However, designing and proving correctness of such algorithms is usually a difficult task, especially if the algorithm has to provide good performance guarantees. Contribution. In this paper, we introduce a general transformation technique from synchronous algorithms to indulgent algorithms, which induces only a constant overhead in terms of time complexity. Our technique is based on a new primitive called an asynchrony detector, which identifies periods of asynchrony in a fault-prone asynchronous system. We showcase the resulting transformation to obtain indulgent algorithms for a large class of colorless agreement tasks, including consensus and set agreement. We also apply our transformation to the distinct class of colored tasks, to obtain the first indulgent renaming algorithm.

Detecting Asynchrony. Central to our technique is a new abstraction, called an asynchrony detector, which we design as a distributed service for detecting periods of asynchrony. The service detects asynchrony both at a local level, by determining whether the view of a process is consistent with a synchronous execution, and at a global level, by determining whether the collective view of a set of processes could have been observed in a synchronous execution.

We present an implementation of an asynchrony detector, based on the idea that each process maintains a log of the messages sent and received, which it exchanges with other processes. This creates a view of the system for every process, which we use to detect asynchronous executions.

The Transformation Technique. Based on this abstraction, we introduce a general technique allowing synchronous algorithms to tolerate asynchrony, while maintaining time efficiency in well-behaved executions. The main idea behind the transformation is the following: as long as the asynchrony detector signals a synchronous execution, processes run the synchronous algorithm. If the system is well behaved, then the synchronous algorithm yields an output, on which the process decides. Otherwise, if the detector notices asynchrony, we revert to an existing asynchronous backup algorithm with weaker termination and performance guarantees.

Transforming Agreement Algorithms. We first showcase the technique by transforming algorithms for a large class of agreement tasks, called colorless tasks, which includes consensus and set agreement. Intuitively, a colorless task allows processes to adopt each other's output values without violating the task specification, while ensuring that every value returned has been proposed by a process.

We show that any synchronous algorithm solving a colorless task can be made indulgent at the cost of two rounds of communication. For example, if a synchronous algorithm solves synchronous consensus in t+1 rounds, where t is the maximum number of crash failures (i.e. the algorithm it is time-optimal), then the resulting indulgent algorithm will solve consensus in t + 3 rounds if the system is initially synchronous, or will revert to a safe backup, e.g. Paxos [START_REF] Lamport | Fast paxos[END_REF][START_REF] Lamport | Generalized consensus and paxos[END_REF] or ASAP [START_REF] Alistarh | How to solve consensus in the smallest window of synchrony[END_REF], otherwise.

The crux of the technique is the hand-off procedure: we ensure that, if a process decides using the synchronous algorithm, any other process either decides or adopts a state which is consistent with the decision. In this second case, we show that a process can recover a consistent state by examining the views of other processes. The validity property will ensure that the backup protocol generates a valid output configuration.

Transforming Renaming Algorithms. We also apply our technique to the renaming problem [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], and obtain the first indulgent renaming algorithm. Starting from the synchronous protocol of [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF], our protocol renames in a tight namespace of N names and terminates in (log N + 3) rounds, in synchronous executions. In asynchronous executions, the protocol renames in a namespace of size N + t.

We consider an eventually synchronous system with N processes Π = {p 1 , p 2 , . . . , p N }, in which t < N/2 processes may fail by crashing. Processes communicate via messagepassing in rounds, which we model much as in [START_REF] Dutta | The inherent price of indulgence[END_REF][START_REF] Dutta | The inherent price of indulgence[END_REF][START_REF] Alistarh | Of choices, failures and asynchrony: The many faces of set agreement[END_REF]. In particular, time is divided into rounds, which are synchronized. However, the system is asynchronous, i.e. there is no guarantee that a message sent in a round is also delivered in the same round. We do assume that processes receive at least Nt messages in every round, and that a process always receives its own message in every round. Also, we assume that there exists a global stabilization time GST ≥ 0 after which the system becomes synchronous, i.e. every message is delivered in the same round in which it was sent. We denote such a system by ES(N, t).

Although indulgent algorithms are designed to work in this asynchronous setting, they are optimized for the case in which the system is initially synchronous, i.e. when GST = 0. We denote the synchronous message-passing model with t < N failures by S(N, t). In case the system stabilizes at a later point in the execution, i.e. 0 < GST < ∞, then the algorithms are still guaranteed to terminate, although they might be less efficient. If the system never stabilizes, i.e. GST = ∞, indulgent algorithms might not terminate, although they always maintain safety.

In the following, we say that an execution is synchronous if every message sent by a correct process in the course of the execution is delivered in the same round in which it was sent. Alternatively, if process p i receives a message m from process p j in round r ≥ 2, then every process received all messages sent by process p j in all rounds r ′ < r. The view of a process p at a round r is given by the messages that p received at round r and in all previous rounds. We say that the view of process p is synchronous at round r if there exists an r-round synchronous execution which is indistinguishable from p's view at round r.

Related Work

Starting with seminal work by Dwork, Lynch and Stockmeyer [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF], a variety of different models have been introduced to express relaxations of the standard asynchronous model of computation. These include failure detectors [START_REF] Chandra | Unreliable failure detectors for asynchronous systems (preliminary version)[END_REF], round-by-round fault detectors (RRFD) [START_REF] Gafni | Round-by-round fault detectors (extended abstract): Unifying synchrony and asynchrony[END_REF], and, more recently, indulgent algorithms [START_REF] Guerraoui | Indulgent algorithms[END_REF].

In [START_REF] Dutta | The inherent price of indulgence[END_REF][START_REF] Dutta | The inherent price of indulgence[END_REF], Guerraoui and Dutta address the complexity of indulgent consensus in the presence of an eventually perfect failure detector. They prove a tight lower bound of t + 2 rounds on the time complexity of the problem, even in synchronous runs, thus proving that there is an inherent price to tolerating asynchronous executions. Our approach is more general than that of this reference, since we transform a whole class of synchronous distributed algorithms, solving various tasks, into their indulgent counterparts. On the other hand, since our technique induces a delay of two rounds of communication over the synchronous algorithm, in the case of consensus, we miss the lower bound of t + 2 rounds by one round.

Recent work studied the complexity of agreement problems, such as consensus [START_REF] Alistarh | How to solve consensus in the smallest window of synchrony[END_REF] and k-set agreement [START_REF] Alistarh | Of choices, failures and asynchrony: The many faces of set agreement[END_REF], if the system becomes synchronous after an unknown stabilization time GST . In [START_REF] Alistarh | How to solve consensus in the smallest window of synchrony[END_REF], the authors present a consensus algorithm that terminates in f + 2 rounds after GST , where f is the number of failures in the system. In [START_REF] Alistarh | Of choices, failures and asynchrony: The many faces of set agreement[END_REF], the authors consider k-set agreement in the same setting, proving that ⌊t/k⌋ + 4 rounds after GST are enough for k-set agreement, and that at least ⌊t/k⌋ + 2 rounds are required. The algorithms from these references work with the same time complexity in the indulgent setting, where GST = 0. On the other hand, the transformation in the current paper does not immediately yield algorithms that would work in a window of synchrony. From the point of view of the technique, references [START_REF] Alistarh | How to solve consensus in the smallest window of synchrony[END_REF][START_REF] Alistarh | Of choices, failures and asynchrony: The many faces of set agreement[END_REF] also use the idea of "detecting asynchrony" as part of the algorithms, although this technique has been generalized in the current work to address a large family of distributed tasks.

Reference [START_REF] Dutta | The overhead of consensus failure recovery[END_REF] considered a setting in which failures stop after GST , in which case 3 rounds of communication are necessary and sufficient. Leader-based, Paxos-like algorithms, e.g. [START_REF] Lamport | Fast paxos[END_REF][START_REF] Lamport | Generalized consensus and paxos[END_REF], form another class of algorithms that tolerate asynchrony, and can also be seen as indulgent algorithms.

A precise definition of colorless tasks is given in [START_REF] Delporte-Gallet | The disagreement power of an adversary[END_REF]. Note that, in this paper, we augment their definition to include the standard validity property (see Section 5).

Asynchrony Detectors

An asynchrony detector is a distributed service that detects periods of asynchrony in an asynchronous system that may be initially synchronous. The service returns a YES/NO indication at the end of every round, and has the property that processes which receive YES at some round share a synchronous execution prefix. Next, we make this definition precise.

Definition 1 (Asynchrony Detector). Let d be a positive integer. A d-delay asynchrony detector in ES(N, t) is a distributed service that, in every round r, returns either YES or NO, at each process. The detector ensures the following properties.

-(Local detection) If process p receives YES at round r, then there exists an r-round synchronous execution in which p has the same view as its current view at round r. -(Global detection) For all processes that receive YES in round r, there exists an (rd)-round synchronous execution prefix S[1, 2, . . . , rd] that is indistinguishable from their views at the end of round rd. -(Non-triviality) The detector never returns NO during a synchronous execution.

The local detection property ensures that, if the detector returns YES, then there exists a synchronous execution consistent with the process' view. On the other hand, the global detection property ensures that, for processes that receive YES from the detector, the (r -R)-round execution prefix was "synchronous enough", i.e. there exists a synchronous execution consistent with what these processes perceived during the prefix. The non-triviality property ensures that there are no false positives.

Implementing an Asynchrony Detector

Next, we present an implementation of a 2-delay asynchrony detector in ES(N, t), which we call AD(2). The pseudocode is presented in Figure 1.

The main idea behind the detector, implemented in the process procedure, is that processes maintain a detailed view of the state of the system by aggregating all messages received in every round. For each round, each process maintains an Active set of processes, i.e. processes that sent at least one message in the round; all other processes are in the Failed set for that round (lines 2-4). Whenever a process receives a new message, it merges the contents of the Active and Failed sets of the sender with its own (lines 8-9). Asynchrony is detected by checking if there exists any process that is in the Active set in some round r, while being in the Failed set in some previous round r ′ < r (lines 10-12). In the next round, each process sends its updated view of the system together with a synch flag, which was set to true, if asynchrony was detected.

procedure detector()i

1 msgi ← ⊥; synchi ← true; Activei ← [ ]; Failed i ← [ ];

Proof of Correctness

In this section, we prove that the protocol presented in the Section 4.1 satisfies the definition of an asynchrony detector. First, to see that the local detection condition is satisfied, notice that the contents of the Active and Failed sets at each process p can be used to construct a synchronous execution which is coherent with process p's view.

In the following, we focus on the global detection property. We show that, for a fixed round r > 0, given a set of processes P ⊆ Π that receive YES from AD(2) at the end of round r + 2, there exists an r-round synchronous execution S[1, r] such that the views of processes in P at the end of round r are consistent with S[1, r]. We begin by proving that if two processes receive YES from the asynchronous detector in round r + 2, then they must have received eachother's round r + 1 messages, either directly, or through a relay. Note that, because of the round structure, a process's round r + 1 message only contains information that it has acquired up to round r.

In the following, we will use a superscript notation to denote the round at which the local variables are seen. For example, Active r+2 q [r + 1] denotes the set Active[r + 2] at process q, as seen from the end of round r + 2.

Lemma 1. Let p and q be two processes that receive YES from AD(2) at the end of round r + 2. Then p ∈ Active r+2 q [r + 1] and q ∈ Active r+2 p [r + 1].

Proof. We prove that p ∈ Active r+2 q [r + 1]-the proof of the second statement is symmetric. Assume, for the sake of contradiction, that p / ∈ Active r+2 q [r + 1]. Then, by lines 8-9 of the process() procedure, none of the processes that send a message to q in round r + 2 received a message from p in round r + 1. However, this set of processes contains at least Nt > t elements, and therefore, in round r + 2, process p receives a message from at least one process that did not receive a message from p in round r + 1. Therefore p ∈ Active r+2 p [r + 2] ∩ F ailed r+2 p [r + 1] (recall that p receives its own message in every round). Following the process() procedure for p, we obtain that synch p = false in round r + 2, which means that process p receives NO from AD(2) in round r + 2, contradiction.

Lemma 2. Let p and q be two processes in P . Then, for all rounds k < l ≤ r, Active r p [l] ∩ F ailed r q [k] = ∅, and Active r p [l] ∩ F ailed r q [k] = ∅, where the Active and Failed sets are seen from the end of round r.

Proof. We prove that, given r ≥ l > k, Active r p [l] ∩ F ailed r q [k] = ∅. Assume, for the sake of contradiction, that there exist rounds k < l ≤ r and a processor s such that s ∈ Active r p [l] ∩ F ailed r q [k]. Lemma 1 ensures that p and q communicate in round r + 1, therefore it follows that s ∈ F ailed

r+2 p [k]. This means that s ∈ Active r+2 p [l] ∩ F ailed r+2 p [k],
for k < l, therefore p cannot receive YES in round r + 2, contradiction.

The next lemma provides a sufficient condition for a set of processes to share a synchronous execution up to the end of some round R. The proof follows from the observation that the required synchronous execution E can be constructed by exactly following the contents of the Active and Failed sets by processes at every round in the execution.

Lemma 3. Let E be an R-round execution in ES(N, t), and P be a set of processes in Π such that, at the end of round R, the following two properties are satisfied:

1. For any p and q in P , and any round r ∈ {1, 2, . .

. , R -1}, Active R p [r + 1] ∩ F ailed R q [r] = ∅. 2. | p∈P Active R p [R]| ≥ N -t.
Then there exists a synchronous execution E which is indistinguishable from the views of processes in P at the end of round R.

Finally, we prove that if a set of processes P receive YES from AD(2) at the end of some round R+2, then there exists a synchronous execution consistent with their views at the end of round R, for any R > 0, i.e. that AD(2) is indeed a 2-round asynchrony detector. The proof follows from the previous results. Lemma 4. Let R > 0 be a round and P be a set of processes that receive YES from AD(2) at the end of round R + 2. Then there exists a synchronous execution consistent with their views at the end of round R.

5 Generating Indulgent Algorithms for Colorless Tasks Intuitively, a colorless task is a terminating task in which any process can adopt any input or output value of any other process, without violating the task specification, and in which any (decided) output value is a (proposed) input value. We also assume that the output values have to verify a predicate P, such as agreement or k-agreement. For example, in the case of consensus, the predicate P states that all output values should be equal. Let val (V ) be the set of values in a vector V . We precisely define this family of tasks as follows.

A colorless task satisfies the following properties: (1) Termination: every correct process eventually outputs;

Transformation Description

We present an emulation technique that generates an indulgent protocol in ES(N, t) out of any protocol in S(N, t) solving a given colorless task T , at the cost of two communication rounds. If the system is not synchronous, the generated protocol will run a given backup protocol Backup which ensures safety, even in asynchronous executions. For example, if an protocol solves synchronous consensus in t + 1 rounds (i.e. it is optimal), then the resulting protocol will solve consensus in t + 3 rounds if the system is initially synchronous. Otherwise, the protocol reverts to a safe backup, e.g. Paxos [START_REF] Lamport | Generalized consensus and paxos[END_REF], or ASAP [START_REF] Alistarh | How to solve consensus in the smallest window of synchrony[END_REF].

We fix a protocol A solving a colorless task in the synchronous model S(N, t). The running time of the synchronous protocol is known to be of R rounds. In the first phase of the transformation, each process p runs the AD(2) asynchrony detector in parallel with the protocol A, as long as the detector returns a YES indication at every round. Note that the protocol's messages are included in the detector's messages (or viceversa), preventing the possibility that the protocol encounters asynchronous message deliveries without the detector noticing. If the detector returns NO during this phase, the process stops running the synchronous protocol, and continues running only AD [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]. If the process receives YES at the end of round R + 2, then it returns the decision value that A produced at the end of round R4 .

On the other hand, if the process receives NO from AD(2) in round R + 2, i.e. asynchrony was detected, then the process will run the second phase of the transformation. More precisely, in phase two, the process will run a backup agreement protocol that tolerates periods of asynchrony (for example, the K4 protocol [START_REF] Alistarh | Of choices, failures and asynchrony: The many faces of set agreement[END_REF], if the task is k-set agreement). The main question is how to initialize the backup protocol, given that some of the processes may have already decided in phase one, without breaking the properties of the task. We solve this problem as follows.

Let Supp (the support set) be the set of processes that received YES from AD(2) in round R + 1 that process p receives messages from in round R + 2. There are two cases. (1) If the set Supp is empty, then the process starts running the backup protocol using its initial proposal value. (2) If the set Supp is non-empty, then the process obtains a new proposal value as follows. It picks one process from Supp and adopts its state at the end of round R -1. Then, in round R, it simulates receiving the messages in

j∈Supp msgSet R+1 j [R],
where we maintain the notation used in Section 4. We will show that in this case, the simulated protocol A will necessarily return a decision value at the end of simulated round R. The process p then runs the backup protocol, using as initial value the decision value resulting from the simulation of the first R rounds.

Proof of Correctness

We now prove that the resulting protocol verifies the task specification. The proofs of termination, validity, and the colorless property follow from the properties of the A and Backup protocols, therefore we will concentrate on proving that the resulting protocol also satisfies the output predicate P.

Theorem 1 (Output Predicate). The indulgent transformation protocol satisfies the output predicate P associated to the task T .

Assume for the sake of contradiction that there exists an execution in which the output of the transformation breaks the output predicate P. If all process decisions are made at the end of round R + 2, then, by the global detection property of AD( 2), there exists a synchronous execution of A in which the same outputs are decided, which break the predicate P, contradiction. If all decisions occur after round R + 2, first notice that, by the validity and colorless properties, the inputs processes propose to the Backup protocol are always valid inputs for the task. It follows that, since all decisions are output by Backup, there exists an execution of the Backup protocol in which the predicate P is broken, again a contradiction.

Therefore, at least one process outputs at the end of round R+2, and some processes decide at some later round. We prove the following claim.

Claim. If a process decides at the end of round R + 2, then (i) all correct processes will have a non-empty support set Supp and (ii) there exists an R-round synchronous execution consistent with the views that all correct processes adopt at the end of round R + 2.

Proof (Sketch). First, let d be a process that decides at the end of round R + 2. Then, in round R + 2, process d received a message from at least Nt processes that got YES from AD(2) at the end of round R + 1. Since N ≥ 2t + 1, it follows that every process that has not crashed by the end of round R + 2 will have received at least one message from a process that has received YES from AD(2) in round R + 1; therefore, all non-crashed processes that get NO from AD(2) in round R + 2 will execute case 2, which ensures the first claim.

Let Q = {q 1 , . . . , q ℓ } be the non-crashed processes at the end of round R+2. By the above claim, we know that these processes either decide or simulate an execution. We prove that all views simulated in this round are consistent with a synchronous execution up to the end of round R, in the sense of Lemma 3. To prove that the intersection of their simulated views in round R contains at least (Nt) messages, notice that the processes from which process d receives messages in round R + 2 are necessarily in this intersection, since otherwise process d would receive NO in round R + 2.

To prove the first condition of Lemma 3, note that process d's view of round R, i.e. the set msgSet R+2 d [R], contains all messages simulated as received in round R by the processes that receive NO in round R + 2. Since Nt > t, every process that receives NO in round R + 2 from the detector also receives a message supporting d's decision in round R + 2; process d receives the same message and does not notice any asynchrony.

Therefore, we can apply Lemma 3 to obtain that there exists a synchronous execution of the protocol A in which the processes in Q obtain the same decision values as the values obtained through the simulation or decision at the end of round R + 2.

Returning to the proof of the output predicate, recall that there exists at least process d which outputs at the end of round R + 2. From the above Claim, it follows that all non-crashed processes simulate synchronous views of the first R rounds. Therefore all non-crashed processes will receive an output from the synchronous protocol A. Moreover, these synchronous views of processes are consistent with a synchronous execution, therefore the set of outputs received by non-crashed processes verifies the predicate P. Hence all the inputs that the processes propose to the Backup protocol verify the predicate P. Since Backup respects validity, it follows that the outputs of Backup will also verify the predicate P.

6 A Protocol for Strong Indulgent Renaming

Protocol Description

In this section, we present an emulation technique that transforms any synchronous renaming protocol into an indulgent renaming protocol. For simplicity, we will assume that the synchronous renaming protocol is the one by Herlihy et al. [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF], which is timeoptimal, terminating in ⌈log N ⌉ + 1 synchronous rounds. The resulting indulgent protocol will rename in N names using ⌈log N ⌉ + 3 rounds of communication if the system is initially synchronous, and will eventually rename into N + t names if the system is asynchronous, by safely reverting to a backup constituted by the asynchronous renaming algorithm by Attiya et al. [START_REF] Attiya | Renaming in an asynchronous environment[END_REF]. Again, the protocol is structured into two phases. First Phase. During the first ⌈log N ⌉ + 1 rounds, processes run the AD(2) asynchrony detector in parallel with the synchronous renaming algorithm. Note that the protocol's messages are included in the detector's messages. If the detector returns NO at one of these rounds, then the process stops running the synchronous algorithm, and continues only with the detector. If at the end of round [log N ] + 1, the process receives YES from AD(2), then it also receives a name name i as the decision value of the synchronous protocol. Second Phase. At the end of round [log N ] + 1, the processes start the asynchronous renaming algorithm of [START_REF] Attiya | Renaming in an asynchronous environment[END_REF]. More precisely, each process builds a vector V with a single entry, which contains the tuple v i , name i , J i , b i , r i , where v i is the processes' initial value. The entry name i is the proposed name, which is either the name returned by the synchronous renaming algorithm, if the process received YES from the detector, or ⊥, otherwise. The entry J i counts the number of times the process proposed a name-it is 1 if the process has received YES from the detector, and 0 otherwise; b i is the decision bit, which is initially 0. Finally, r i is the round number 5 when the entry was last updated, which is in this case ⌈log n⌉ + 1.

The processes broadcast their vectors V for the next two rounds, while continuing to run the asynchrony detector in parallel. The contents of the vector V are updated at every round, as follows: if a vector V ′ containing new entries is received, the process adds all the new entries to its vector; if there are conflicting entries corresponding to the same process, the tie is broken using the round number r i .

If, at the end of round ⌈log N ⌉ + 3 the process receives YES from the detector, then it decides on name i . Otherwise, it continues runnning the AttiyaRenaming algorithm until decision is possible.

Proof of Correctness

The first step in the proof of correctness of the transformation provides some properties of the asynchronous renaming algorithm of [START_REF] Attiya | Renaming in an asynchronous environment[END_REF]. More precisely, the first Lemma states that the asynchronous renaming algorithm remains correct even though processes propose names initially, that is at the beginning of round ⌈log N ⌉ + 2. The proof follows from an examination of the protocol and proofs from [START_REF] Attiya | Renaming in an asynchronous environment[END_REF].

Lemma 5. The asynchronous renaming protocol of [START_REF] Attiya | Renaming in an asynchronous environment[END_REF] ensures termination, name uniqueness, and a name space bound of N + t, even if processes propose names at the beginning of the first round.

The previous Lemma ensures that the transformation guarantees termination, i.e. that every correct process eventually returns a name. The non-triviality property of the asynchrony detector ensures that the resulting algorithm will terminate in ⌈log N ⌉ + 3 rounds in any synchronous run. In the following, we will concentrate on the uniqueness of the names and on the bounds on the resulting namespace. We start by proving that the protocol does not generate duplicate names.

Lemma 6 (Uniqueness). Given any two names n i , n j returned by processes in an execution, we have that n i = n j . Proof (Sketch). Assume for the sake of contradiction that there exists a run in which two processes p i , p j decide on the same name n 0 . First, we consider the case in which both decisions occurred at round ⌈log N ⌉ + 3, the first round at with a process can decide using our emulation. Notice that, if a decision is made, the processes necessarily decide on the decision value of the simulated synchronous protocol 6 . By the global detection property of AD(2) it then follows that there exists a synchronous execution of the synchronous renaming protocol in which two distinct processes return the same value, contradicting the correctness of the protocol. Similarly, we can show that if both decisions occur after round ⌈log N ⌉ + 3, we can reduce the correctness of the transformation to the correctness of the asynchronous protocol.

Therefore, the remaining case is that in which one of the decisions occurs at round ⌈log N ⌉ + 3, and the other decision occurs at a later round, i.e. it is a decision made by the asynchronous renaming protocol. In this case, let p i be the process that decides on n 0 at the end of round ⌈log N ⌉ + 3. This implies that process p i received YES at the end of round ⌈log N ⌉ + 3 from AD(2). Therefore, since p i sees a synchronous view, there exists a set S of at least Nt processes that received p i 's message reserving name n 0 in round ⌈log N ⌉ + 2. It then follows that each non-crashed process receives a message from a process in the set S in round ⌈log N ⌉ + 3. By the structure of the protocol, we obtain that each process has the entry v i , n 0 , 1, 0, ⌈log N ⌉ + 1 in their V vector at the end of round ⌈log N ⌉ + 3. It follows from the structure of the asynchronous protocol that no process other than p i will ever decide on the name n 0 at any later round, which concludes the proof of the Lemma.

Finally, we prove that the transformation ensures the following guarantees on the size of the namespace.

Lemma 7 (Namespace Size). The transformation ensures the following properties: [START_REF] Guerraoui | Indulgent algorithms[END_REF] In synchronous executions, the resulting algorithm will rename in a namespace of at most N names. [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] In any execution, the resulting algorithm will rename in a namespace of at most N + t names. Proof (Sketch). For the proof of the first property, notice that, in a synchronous execution, any output combination for the transformation is an output combination for the synchronous renaming protocol. For the second property, let ℓ ≥ 0 be the number of names decided on at the end of round ⌈log N ⌉ + 3 in a run of the protocol. These names are clearly between 1 and N . Lemma 6 guarantees that none of these names is decided on in the rest of the execution. On the other hand, Lemma 5 and the namespace bound of N + t for the asynchronous protocol ensure that the asynchronous protocol decides exclusively on names between 1 and N + t, which concludes the proof of the claim.

Conclusions and Future Work

In this paper, we have introduced a general transformation technique from synchronous algorithms to indulgent algorithms, and applied it to obtain indulgent solutions for a large class of distributed tasks, including consensus, set agreement and renaming. Our results suggest that, even though it is generally hard to design asynchronous algorithms in fault-prone systems, one can obtain efficient algorithms that tolerate asynchronous executions starting from synchronous algorithms.

In terms of future work, we first envision generalizing our technique to generate algorithms that also work in a window of synchrony, and investigating its limitations in terms of time and communication complexity. Another interesting research direction would be to analyze if similar techniques exist in the case of Byzantine failures-in particular, if, starting from a synchronous fault-tolerant algorithm, one can obtain a Byzantine fault-tolerant algorithm, tolerating asynchronous executions.

2 for 3 FFig. 1 .

 231 Fig. 1. The AD(2) asynchrony detection protocol.

5. 1

 1 Task DefinitionIn the following, a task is a tuple (I, O, ∆), where I is the set of vectors of input values, O is a set of vectors of output values, and ∆ is a total relation from I to O. A solution to a task, given an input vector I, yields an output vector O ∈ O such that O ∈ ∆(I).

( 2 )

 2 Validity: for every O ∈ ∆(I), val (O) ⊆ val (I); (3) The Colorless property: If O ∈ ∆(I), then for every I ′ with val (I ′ ) ⊆ val (I) : I ′ ∈ I and ∆(I ′ ) ⊆ ∆(I). Also, for every O ′ with val (O ′ ) ⊆ val (O) : O ′ ∈ O and O ′ ∈ ∆(I). Finally, we assume that the outputs satisfy a generic property (4) Output Predicate: every O ∈ O satisfies a given predicate P. Consensus and k-set agreement are canonical examples of colorless tasks.

Roadmap. In Section 2, we present the model, while Section 3 presents an overview of related work. We define asynchrony detectors in Section 4. Section 5 presents the transformation for colorless agreement tasks, while Section 6 applies it to the renaming problem. In Section 7 we discuss our results. Due to space limitations, the proofs of some basic results are omitted, and we present detailed sketches for some of the proofs.

Since AD(2) returns YES at process p at the end of round R + 2, it follows that it must have returned YES at p at the end of round R as well. The local detection property of the asynchrony detector implies that the protocol A has to return a decision value, since it executes a synchronous execution.

This entry in the vector is implied in the original version of the algorithm[START_REF] Attiya | Renaming in an asynchronous environment[END_REF].

A simple analysis of the asynchronous renaming protocol shows that a process cannot decide after two rounds of communication, unless it had already proposed a value at the beginning of the first round.

Acknowledgements

The authors would like to thank Prof. Hagit Attiya and Nikola Knežević for their help on previous drafts of this paper, and the anonymous reviewers for their useful feedback.


Dan Alistarh
email: alistarh@epfl.ch

Hagit Attiya

Rachid Guerraoui
email: guerraoui@epfl.ch

Corentin Travers
email: travers@labri.fr

Early Deciding Synchronous Renaming in O(log f ) Rounds or Less

Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the running time adapts to the actual number of failures f in the execution. We show that, surprisingly, renaming can be solved in constant time if the number of failures f is limited to O( √ n), while for general f ≤ n -1 renaming can always be solved in O(log f ) communication rounds. In the wait-free case, i.e. for f = n -1, our upper bounds match the Ω(log n) lower bound of Chaudhuri et al. [13].

Introduction

Unique names, or identifiers, are a fundamental prerequisite for solving a variety of problems in distributed computing. While in many settings unique names are available, they often come from a very large, practically unbounded namespace, which reduces their usefulness. The renaming problem [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], in which a set of processes need to be assigned names from a namespace of small size, is one of the fundamental problems in distributed computing, and a significant amount of work, e.g. [1, 2, 4, 6-10, 17, 18], studied its solvability and complexity in faultprone distributed systems.

Much of the work on the renaming problem, whether in shared-memory [START_REF] Alistarh | Optimal-time adaptive strong renaming, with applications to count-ing[END_REF][START_REF] Attiya | Adaptive and efficient algorithms for lattice agreement and renaming[END_REF] or in message-passing systems [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], has focused on the asynchronous case, in which the processes' steps or messages may be delayed arbitrarily by the scheduler. However, real world systems experience long periods where delays are bounded, and inter-process communication is synchronous, even though processes may still fail by crashing. The complexity of renaming in such a synchronous setting, where processes communicate by message-passing, was investigated by Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] and Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. In brief, they found that for n processes, up to n -1 of which may fail by crashing, there exist algorithms that assign a tight namespace of names 1, . . . , n names in O(log n) rounds of communication. Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] also showed a matching lower bound.

The analysis in these papers only focused on the case where the maximum number of processes, n -1, may fail by crashing during an execution. However, the Ω(log n) lower bound of [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] does not exclude algorithms that terminate faster when the actual number of failures f in the execution is less than n -1. Such speculative algorithms, also known as early deciding, are known to exist for consensus [START_REF] Pease | Reaching agreement in the presence of faults[END_REF] and set agreement [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF]. Early-deciding protocols achieve consensus in O(f ) communication rounds [START_REF] Dolev | Early stopping in byzantine agreement[END_REF], and k-set agreement in O( f k ) rounds [START_REF] Gafni | The complexity of early deciding set agreement[END_REF].

It is therefore natural to ask what is the time complexity of early deciding synchronous renaming in a message-passing system. The answer to this question does not appear trivial: for example, a successful strategy for renaming [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] was for each process to obtain a new bit from its name by running a simple one round symmetry-breaking protocol-after Θ(log n) rounds, each process has a unique name from 1 to n. However, it is hard to speed up this approach to obtain more bits for the process's name in rounds where there are few failures, without breaking name uniqueness. Another approach [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], where each process proposes a name in each round based on what every other process proposed in previous rounds, until there are no collisions, turns out to be very difficult to analyze when the adversary has a limited budget of f failures.

In this paper, we overcome these challenges, and present the first earlydeciding upper bounds for renaming. In short, we find that the complexity of the problem is strongly coupled with the relation between n, the number of processes and f , the failure budget of the adversary. We show that there exists an algorithm that ensures a tight namespace of n names, and terminates in a constant number of rounds in every execution where f ∈ O( √ n), and, in O(log f ) rounds, otherwise. The existence of a constant-time renaming algorithm for non-trivial f is surprising, since the early-deciding bounds for consensus [START_REF] Dolev | Early stopping in byzantine agreement[END_REF] and set agreement [START_REF] Gafni | The complexity of early deciding set agreement[END_REF] are linear in f irrespective of the relation with the total number of processes n.

Our second result is an algorithm that improves on the constants in the asymptotic notation, terminating in log f + 5 rounds, and assigning names from 1 to 2n.

The first algorithm is a slight modification of a result by Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. His protocol is based on a novel connection between synchronous renaming and the approximate agreement problem [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]. In brief, processes assign temporary ranks to each process identifier that they receive, and perform approximate agreement to converge on an approximate rank for each initial process identifier, within a carefully chosen approximation factor. Each process returns this approximate rank, rounded to the nearest integer, as its name: the protocol ensures that, upon termination, the approximate ranks are far enough apart so that no two processes decide on the same rank. Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF] showed that this protocol ensures a tight namespace, preserves the order of the initial identifiers, and terminates in O(log n) rounds in all executions.

Our main contribution is analyzing this protocol for general f , and showing that it terminates in constant time if f ∈ O( √ n), and in O(log f ) rounds otherwise. Our analysis characterizes the optimal adversarial strategy for arbitrary values of the parameters n and f -we achieve this by carefully bounding the approximation factor of the approximate agreement protocols relative to the number of failures that the adversary expends in each round, showing that this factor goes down fast, and the algorithm terminates very quickly, if the adversary does not fail a significant fraction of the processes in each round.

The second renaming algorithm we present is simpler, and achieves better constants in the asymptotic notation, while relaxing the size of the namespace to 2n. The protocol is split in two phases: In the first phase, each process identifies a set of names it is interested in, whose size is proportional to the number of failures that the adversary expends in the phase. In the second phase, processes proceed to progressively halve the size of the set of names they are interested in, until each set is a singleton. At this point, each process may adopt the single name in its set. The key technical difficulty is in assigning each process the "right" set of names at the end of the first phase, so that there are always enough names for the set of participants. To ensure this, we need to relax the total size of the namespace that processes are interested in to be of size 2n. The halving procedure in the second phase is similar to the O(log n) round algorithm by Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF].

We therefore show that the time complexity of early-deciding renaming is upper bounded by O(log f ) synchronous rounds for general f , and can be constant for non-trivial f ∈ O( √ n). Both algorithms are adaptive, since they do not know the number of participants n in advance; they also adapt to the number of failures f in the execution.

Roadmap. We present the problem statement and the model in Section 2, and give an overview of related work in Section 3. In Section 4, we present the analysis of the tight renaming algorithm, while the second algorithm can be found in Section 5. We conclude with a discussion of open questions in Section 6.

Model and Problem Statement

Model. We consider a standard synchronous message passing system with n processes p 1 , . . . , p n . Initially, processes have unique identifiers from a namespace of unbounded size. Time is divided into rounds, and the processes' clocks are synchronized. Each round proceeds as a sequence of send, receive, and process steps, in which processes may send and receive messages, and perform local computation if necessary. We assume that at most t < n processes may fail by crashing. If crashed, a process stops taking further steps in the execution; a process may fail to send any subset of its messages in rounds in which it crashes. Let f denote the number of failures in the current execution. We focus on early-deciding algorithms, that adapt their time complexity to the actual number of failures in the execution, i.e. whose running time is a function of f only.

Renaming. The renaming problem [START_REF] Attiya | Renaming in an asynchronous environment[END_REF] requires that each correct process eventually returns a name, and that the names returned should be unique. The size of the resulting namespace should only depend on the parameters n. The tight renaming problem requires that the size of the namespace be exactly n; otherwise, we say that the solution is loose.

Approximate Agreement. Consider a small real number ǫ > 0. In the ǫapproximate agreement problem [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF], each process p i starts with a proposal v i , which is a real number. An approximate agreement algorithm must satisfy the following properties: (1) Each correct process eventually decides a value d i ; (2) For any correct processes p i and p j , |d id j | ≤ ǫ; (3) For any correct process p ℓ , there are processes p i and p j with initial values v i and v j , such that

v i ≤ d ℓ ≤ v j .
Notation. Throughout this paper, log denotes the logarithm base two. Moreover, we write log f instead of ⌊log f ⌋. To simplify notation, we assume that f ≥ 1, which allows us to consider running times of O(log f ) rounds.

Related Work

The renaming problem was introduced in [START_REF] Attiya | Renaming in an asynchronous environment[END_REF], where the authors also provide a wait-free solution using (2n -1) names in an asynchronous message-passing system, and show that at least (n + 1) names are required in the wait-free case. This lower bound on the namespace size for the case of asynchronous solutions was improved to (2n -2) by Herlihy and Shavit [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF], and Rajsbaum and Castañeda [START_REF] Castañeda | New combinatorial topology bounds for renaming: The lower bound[END_REF]. (This lower bound holds when n is a power of a prime number.)

Considerable research has analyzed the upper and lower bounds for renaming in asynchronous setting, in particular in shared memory e.g., [START_REF] Alistarh | Optimal-time adaptive strong renaming, with applications to count-ing[END_REF][START_REF] Alistarh | The complexity of renaming[END_REF][START_REF] Attiya | Adaptive and efficient algorithms for lattice agreement and renaming[END_REF][START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF][START_REF] Brodsky | Fully-adaptive algorithms for long-lived renaming[END_REF][START_REF] Burns | The ambiguity of choosing[END_REF][START_REF] Moir | Fast, long-lived renaming (extended abstract)[END_REF]. For a detailed description of these results, we refer the reader to e.g., [START_REF] Alistarh | Optimal-time adaptive strong renaming, with applications to count-ing[END_REF].

On the other hand, there has been relatively little work on the complexity of synchronous renaming. Herlihy et al. [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] considered wait-free renaming in a synchronous message-passing system, identical to the one we consider in this paper. They prove a lower bound of Ω(log n) rounds on the time complexity of the problem in runs where t = n-1 processes may crash, and provide a matching algorithm that achieves tight renaming with time complexity ⌊log n⌋ + 3 in every execution. In contrast, our algorithms are early deciding, in that they adapt to the actual number of failures f in the current execution, deciding in O(log f ) rounds. On the other hand, the lower bound argument of Herlihy et al. [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] applies to our algorithms as well 5 , implying a lower bound of Ω(log n) rounds in executions where f = n -1.

In [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF], Okun presents a synchronous message-passing algorithm for tight renaming algorithm with O(log n) time complexity. His algorithm is based on a procedure propose i (vi, ǫ) ; novel connection between renaming and approximate agreement. In brief, processes perform approximate agreement on the rank of each initial identifier, until they are certain that no two processes obtain the same rank. In this paper, we extend this technique by providing a new analysis for minor variation of his algorithm, proving that its running time is in fact O(log f ) in executions with f failures, which is asymptotically optimal.

1 di ← vi;

A Tight Renaming Algorithm

In this section, we analyze the tight renaming algorithm of Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF] and prove that it terminates in O(log f ) rounds, where f < n is the number of processes that the adversary crashes in the current execution. We begin with a short description of the algorithm; a detailed exposition can be found in the original paper [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF].

Algorithm Overview. The algorithm is based on a novel connection between renaming and the approximate agreement problem. First, a simple synchronous approximate agreement (AA) algorithm is introduced. Then, the algorithm runs in parallel at most n separate instances of this approximate agreement algorithm, one for each process in the system. The goal is to agree on an approximate rank for each process's initial identifier, which will be the value decided by the corresponding approximate agreement algorithm, rounded to the nearest integer. The key ingredient is to run the approximate agreement algorithm for long enough to ensure that the decision values of the AA protocols corresponding to each initial identifier are sufficiently spaced, ensuring that the rank decided for each process is unique.

The Approximate Agreement Algorithm. The algorithm, whose pseudocode appears in Figure 1, proceeds as follows. Each process starts with an initial value v i and a desired approximation factor ǫ, which bounds the maximum desired skew between decided values. The process maintains an estimate d i of its decision value, which is updated in every round to the arithmetic average of all values received. Once all the estimates received in a round are within at most ǫ of each other, the process returns its current estimate. The Renaming Algorithm. Each process p i starts with an initial name v i . The algorithm, whose pseudocode appears in Figure 2, has two phases.

The first phase contains the first three rounds, in which processes exchange their identifiers, in order to identify the parameter n and the relative ranks of their identifiers.

In the second phase, which starts at round four, based on the information computed so far, each process proposes a rank for each participating process to a separate instance of the approximate agreement algorithm in Figure 1. Notice that all these agreement instances run in parallel; all messages by a process in a round (one for each AA protocol in which it participates) are packaged into a single composite message, which each process sends in each round. The approximation factor for all these agreement instances is 1/(10C 2 ), where C 2 is the number of distinct identifiers the process received in round 2 of the first phase. (This factor is chosen such that no two identifiers may receive the same final rank from the approximate agreement instances when rounded to the nearest integer.) The algorithm terminates when all the approximate agreement algorithms terminate, ensuring the desired approximation factor. Name uniqueness. We give a brief overview of the mechanism ensuring name uniqueness; a complete analysis can be found in [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. Recall that, for each initial identifier id, each process p proposes the rank of id multiplied by C 2 /C 3 as the initial value in id's instance of the AA protocol. Obviously, the processes' ranks for the same identifier may be distinct (as a consequence of failures in the first phase). However, a key observation is that they will be distinct in a consistent way: if p proposes rank 6 for id α, and rank 7 for id β > α, then another process q proposing rank 7 for id α will have to propose rank at least 8 for id β. Analyzing the AA protocol, this will imply that, given any process p, its decision values for distinct ids α < β will be at distance at least 1 from each other [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]Theorem 3].

This mechanism might still allow the possibility that two distinct processes decide on the same name when rounding their AA decision value to the nearest integer. This is handled by multiplying the initial ranks with C 2 /C 3 . This ratio is higher than 1 only when a processor observes crashes between the second and third rounds, and the algorithm ensures that for any ids α and β, their corresponding decision values at any two processes p and q are at distance > 1 from each other [19, Lemma 3]. In turn, this implies that no two processes may decide the same name.

Analysis. Our key observation is that the variant of the synchronous approximate agreement algorithm of Okun [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF] presented in Figure 1 guarantees the required approximation factor of 1/(10C 2 ) in a constant number of rounds when f > √ n/2, and O(log f ) rounds, otherwise. In turn, this implies that the renaming algorithm terminates within three additional rounds.

To prove this, we first introduce some notation. Let σ(S) be the diameter of a set S, i.e. max a,b∈S (|a -b|).

For any round r > 0 in the execution of the approximate agreement algorithm, let U r be the multiset of distinct values that processes that are active (i.e., send at least one message) in round r have in the beginning of the round.

Let f r be the number of processes that crash in round r; for convenience, denote f 0 = 0. Denote by δ r the fraction of processes that crash in round r from among the processes that did not crash before round r; that is,

δ r = f r /(n - r-1 i=0 f i )
We first state the following lemma, bounding the diameter of the set U r+1 depending on the diameter of U r and the fraction of processes that crash in round r; its proof follows [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]Lemma 1].

Lemma 1. σ(U r+1 ) ≤ 2δr+1 1-δr+1 • σ(U r ).
The next lemma bounds the number of rounds needed for the approximate agreement algorithm of Figure 1 to achieve a maximum diameter of ǫ = 1/(10n) for the set of decisions corresponding to each initial value, when starting with proposal sets of diameter ≤ n. The bound depends on f , the number of failures that the adversary expends in total, and on the number of failures f i which the adversary expends in each round i ≥ 1. 1, starting with an initial set of diameter σ(U 1 ) ≤ n, in which at most f processes crash. Let R be the number of rounds needed for the algorithm to reach a diameter ǫ ≤ 1/(10n). The following claims hold:

Lemma 2. Consider an execution of the approximate agreement algorithm of Figure

-If f ≤ √ n/2, then R is a constant. -If √ n/2 < f ≤ n -1, then R ≤ 5 log f + 10.
Proof. We assume n ≥ 6; the claim can be checked for n ≤ 5 by calculation. The first case is when f ≤ √ n/2. In this case, notice that the fraction of processes that fail in any round of the protocol is at most √ n/n, i.e. δ r ≤ √ n/n, for all r ≥ 1. In turn, by Lemma 1, the diameter of the set of values for the current instance of approximate agreement is reduced by at least 2δ r /(1δ r ) ≤ 1/( √ n -0.5) in each round r. Therefore, after the first 10 rounds, the diameter of this set is at most

n ( √ n -0.5) 10 ≤ 1 10n
, for any n ≥ 6.

Therefore the maximum diameter the end of round 10 is ≤ 1/(10n), as claimed.

In the second case, we assume that f > √ n/2. First, notice that δ r , the fraction of active processes that crash in a round r, can be greater than 1/2 in at most ⌊log 2 (f + 1)⌋ + 1 distinct rounds. Therefore, any execution of at least 5⌊log 2 (f + 1)⌋ + 10 rounds contains at least 4⌊log 2 (f + 1)⌋ + 9 rounds r in which δ r < 1/2. Lemma 1 implies that the diameter of the set U r at the end of these rounds is at most

n 2 4⌊log 2 (f +1)⌋+9 ≤ n 2 9 • (f + 1) 4 ≤ 1 10n for all n ≥ 1,
where the last step uses the fact that f ≥ √ n/2. Therefore, in this case, the number of rounds necessary to obtain a maximum diameter of at most 1/(10n) is O(log f ).

We conclude that the resulting renaming algorithm is early deciding, terminating in a constant number of rounds, when f ≤ √ n/2, and O(log f ) rounds, otherwise.

Theorem 1. For any f , 0 ≤ f ≤ n -1, let ℓ f = constant if f ≤ √ n/2
, and ℓ f = 5 log(f + 1) + 10, otherwise. Then the renaming algorithm in Figure 2 is a tight order-preserving renaming algorithm with time complexity O(ℓ f ) and message complexity O(n 2 ℓ f ) in executions where f processes fail by crashing.

Proof. We focus on early decision, since the other properties follow from Theorem 4 of [START_REF] Okun | Strong order-preserving renaming in the synchronous message passing model[END_REF]. First, recall that the initial value v for each approximate agreement algorithm is computed locally by each process as rank

V (α) • C 2 /C 3 . Since rank V (α)/C 3 ≤ 1
, by the definition of C 2 , we obtain that all initial values are between 1 and n. This also implies that our desired approximation factor ǫ is at most 1/(10n). Lemma 2 implies that all instances of approximate agreement that the renaming algorithm executes in parallel terminate in O(ℓ f ) rounds, with an approximation factor ǫ ≤ 1/(10n). We obtain that the renaming algorithm terminates in O(ℓ f ) rounds, as claimed.

A Loose Renaming Algorithm with Improved Round Complexity

In this section, we present a loose renaming algorithm that terminates in log f 1 +5 rounds and uses at most 2n names, where n is the number of participating processes and f 1 the number of failures that occur in the first round. Our algorithm extends the non-early deciding renaming algorithm by Chaudhuri, Herlihy, and Tuttle [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF]. The latter algorithm is tight; its round complexity, however, depends solely on n and not on the number of failures among the participating processes. Specifically, the namespace when n processes participate is [1, n] and the algorithm terminates in log n + 2 rounds. In the following, the algorithm of [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] is called the CHT-renaming algorithm.

Algorithm Overview. The pseudo-code of the algorithm appears in Figure 3. It contains two phases. In the first phase, which consists of the two first rounds (line 1-line 7), each process selects an interval of names in which it wishes to pick its final name. The size of each interval is upper-bounded by 4f 1 , where f 1 is the number of processes that fail during the first round. The second phase (line 8-line 16) consists of a variant of the CHT-renaming algorithm. Processes use this procedure to progressively shrink the interval of names they are interested in, until obtaining an interval of size 1. The algorithm ensures that no two processes obtain the same interval of size 1, i.e. a single name. Thus, each process can decide the unique name in its final interval. Moreover, it guarantees that in each round, processes holding the largest intervals reduce their interval by one half. Therefore our algorithm terminates in O(log f 1 ) rounds.

We begin with a brief description of the CHT-renaming algorithm and then explain how each process selects an initial interval of names.

Definitions and notations. Before describing the algorithm in more details, we introduce some notations, extending those in [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF]. An interval I of positive integers is well-formed if I is of the form [d2 j + 1, (d + 1)2 j ] for some positive integers d, j. Note that for every pair I, J of well-formed intervals, I ∩ J = ∅ =⇒ I ⊆ J ∨ J ⊆ I. Given a set I of well-formed intervals, we say that interval I ∈ I is maximal in I if for every J ∈ I, either I ∩ J = ∅ or J ⊆ I.

The CHT-renaming Algorithm Each process p maintains a well-formed interval of names I, which are the names p is interested in. In each round, process p sends its id and the interval it currently holds I. The intervals intersecting with I that p receives are stored in the set I (line 10). p also stores the set of ids of the processes that are conflicting with p, that is, processes that hold an interval intersecting with I in the set P (line 11). If I is maximal in I (line 12), I is split in half, and p picks the bottom half or the top half of I, denoted bot(I) and top(I) respectively, as its new interval (line 13-line 14). More precisely, the new interval of p is bot(I) if the rank of p's identity in P is smaller than |I| 2 . Otherwise, p selects top(I) as its new interval. Finally, if p observes that every interval sent in the round has size 1, it decides the unique name in its interval. Since in each round the size of maximal interval is at least divided by 2, the procedure renamei(idi) ; algorithm terminates after O(log c) rounds, where c is the size of the largest initial maximal interval. Name uniqueness relies on the following invariant, which is satisfied by the set of intervals I[r] held by the processes at the beginning of each round r: Invariant 1. For every I ∈ I[r], if m processes hold an interval I ′ ⊆ I, then m ≤ |I|. In particular, this means that I is large enough to allow processes with an interval I ′ ⊆ I to decide distinct names in the interval I.

In the original CHT-renaming, the initial interval of each process p is of the form [1, 2 b ], where 2 b is the least power of 2 larger than or equal to the number of participating processes from which p has received a message in the first round. The invariant above is thus initially true. In our algorithm, initial intervals are selected differently, but the invariant is still satisfied.

Selection of initial intervals. In the first round, process p broadcasts its id, and ranks its id among the ids it receives (line 2). Let rk p be the rank obtained by p. If, among the ids of the participating processes, the rank of the id of p is i, and f 1 is the number of failures that occur in the first round, then

i -f 1 ≤ rk p ≤ i. (1)
This is because p may miss at most f 1 messages from processes with id smaller than i. In the second round, p sends its rank together with its id. It then estimates, based on the ranks it receives, the number of failures that occur in the first round. To that end, p evaluates for each interval of names I the difference between the number of processes ranked in I and the size of I (line 4-line 5). The estimate est f of the number of failures is then the maximum over all differences. More precisely, est f = max

I⊆[1,rk max] i∈I h i -|I|.
where rk max is the largest rank received by p and h i is-to the knowledge of p-the number of processes that rank their id i in the first round. The estimation est f is upper-bounded by f 1 , the number f 1 of failures that occur in the first round. To see why, consider an interval I = [a, b]. We have:

i∈I h i ≤ |{q : a ≤ rk q ≤ b}| ≤ |{q : a -f 1 ≤ rank(id q , P ) ≤ b}| ≤ |I| + f 1 , ( 2
)
where P is the set of participating processes and rank(id q , P ) is the rank of id q among the ids of the processes in P . The last inequality follows from Equation 1.

Finally, p selects a well-formed interval. This is performed in two steps. First, p chooses two integers d, j such that the well-formed interval [d2 j + 1, (d + 1)2 j ] contains rk p , and 2 j is the least power of 2 larger than or equal to est f . However, by equation ( 2), at most 2 j + est f ≤ 2 j+1 processes may have their rank contained in [d2 j +1, (d+1)2 j ]. Then, in order to satisfy Invariant 1, p selects the interval I = [d2 j+1 + 1, (d + 1)2 j+1 ] as its initial interval. Since a process p ′ that selects an interval ⊆ I has its rank rk p ′ contained in [d2 j + 1, (d + 1)2 j ], at most 2 j+1 = |I| processes select intervals I ′ ⊆ I. Invariant 1 is thus satisfied, which preserves the correctness of the CHT-renaming algorithm. Finally, notice that the size of each initial interval is at most 4f 1 , where f 1 is the number of failures in the first round. Hence the total running time is O(log f 1 ) rounds.

The proof of correctness can be found in a companion technical report [START_REF] Alistarh | Early deciding synchronous renaming in O(log f ) rounds or less[END_REF].

Discussion

This paper presents the first early-deciding upper bounds for synchronous renaming. We show that, surprisingly, renaming can be solved in constant number of rounds if the number of failures f is limited to O( √ n), while in the general case, renaming can always be solved in O(log f ) communication rounds. In the wait-free case, i.e. for f = n -1, this upper bound is matched asymptotically by the Ω(log n) lower bound of Chaudhuri et al. [START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF].

It remains an open question whether this is tight for other values of f .

2 for 4 δ 7 Fig. 1 .

 2471 Fig. 1. The Approximate Agreement algorithm.

procedure renamei(vi) ; 1 / 2 broadcast(vi); 3 Cr 4 n ← C1; 5 V 7 /* Phase two */ for each round r ≥ 4 do 8 for every identifier id ∈ V do 9 13 Fig. 2 .

 12345789132 Fig. 2. The Tight Renaming Algorithm.

1 /* 3 / 7 I 8 / 17 Fig. 3 .

 1378173 Fig. 3. The Loose Renaming Protocol.

While the original lower bound of Herlihy et al.[START_REF] Chaudhuri | Wait-free implementations in message-passing systems[END_REF] applies only to comparison-based algorithms, an argument by Attiya et al.[START_REF] Attiya | Time bounds for decision problems in the presence of timing uncertainty and failures[END_REF] generalizes this bound to a wider class of algorithms, which includes the ones in this paper.

⋆ Supported in part by the Israel Science Foundation (grant number 1227/10). ⋆⋆ Additional supports from the ANR projects ALADDIN and DISPLEXITY.


X Torrelles

V Langlais

M De Santis

H Tolentino

Y Gauthier

Nanostructuring surfaces: deconstruction of Pt(110)-(1x2) surface by C60

Keywords:

When deposited on metal surfaces, C60 creates nanoholes. Grazing incidence X-rays diffraction reveals a c(4x4) reconstruction induced by C60 on Pt(110)-(1x2). While the initial (1x2) missing row is partially deconstructed, under each fullerene we find double atomic vacancy involving two Pt layers. The resulting interface is deeply modified with a 75% Pt occupancy and regularly distributed double vacancy. The orientation of the molecule is compatible with local surface cm symmetry with a pentagonal ring almost parallel to the surface while hexagonal rings are almost parallel to the (111) facets of the nanohole. The short nearest neighbor C60 distances increase the Van der Waals repulsion forces that are minimized by a charge transfer between molecule and substrate involving a large number of C-Pt bonds and a reduction of 6% of the apparent diameter of the C60 molecule.

2D molecular ordering is often accompanied by surface restructuring of the 2-3 topmost atomic layers: such a modified interface may thus be used for both surface moulding and surface nanopatterning, with relevant technological applications [1][2][3][4] . The mechanism of molecule's surface anchoring is usually quite complex due to the interplay between intermolecular bonds and moleculesubstrate interactions involving a large number of adsorption sites. This may result in either displacive substrate reconstructions, involving extensive mass transport, which can be accompanied by a structural deformation of the adsorbed molecules. Formation of vacancies has already been observed on Pt(111) 4 , Pd(110) [5][6] , Ag(110) 7 , Ag[111] 8 , and Au(110) 9 . The shape and size of the nanoholes affect the actual properties of C60. To fully understand the molecular film properties, the molecule-substrate system has to be considered as a whole and the isolated molecules properties cannot be simply transferred to the monolayer case. Grazing incidence X-rays diffraction (GIXRD) allows not only determining the substrate structure and C60 orientation, but also the nature of the bonds formed between C60 and Pt.

The Pt(110)-(1x2) missing row surface was prepared by argon sputtering and annealing (T = 970 K) cycles, followed by cooling down to 850 K under oxygen partial pressure. The resulting (1x2) domains size was of typically 2000 Å as determined from the scan width of the (0, ½, 0.05) reflection. C60 (purity 99.9%) was sublimated, from an alumina crucible kept at 750 K, on the Pt sample maintained at 810 K. The fullerene coverage was calibrated recording the C 273 /Pt 247 Auger peak-to-peak ratio. As previously reported 10 , this experimental procedure results in a single adsorbed fullerene layer on the surface. The spectra were collected at BM32 beamline 11 of the European Synchrotron Radiation Facility, ESRF. The X-ray beam was generated by a bending magnet, monochromatised with a water-cooled double crystal Si(111) monochromator and sagitally focused. The energy and size at the sample of the incident beam were set to 18.0 keV and 0.5 mm x 0.1 mm (horizontal x vertical dimensions at the sample surface) with a constant incidence angle of 0.25º. The integrated intensities were recorded by rocking the crystal around its surface normal. A total of 1775 reflections, specific to the c(4x4) structure, were measured, which reduced to 1221 after averaging of the equivalent reflections 12 involving 45 Fractional Order Rods (FORs) and 9 Crystal Truncation Rods (CTRs). The Pt(110) surface is described by lattice vectors (a 1 , a 2 , a 3 ) parallel to the [1-10], [001], and [110] directions, respectively, where a 1 =a 3 =a 0 /√2, a 2 =a 0 (a 0 = bulk lattice constant). H, K, L denote the coordinates of the corresponding reciprocal lattice vectors. The new lattice parameters corresponding to this c(4x4) cell become (a' 1 ,a' 2 ,a 3 )=(4*a 1 , 4*a 2 , a 3 ). The standard deviations  HKL of the structure factors F HKL were evaluated by the quadrature sum of a systematic error estimated close to 11% and statistical error [START_REF] Robinson | Handbook of Synchrotron Radiation[END_REF] . From the analysis of the experimental data the c2mm plane group symmetry was determined. Calculations were performed with a modified version of ROD 14 used to optimize the agreement fit factor  2 .

First of the all, the data analysis was performed without assumption taking into account that the substrate structure is a first order parameter, compared to the actual position and orientation of the molecule due to the atomic number difference. The initial calculations, using the CTRs and FORs, were based on the (1x2) reconstruction of the clean surface which fulfils the c2mm experimental symmetry. The atomic density of all sites in the three topmost layers was then let free to vary in order to find out which atomic positions were actually occupied by Pt atoms. This procedure was carried out to determine the shape and size of the nanoholes, if any, hosting the molecule and compatible with the measured symmetry. The final analysis included 48 independent Pt atoms distributed over 5 layers and one molecule. We determined a total of 62 positional coordinates for bulk atoms simultaneously with the height of the C60 and 3 Euler angles for its orientation. Seven isotropic thermal vibration parameters [START_REF]Pt atoms to both types of rows in the top layer: BPt-top-part = 9 Å 2 (partially filled missing row) and BPt-top-filled = 6 Å 2 (filled row). Deeper layers were given the following values: BPt-2 = 2 Å 2 , BPt-3 = 0.7 Å 2[END_REF] were also optimized (one for the fullerenes, two for the topmost Pt layer and one for each of the 4 deeper Pt layers). In figure 1 is depicted the substrate model respecting the experimental symmetry consisting of a Pt top layer with complete rows alternating with half filled ones yielding a 75% occupancy with double vacancies alternating with Pt doublets. The molecules were then considered in a second step, with C60 supposed to reside in the optimum substrate configuration (fig. 1) and compatible with a c2mm symmetry (configuration C2 of Fig. 2). The c(4x4) unit cell contains one fullerene and an unique nanohole: as a consequence, in this dense quasi-hexagonal phase, all C60 have the same orientation and the same double vacancy adsorption site. As the fit agreement with this C2 model was moderate ( 2  2.1) the surface symmetry was released to cm, with the mirror plane parallel to the [1-10] direction. The lowest  2value ( 1.5) was obtained with the C1configuration model (Fig. 2a) and the presence of two mirrored domains to reproduce the experimental c2mm symmetry. In the final stage, C60 balls were allowed to rotate, around an axis parallel to [001] direction, and translate, parallel to [1-10] direction, with respect to the initial C2 adsorption configuration. The final configuration of the system is shown in Fig. 3 while Fig. 4 shows some representative data of the fit quality. The C60 molecules are located on the biatomic Pt-surface holes with a pentagon almost parallel to the surface on the bridge sites of the second Pt layer. The C60 orientation (C1) is achieved by rotating the molecule by approximately -52º with respect to the C2-orientation around a [001] axis while shifting it by 0.5 Å along [1-10] direction. On the side view of the fig. 3, the Pt-Pt bonds were removed to better visualize the C-Pt bonds. The corresponding atomic coordinates of the Pt atoms in the three outermost layers and those of the C-atoms of the C60 in the cm asymmetric unit cell are given in Table 1. The C60 molecules are NOT embedded into the holes and stand ~0.2 Å above the topmost Pt surface layer, close to the center of the double vacancy. The first Pt-Pt interlayer distance, 1.30 Å, is significantly shorter than the bulk distance (1.375 Å) which could be due to the presence of the additional atoms in the initial (1x2) missing row, however, this distance is much larger than for the clean surface [START_REF] Fery | [END_REF] (~1.1 Å). The most stable C60 configuration (referred as C1 in fig. 2) yields 15 C-Pt bonds with lengths ranging from 2.1 to 2.6 Å with an average bond distance of 2.4  0.1 Å. Four C-atoms have C-Pt bond lengths lower than 2.15 Å: two of them are linked to atoms (labeled as Pt1-1) of the partially filled row while the other two (those of the 5:6 bond) are linked to Pt atoms in bridge site of the second layer (Pt2-1) (see table 1 and Fig. 2a). These two strong bonds between C60 and Pt1-1 are compensated by the other 5 C-Pt bonds on the other side of the molecule also identified as black C-atoms in fig. 2a. The molecular stability is achieved by 15 C-Pt bonds that redistribute the molecule-substrate charge transfer via a large contact area, and the coexistence of different types of covalent bonds 18 : the different bond lengths fix the molecule on the surface by minimizing the surface stress at the interface. This fact is supported by the atomic shifts off the "ideal" bulk positions of the Pt atoms at the reconstructed surface, as observed in Table 1. The effect of this strong bonding shows up as an apparent ~6% reduction of the C60 diameter, as obtained from the refinement procedure. This behavior has already been observed 19 by scanning tunneling microscopy (STM). Our STM images 10 and X-Ray diffraction results shed new light on the C60 interaction with the Pt(110) surface. Indeed, while we conclude to similar -albeit not identicalconfiguration for the C60 orientation with respect to the surface, the outcome of the diffraction analysis is quite at ode with density functional theory (DFT) predictions. The models taken in consideration by the DFT calculations 20 are the following: (1) c(4x4)-C60 on (1x2)-Pt, (2) chemisorbed C60 on bi-and tri-atomic vacancies on (1x1)-Pt(110) and (3) C60 adsorbed on (1x1)-Pt without vacancies. The correct determination of both Pt atoms arrangement and C60 molecular orientation could not be achieved by DFT for the c(4x4) phase due to the wrong choice of the starting models to explain the STM images. The total energy of the system (molecules + substrate) depends on the correct choice of the vacancies distribution on Pt surface, atomic relaxations and on molecular orientation. While in the calculations, the relaxations are properly taken into account by considering an adequate number of Pt layers, DFT leads to unreliable results due to the wrong interface structure. Moreover, the DFT surprisingly prefers model (3), as the one which best agrees with STM images, instead of models ( 1) and ( 2) that described the correct c(4x4)-C60 arrangement and the correct double vacancies on Pt, respectively.

On Pd(110), C60 is supposed to adsorb on vacancies formed by Pd atoms released out of the first or the two first layers 5,6 . Regarding the molecular orientation, the adsorption on Pd and Pt presents a great similarity. Indeed, in both cases, the C60 stick to the surface through or close to a 5:6 bond. In addition, nanoholes formation is also observed on Au(110) upon C60 adsorption 21 . Since Pt has a lattice parameter between those of Au and Pd, one could reasonably expect a similar type of C60 induced vacancies on Pt than those already observed on fcc(110) metals as demonstrated from our X-ray diffraction analysis. The present results -biatomic vacancy model -have the advantage to give a coherent overall scheme for the fullerene-substrate configuration on large lattice constant fcc metals. A clear outcome of the 2-fold vacancy formation is that it allows maximum coordination as compared to the (1x2) case or any other substrate configuration with less dense surface layers or local environments. In this respect, the formation of nanoholes is also much more favorable than a flat layer that might occur in case of dominant molecule-molecule interaction and weak adsorbate-substrate interaction yielding a perfect hcp fullerene layer (never observed).

In conclusion, the structural properties of c(4x4)-C60/Pt(110) system have been studied by grazing incidence X-ray diffraction. The atomic arrangement at the interface of the topmost substrate atoms has been determined as well as the optimum C60 configuration. The interaction between the topmost Pt surface atoms with the fullerene molecules induces a distribution of nanoholes used as 2D template to host the quasi-hexagonally packed C60 molecules. The molecules induce a Pt surface de-reconstruction of the (1x2) missing rows that are 50% re-filled with Pt atoms. The large distribution of C-Pt bond lengths, between 2.1 and close to 2.6 Å, indicates delocalization of the charge from the molecule to the substrate among a rather large contact interface area. The interaction between C60 molecules with the topmost Pt surface layers results in a less stressed interface structure when the cm C60orientation (C1 configuration) is considered. The molecule is laterally shifted by the 0.5 Å along [1-10] direction with one of its pentagon rings almost parallel to the surface on Pt bridge sites.

Tab. 1: Atomic coordinates (in normalized lattice units) of atoms included in the cm asymmetric unit cell for the best bridge C1 model. Only the 3 topmost Pt surface layers are included. Pti-j indicates Pt atom j located in layer i.

Fig. 1 :

 1 Fig. 1: (color online) Pt(110)-c(4x4): Top and lateral views of the optimum surface slab ordering showing the geometry and distribution of the nanoholes (two layers) on the Pt(110)-surface. Note the shift of some

Fig. 2 :

 2 Fig. 2: (color online) Bottom view of C60 balls showing the C1 (a) and C2 (b) configurations bonded to the two topmost surface Pt-layers: the C60 molecule approximately places a 5 bond (pentagon almost parallel to the surface) or a 6:6 bond (hexagon:hexagon bond) on a bridge site of the second Pt layer, respectively. Black or gray atoms in C1 indicate Catoms with shorter or larger C-Pt distances than 2.4 Å, respectively. Topmost or second surface Pt layers are indicated with light (whiter) or (darker) sky blue colors, respectively.

Fig. 3 :

 3 Fig. 3: Top and lateral views of the C60/Pt(110)-c(4x4) superstructure showing the best and most plausible orientation of the C60 molecules according to the least squares refinement procedure. The structure corresponds with a C60 molecule with a pentagon ring parallel to the substrate surface shifted 0.5 Å long [1-10] direction and located on Pt bridge sites.

Fig. 4 :

 4 Fig. 4: and Crytal Truncational rods of the C60/Pt(110)-c(2x2) structure. The continuous lines correspond to the calculated data form the structure shown in Fig. 3.

Acknowledgements X. T. thanks the Spanish MICINN agency for partially funding this project through project CSD2007-0004. V.L. acknowledges the support of "generalitat de Catalunya" through the 2009 SGR 1292 project and of the MEI through the MAT2007-66309-C02-02 project.

Element