Hagit Attiya

Armando Castañeda
email: armando.castaneda@im.unam.mx

Danny Hendler
email: hendlerd@cs.bgu.ac.il

Matthieu Perrin
email: matthieu.perrin@univ-nantes.fr

Separating Lock-Freedom from Wait-Freedom

Keywords: Theory of computation → Shared memory algorithms, Concurrent algorithms, KEYWORDS concurrency, shared memory, multi-core algorithms, wait-freedom, lock-freedom, nonblocking

A long-standing open question has been whether lock-freedom and wait-freedom are fundamentally different progress conditions, namely, can the former be provided in situations where the latter cannot? This paper answers the question in the affirmative, by proving that there are objects with lock-free implementations, but without wait-free implementations-using objects of any finite power.

We precisely define an object called n-process long-lived approximate agreement (n-LLAA), in which two sets of processes associated with two sides, 0 or 1, need to decide on a sequence of increasingly closer outputs. We prove that 2-LLAA has a lock-free implementation using reads and writes only, while n-LLAA has a lock-free implementation using reads, writes and (n -1)-process consensus objects. In contrast, we prove that there is no wait-free implementation of the n-LLAA object using reads, writes and specific (n -1)-process consensus objects, called (n -1)-window registers.

INTRODUCTION

Asynchronous shared-memory algorithms capture the behavior of concurrent systems, where failure-prone processes, each running at its own speed, communicate by applying primitives to shared base objects. Such algorithms are often used to implement higher-level objects, supporting ongoing invocations. These implementations withstand adverse system behavior, due to scheduling anomalies and failures.

Two main progress conditions have been studied for asynchronous shared-memory implementations [START_REF] Herlihy | Wait-free synchronization[END_REF]. The first, wait-freedom, ensures individual progress to each process, i.e., its operations complete as long as it takes an infinite number of steps. The second, lockfreedom, requires only global progress, namely, if a process takes an infinite number of steps then some (possibly other) processes complete their operations. 1 Clearly, every wait-free implementation is also lock-free.

Many wait-free implementations, starting with the universal construction [START_REF] Herlihy | Wait-free synchronization[END_REF] and recently [START_REF] Kogan | A methodology for creating fast wait-free data structures[END_REF], are derived by first presenting a fairly simple lock-free implementation, which is then made waitfree through sophisticated techniques. It is therefore natural to ask whether every object with a lock-free implementation also has a wait-free implementation. For one-shot (or bounded) objects, which each process accesses at most once (or a bounded number of times), the answer is trivially positive: Every lock-free algorithm is also wait-free, since once a process completes its operation (or a bounded number thereof), it takes no more steps, and the global progress condition implies that other processes are guaranteed to complete their operations.

The question, however, is challenging for long-lived objects, as there are objects with a lock-free implementation but without a known wait-free implementation using the same primitives (e.g., queues from test&set primitives [START_REF] Afek | Common2 extended to stacks and unbounded concurrency[END_REF]). The fundamental nature of wait-freedom and lock-freedom, and their use in numerous papers, makes this an important question.

The question was seemingly answered by Herlihy [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF], who argued that there is an object for which there is a lock-free implementation for two processes using only reads and writes, and there is no wait-free algorithm in the same setting. Besides several inaccuracies in the proofs (see below), the answer provided by [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF] is limited: it does not show a separation for more than two processes and it does not show a separation when primitives stronger than reads and writes can be used.

This paper paints a more complete picture of the separation between lock-freedom and wait-freedom. We precisely define an object called n-process long-lived approximate agreement (in short, n-LLAA), supporting a single operation called output(), which has no argument and returns a real number. Each of the n processes is assigned a side, either 0 or 1. Let S be a sequential execution with invocations of output(). The current position of side i in S is the output value of the last operation of a process in side i, or i if there are no operations of processes in side i. The sequential specification of n-LLAA includes every sequential execution in which the distance between the current positions of the two sides is at most 1 2 r , where r is the total number of operations in the execution.

We present a lock-free linearizable implementation of 2-LLAA, a restriction of n-LLAA for two processes, using reads and writes only (Section 3). This implementation is extended to a lock-free linearizable implementation of n-LLAA, using reads, writes and (n -1)-process consensus objects (Section 4). 2A specific consensus object that can be used is a window register. These registers support read and write primitives: the write primitive is standard, but the read primitive, parameterized with an integer k > 1, returns a k-tuple composed of the last k values written, in the order in which they were written. A k-window register supports read primitives with parameter ≤ k; note that a 1-window register is a standard register supporting read and write primitives. This object was initially defined in [START_REF] Perrin | Causal consistency: beyond memory[END_REF] to illustrate causal consistency. A similar object was defined concurrently in the context of space lower bounds for concurrent objects [START_REF] Ellen | A complexity-based hierarchy for multiprocessor synchronization[END_REF]. It is proved in [START_REF] Achour Mostéfaoui | A simple object that spans the whole consensus hierarchy[END_REF] that a k-window register can solve consensus among exactly k processes, i.e., its consensus number is k.

Our main impossibility result shows that there is no wait-free implementation of the n-LLAA object, that uses only k-window registers, for k < n (Section 5). Note that this includes read/write registers. Related Work: The 2-LLAA object is a stronger version of the iterated approximate agreement object studied in [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF], and its implementation is the same, except for a few small details. However, as explained in Section 3.2, 2-LLAA requires a more elaborate correctness proof, which determines the linearization points dynamically. Differently from 2-LLAA, the convergence requirement of the iterated approximate agreement object is that the r -th output operation of p i is at distance at most 1/2 r from the the current position of the other process. Furthermore, the impossibility result for wait-free implementations in [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF] relies on an unstated assumption (in the second paragraph of the proof of Lemma 14) that an infinite number of steps by one process must eventually fix the decision of the other process. Although this behavior, often referred to as helping, is a common way to turn lock-free implementations into wait-free ones, it is not a priori known to be a necessary condition for waitfreedom. The notion of helping was recently formalized [START_REF] Attiya | Nontrivial and universal helping for wait-free queues and stacks[END_REF][START_REF] Censor-Hillel | Help! In PODC[END_REF] and was shown to be a nontrivial property, allowing to prove nontrivial results not known to hold otherwise. Additionally, the final step of the impossibility proof in [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF] (in the proof of Theorem 15) needs a stronger convergence requirement than the one required by the iterated approximate agreement object. Our impossibility proof addresses these challenges and extends to the general case of systems with (n -1)-consensus objects.

Aspnes and Herlihy [START_REF] Aspnes | Wait-free data structures in the asynchronous pram model[END_REF] defined a class of objects for which there are wait-free implementations from read/write objects, as well as lock-free ones. Another class of objects, called Common2, includes the set of objects that have a wait-free implementation from objects with consensus number 2, e.g., test&set [START_REF] Afek | Common2 extended to stacks and unbounded concurrency[END_REF][START_REF] Afek | A completeness theorem for a class of synchronization objects[END_REF].

Strong linearizability [START_REF] Golab | Linearizable implementations do not suffice for randomized distributed computation[END_REF] was introduced as a way to circumvent some anomalies when used with randomized implementations. It was shown that there are deterministic lock-free and strongly linearizable implementations of snapshot, max-register or counter from multi-writer multi-reader registers, while there are no such wait-free implementations [START_REF] Denysyuk | Wait-freedom is harder than lock-freedom under strong linearizability[END_REF].

MODEL OF COMPUTATION

We consider a standard shared memory system with n asynchronous processes, p 0 , . . . , p n-1 , which may crash at any time during an execution. Processes communicate with each other by applying atomic primitives to base objects. The base objects we consider are window registers of size k ∈ {1, . . . , n -1} (in short, k-window registers) to which read and write primitives are applied. The write primitive has a single parameter, the value to be written. The read primitive returns a k-tuple composed of the last k values written, in the order in which they were written. Missing values are replaced by a default value ⊥. Each window register can be read and written to by all processes, i.e., they are multi-reader multi-writer. Note that a 1-window register is the standard register, supporting ordinary read and write operations.

A (high-level) concurrent object, or data type, is defined by a state machine consisting of a set of states, a set of operations, and a set of transitions between states. Such a specification is known as sequential. An implementation of a data type T is a distributed algorithm A consisting of a local state machine A p , for each process p. For any process p, A p specifies which primitives p applies in order to return a response when it invokes an operation of T . Each of these primitive invocations is a step. For the rest of this section, fix an implementation A of some data type T .

A configuration C of the system contains the states of all registers and processes. In an initial configuration, registers and processes are in their initial states. Given a configuration C and process p, p(C) is the configuration after p takes its next step in C. Moreover, p 0 (C) = C and for every n ∈ N, p n+1 (C) = p(p n (C)).

An execution of A is a possibly infinite sequence of steps (namely, invocations of primitives) and invocations and responses of highlevel operations in A, with the following properties: (1) Each process first invokes a high-level operation, and only when it has a corresponding response, it can invoke another high-level operation, i.e., executions are well-formed. (2) A process takes steps only between an invocation and a response. (3) For any invocation of process p, the steps of p between that invocation and the following response of p, if there is one, correspond to steps of p that are specified by A.

An operation in an execution is complete if both its invocation and response appear in the execution. An operation is pending if only its invocation appears in the execution. An implementation is wait-free if every process completes each of its operations in a finite number of its steps. Formally, if a process executes infinitely many steps in an execution, all its operations are complete. An implementation is lock-free if whenever processes execute steps, at least one of the operations terminates. Formally, in every infinite execution, infinitely many operations are complete. Thus, a waitfree implementation is lock-free but not necessarily vice versa.

An operation OP precedes another operation OP ′ if OP completes before OP ′ starts. OP and OP ′ are concurrent (or overlapping) if neither OP precedes OP ′ nor OP ′ precedes OP. OP does not precede OP ′ if either OP is concurrent with OP ′ or OP ′ precedes OP.

Linearizability [START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF] is the standard notion used to identify a correct implementation. Roughly speaking, an implementation is linearizable if each operation appears to take effect atomically at some time between its invocation and response, hence operations' real-time order is maintained. Formally, let A be an implementation of a data type T . An execution α of A is linearizable if there is a sequential execution S of T (i.e., a sequence of matching invocationresponse pairs, starting with an invocation) such that: (1) S contains every complete operation of α and some pending operations. Hence, the output value in the matching responses of an invocation in S and α are the same. (2) For every pair of operations op and op ′ in α, if the response of op precedes the invocation of op ′ in α, then op appears before op ′ in S; namely, S respects the real-time order in α.

A is linearizable if each of its executions is linearizable.

READ/WRITE LOCK-FREE 2-LLAA

This section presents a read/write lock-free 2-LLAA implementation, as well as a sketch of its correctness proofs. Some proofs are deferred to the appendix. Definition 1. Let S be a sequential execution with invocations of two processes p 0 and p 1 to an operation output(), each returning a real number. The current position of p i in S is the output value of the last operation of p i , or i if there are no operations of p i . We say that S satisfies the convergence requirement if the distance between the current positions of the processes is at most 1/2 r , where r is the total number of operations in the execution. The sequential specification of the 2-LLAA object contains every sequential execution of output() operations by p 0 and p 1 such that each of its prefixes satisfies the convergence requirement.

The algorithm in Figure 1 is a lock-free implementation of 2-LLAA using read/write primitives. Each process p i locally stores its current position and round (number of complete and pending operations of p i , so far) in its local variable me, and stores the position and round of the other process, denoted p j , in you. The initial position and round of p i are i and 0. Processes communicate through the shared array M by writing and reading positions and rounds. Additionally, p i uses two (closed) intervals prev and ranдe: prev stores the interval committed in p i 's previous operation, which indicates where any future position of p i might be, and ranдe stores the current interval the position of p j should belong to in order for p i to decide.

When executing output(), p i first increments its round counter and writes the new value in M (lines 01 and 02) and then iterates the while loop (lines 03 to 15). Each iteration tries to get closer to the position of p j in M, until the condition in line 08 is satisfied. There are two (disjoint) cases that can make p i 's current operation decided. In the first case, called closeness rule, the position of p j read by p i is in the interval ranдe computed in line 07, hence the distance between the positions is at most 1/2 r , where r is the total number of operations p i is aware of. This ensures that the distance between the positions of the processes obeys the convergence requirement of 2-LLAA. In the second case, called invalid position rule, the position of p j is out of the previously-committed range prev of p i . Observe that this can happen because of asynchrony: p i might have completed several operations getting closer to a position of p j in M that is different from the position p j is about to write. The rationale behind the invalid position rule is that as p j was slow and its position is not in prev of p i , it would have to "catch up" and decide by the closeness rule in its current operation. As shown below (Lemma 1), whenever p i decides by the invalid position rule, the current operation of p j is pending and p j decides by the closeness rule in every extension in which its operation is complete.

Correctness Proof

In the analysis of the algorithm, for simplicity and without loss of generality, the invocation of an operation is identified with its first shared-memory write operation outside the while loop of the output function (line 02), that is, it is executed atomically together with the local operations of line 01. The response of a decided operation is identified with its last shared-memory read step inside the loop (line 05). We also assume that the local computation inside the while loop (lines 05-15) is executed atomically together with the shared-memory read step in line 05.

For an execution α, we use the following notation and terminology. The k-th operation of a process p i in α is denoted P k i (α), if there is such an operation. P 0 i (α) denotes a fictitious operation whose output is the initial position of p i . An operation P k i (α) of p i is decided if it takes its response (read) step in α. In this case, v k i (α) denotes the value of variable v at the end of P k i (α). We let rad(prev k i (α)) denote the radius of the interval prev k i (α) with center me k i .pos(α). A decided operation P k i (α) decides by the closeness

rule on P m j (α) (with j = 1 -i) if you k i .pos(α) ∈ ranдe k i (α) and you k i .round(α) = m. P k i (α)
decides by the invalid position rule on P m j (α) if you k i .pos(α) prev k i (α) and you k i .round(α) = m. We omit α from the above definitions when it can be understood from the context.

To see that Algorithm 1 is lock-free, we note that two operations P k i and P m j cannot both take an infinite number of steps without completing, since eventually they agree on rounds = k + m and their positions get sufficiently close to each other. The formal proof is omitted for lack of space Algorithm Linearize (Figure 2) specifies how we linearize a quiescent execution (i.e. an execution without pending operations) α. Lemma 1 stated below (whose proof is in the appendix) forms the basis for showing that Algorithm Linearize produces correct linearizations. Linearize considers the operations of α in the order they decide. Let P k i and P m j be the operations considered at the beginning of the ℓ-th iteration of the while loop of Linearize. If P m j is decided, then P m j is already in seq ℓ , and, as we shall see, P k i decides by the closeness rule. This implies that P k i and P m j satisfy the convergence requirement. If P m j is not decided (hence pending), then P m j can be safely placed before or after P k i because Lemma 1 implies that P m j will decide by the closeness rule. Finally, as the proof of Lemma 3 argues, if none of P k i and P m j are in seq ℓ , then P k i and P m j start from a quiescent state of the algorithm (operations P 2 and Q 1 in Figure 3 are an example of this situation) and their order is decided considering the outputs of the previous operations. Lemma 1. Let α be a finite execution whose last step is a read (in line 05) of an operation P k i of p i that makes that operation decided (by either the closeness or the invalid position rules) on some undecided operation P m j of p j , with j = 1 -i. Let α β be any extension of α in which P m j is decided. Then, P m j decides by the closeness rule in α β and dist(me k i .pos, me m j .pos) ≤ 1/2 m+k .

It follows directly from Algorithm Linearize that the latest point in which an operation is linearized is when it decides (by reading in line 05 of Figure 1). Moreover, once an operation is linearized, the operation (by the other process) it decides on is also linearized (if it was not linearized before). Lemma 2. Let α be a finite execution without pending operations. The sequential execution produced by Linearize(α) respects the realtime order in α.

Proof. Consider two operations P k i and P m j in α, k, m > 0. Suppose that P k i precedes P m j in α. The latest point at which Algorithm Linearize linearizes P k i is when β l +1 in line 03 of Algorithm Linearize ends in the read step which makes P k i decide in α. None of the steps of P m j appear in β l +1 , hence P k i does not decide on P m j and consequently P m j is not linearized in lines 10, 15 or 17 of Algorithm Linearize (which are the only places operations are linearized). Furthermore, no prior operation by p i could have decided on P m j in β l +1 , hence it was not linearized before. □ 2: A sequential algorithm to linearize an execution α without pending operations. Lemma 3, is the key technical lemma in the algorithm's correctness proof, establishing that Algorithm Linearize outputs correct linearizations. Lemma 3. Let α be any finite execution without pending operations. Then, Lin(α) is a sequential execution of the 2-LLAA object.

P 1 P 2 P 3 Q 1 Q 2 Q 3 P Q Lin P 1 Q 1 P 2 P 2 Q 1 or P 3 Q 2 Q 3
Proof Sketch. We consider a linearization Lin(α) of an execution α which, as we assume towards a contradiction, is not a sequential execution of 2-LLAA, and consider the first operation P k i that violates convergence. Let P m-1 j be the latest preceding operation of p j in Lin(α). Then, dist(me k i .pos, me m-1 j .pos) > 1/2 m+k -1 .

Since Lin(α) respects the real-time order in α (Lemma 2), P k i does not precede P m-1 j in α.

If P m-1 j and P k i are concurrent in α, let β be the shortest prefix of α in which the first of them, say P k i , is decided. Hence P m-1 j is pending and P k i decides on P m-1 j

. By Lemma 1,

dist(me k i .pos, me m-1 j .pos) ≤ 1/2 m+k -1 ,
and the convergence requirement holds.

We therefore know that P m-1 j precedes P k i in α. It can be shown that at the end of the previous (possibly fictitious) operation

P k-1 i of p i , rad(prev k -1 i ) ≥ 1/2 m+k -2 . Moreover, when P k i starts, prev i = prev k-1 i , me i .pos = me k -1 i .pos
dist(me k i .pos, me m j .pos) ≤ 1/2 m+k (2)
To prove (1), note that P m j cannot precede P k-1 i because it is concurrent with P k i . Also, it is easy to show that P k -1 i precedes P m j in α. Thus, P m-1 j precedes P k i and P k -1 i precedes P m j , and hence both P k-1 i and P m-1 j are complete when the first among P k i and P m j starts in α. Without loss of generality, suppose that P k i decides before P m j , then, since they overlap, P k i decides on P m j . Since P m-1 j precedes P k i and P k -1 i precedes P m j , in the while iteration of Algorithm Linearize that linearizes P k i , the conditions of lines 06 and 12 are false, namely, P k i and P m j were not linearized yet, and they are linearized in lines 14-18. It can be shown that P m j is not linearized before P k i , and the condition of line 14 holds, implying [START_REF] Achour Mostéfaoui | A simple object that spans the whole consensus hierarchy[END_REF].

Lemma 1 implies (2), since P k i are P m j are concurrent, similarly to the case when P k i and P m-1 j are concurrent, handled before. .pos) ≤ 1/2 m+k-2 , and hence |I| ≤ 1/2 m+k -2 . The interesting case is when |I| = 1/2 m+k -2 . Lemma 12 (in the appendix) implies that the first to decide among P k i and P m j must decide a position (in I) that is an integer multiple of 1/2 m+k . There are only five integer multiples of 1/2 m+k in I. 4). □

P k-1 i P m-1 j P k i P m j c 0 c 1 c 2 c 3 c 4 1/2 m+k-2 1/2 m+k-1
Consider any finite execution α of the algorithm from Figure 1. Let α β be an extension of α in which all operations in α are complete (and no new operation is started). This extension exists since the algorithm is lock-free. By Lemma 2, the sequential execution seq(α β) produced by Lin(α β) respects the real-time order of α β; by Lemma 3, it is a sequential execution of the 2-LLAA object. Thus, seq(α β) is a linearization of α β, and of α as well, implying the main theorem of this section: Theorem 4. Algorithm 1 is a lock-free linearizable implementation of the 2-LLAA object, using reads and writes.

A Simpler Linearization Proof?

This section discussed whether a simpler linearization argument exits. The linearization proof in the previous subsection is nontrivial, partly because Algorithm Linearize may place operations that are pending in α before operations that are complete. Furthermore, as we described previously, to linearize a non-quiescent execution α, we first complete all pending operations in α and then apply Algorithm Linearize to the resulting quiescent execution. Consequently, it is possible that the linearization S ′ we obtain for an extension α ′ of α is not an extension of the linearization S we obtain for α, implying that our implementation is not necessarily strongly linearizable [START_REF] Golab | Linearizable implementations do not suffice for randomized distributed computation[END_REF]. 4 In contrast, the linearizability order used in the correctness proof of the lock-free algorithm [10, Figure 5, Section 4] is simple and shows that the algorithm is strongly linearizable. Below we argue that this simple approach does not work for our stronger 2-LLAA object. 3 It is useful to consider the initial configuration, where m = k = 1 and me k -1 i .pos = 0, me m-1 j .pos = 1. 4 An algorithm is strongly linearizable if there is a function f from executions of the algorithm to sequential executions such that (1) for every execution α , f (α ) is a linearization of α and (2) for every execution α β , f (α ) is a prefix of f (α β ).

The linearization order used in [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF] (right above Lemma 11) is the following. For every operation OP in an execution, let rounds(OP) be the first value the operation sets to the local variable rounds (that variable is called i in [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF]). Then, if rounds(OP) < rounds(OP ′ ), OP is linearized before OP ′ , and if rounds(OP) = rounds(OP ′ ), OP and OP ′ can be linearized in any order.

Consider the following execution of the algorithm in Figure 1: (1) p 0 starts an invocation to output(), completes one iteration of the loop (note that it does not decide as 1/2 r ounds = 1/2 1 ) and stops before writing its new preference at the first step of the second iteration of the loop. Note that p 0 is about to write 1/2 and the position of p 0 in M is still 0. (2) p 1 executes, until completion, two consecutive invocations to output() (p 0 takes no steps while p 1 completes the two invocations). Observe that p 1 obtains 1/4 and 1/8 from the two invocations, respectively. (3) p 0 runs solo until it completes its pending output() invocation. Note that p 0 obtains 1/4 from the invocation.

It is easy to see that, for the execution α defined above, rounds(P 1 0 ) = 1, rounds(P 1 1 ) = 2 and rounds(P 2 1 ) = 3, and thus, using the linearization order defined in [START_REF] Herlihy | Impossibility results for asynchronous pram[END_REF], α would be linearized as follows: ⟨P 1 0 : 1/4⟩⟨P 1 1 : 1/4⟩⟨P 2 1 : 1/8⟩. However, this linearization is incorrect because lin(α) is not a sequential execution of 2-LLAA: the prefix ⟨P 1 0 : 1/4⟩ of the sequential execution is invalid, because the distance between the current position of p 0 and the current (initial) position of p 1 , which are respectively 1/4 and 1, is larger than 1/2 1 . Consequently, lin(α) is not a valid sequential execution of 2-LLAA either.

Finally, it can be verified that Algorithm Linearize produces the linearization ⟨P 1 1 : 1/4⟩⟨P 1 0 : 1/4⟩⟨P 2 1 : 1/8⟩ from α, which is a sequential execution of 2-LLAA.

LOCK-FREE n-LLAA, USING (n -1)-CONSENSUS OBJECTS

We formally define the n-LLAA object and explain how it can be implemented in a lock-free manner using (n -1)-process consensus objects; full correctness proofs are omitted for lack of space.

Definition 2. Each of the n processes belongs to a side, either 0 or 1. The n-LLAA object supports a single operation called output(). Let S be a sequential execution with invocations of output(), each returning a real number. The current position of side i in S is the output value of the last operation of a process in side i, or i if there are no operations of processes in side i. We say that S satisfies the convergence requirement if the distance between the current positions of the two sides is at most 1 2 r , where r is the total number of operations in the execution. The sequential specification of the n-LLAA object contains every sequential execution of output() operations by the n processes such that each of its prefixes satisfies the convergence requirement.

The lock-free implementation of n-LLAA is based on the lockfree 2-LLAA algorithm. Consider first the case in which there is at least one process in each side. Then, using (n -1)-process consensus objects, the ≤ n-1 processes in side i simulate operations of process p i in Algorithm 1; each time an operation terminates, the processes decide who takes this output value, also using consensus objects. When there are n processes in the same side, the processes can safely decide on the initial value of the other side.

Figure 5 shows how processes in the same side i simulate process p i of Algorithm 1. Lines 05-31 simulate a single operation output() of p i ; each time this loop starts, a new operation of p i is simulated. Lines 08 and 11 correspond to the write operations of Algorithm 1 and Lines 12-16 simulate the read operation of Algorithm 1, with the help of the consensus objects in READS. Each process first reads the pair (pos, round) of the processes in the other side and considers the most current one (from its point of view), with the help of the timestamps in the local variables me. This is its proposal to the consensus which decides the next read value of the simulated process p i . Once the output value of the current simulated operation of p i has been computed (the condition in Line 19 is true), the processes in the same side i compete for that output value in Line 22, with the help of the consensus objects in OPS. The winning process outputs that value for its current operation, while the others start a new simulated operation of p i . The goal of Lines 01-04 is to handle the case in which all processes belong to the same side: when a process discovers that all processes are in its side, it knows that the other side is not moving (it has not moved since the beginning of the execution) hence it can safely decide the initial position of the other side.

The way processes advertise their side in Line 01, and then check the others' side in Line 03, ensures that in every execution, at most n -1 processes invoke the same consensus object (in Lines 16 and 22). The following property directly follows from the agreement property of consensus. Lemma 5. Consider an execution of Algorithm 5. Then, for every pair of processes p ℓ and p j in the same side, if both p ℓ and p j assign the kth value to a local variable v, which is either me, you, prev or ranдe, then v k j = v k ℓ .

Using this lemma, we can now precisely define the notion of a simulated operation. Let α be a (finite or infinite) execution of Algorithm 5. For every side i and integer k ≥ 1, the k-th simulated operation of side i, denoted sOP k i , is the subsequence of α containing all steps corresponding to steps in Lines 08, 11, 12, 16 or 22 of any process such that when it executes the step, its me.round local variable is equal to k. The following lemma relates the executions of Algorithms 1 and 5, where the two processes in Algorithm 1 are denoted q 0 and q 1 . Lemma 6. For every finite or infinite execution α of Algorithm 5, there is an execution α * of Algorithm 1 such that:

(1) There is a function f from the set of operations of α onto the set of operations in α * ; moreover, for each operation OP in side i, f (OP) is an operation of q i .

(2) An operation OP is pending if and only if f (OP) is pending; moreover, OP has infinitely many steps if and only if f (OP) has infinitely many steps too.

(3) The outputs of a completed operation OP and its associated completed operation f (OP) are the same.

(4) If OP precedes OP ′ in α then f (OP) precedes f (OP ′ ) in α * .

Proof Sketch. By Lemma 5, every pair of processes performing the steps of the same simulated operation sOP, write the same sequence of values (possibly at distinct times, due to asynchrony). Thus, for each simulated operation sOP in α, we can map an operation д(sOP) in an execution of α * of Algorithm 1 by removing redundant steps from α (essentially, we keep the first ℓth simulated step of sOP, for every ℓ). For any operation OP of process p i in α, let h(OP) be the simulated operation in α, the last step of OP by p i belongs to. Then, if OP is completed, h(OP) is the simulated operation p i is simulating when it wins in the consensus at Line 22. Finally, we let f (OP) = д(h(OP)) □ Theorem 7. Algorithm 5 is a lock-free linearizable implementation of the n-LLAA object, using reads, writes and (n -1)-process consensus objects.

Proof. Lemma 6 implies that if there is an infinite execution α of Algorithm 5 in which only finitely many operations are completed, then there is an infinite execution α * of Algorithm 1 in which only finitely many operations are completed, in contradiction to the lockfreedom of Algorithm 1. This implies that Algorithm 5 is lock-free as well.

Next, consider any finite execution α and let α β be an extension in which all operations in α are completed. Let λ be an execution of Algorithm 1 associated with α β, as in Lemma 6. The output of a completed operation OP is equal to the output of its associated completed operation f (OP), and if OP precedes OP ′ in α β then, by Lemma 6, f (OP) precedes f (OP ′ ) in λ. Thus, by replacing each OP with f (OP), we can obtain a linearization lin(α β) of α β from any linearization lin(λ) of λ, since the convergence requirement in both 2-LLAA and n-LLAA is a function of the number of all previous operations. Thus, Algorithm 5 is linearizable. □

IMPOSSIBILITY OF WAIT-FREE n-LLAA USING (n -1)-WINDOW REGISTERS

An execution β is an extension of a finite execution α if α is a prefix of β. A configuration C is reachable if there is a finite execution that ends with all processes and variables in the same states as in C.

A configuration C ′ is reachable from a configuration C if there is a finite execution α that ends with C ′ and a prefix of the execution α ends with C. Two configurations C and C ′ are indistinguishable to process p, denoted C p ∼ C ′ , if the state of every shared variable and the state of p are the same in C and C ′ .

Fix an implementation A of the n-LLAA object. Below, we consider only executions of A in which process p 0 is on side 0, performing a single output() operation, and all other processes are on side 1.

Let α be a finite execution of A; α is v-potent if there is an extension α ′ of α in which the operation of p 0 is complete and returns v; α is v-univalent (or just univalent when v is irrelevant) if α is v-potent and for all w v, α is not w-potent; α is bivalent if it is both v-potent and w-potent, for two values v w. Definition 3. An execution α is ambivalent for process q p 0 (or simply ambivalent when q is immaterial), if α is v-univalent and for some w v, there is a w-univalent execution α ′ that is indistinguishable from α to process q. If α ends with a configuration C, we say that C is ambivalent for process q. Definition 4. An execution α, ending with configuration C, has a critical q-extension (or simply critical extension when q is immaterial) for a process q p 0 , if there is a process q ′ {p 0 , q} such that, for all ℓ ≥ 0, p 0 (q ℓ (C)) is v-univalent and p 0 (q ′ (q ℓ (C))) is w-univalent with v w. Definition 5. An execution α, ending with configuration C, is (v, q, v ′ )-critical (or simply critical if v, q and v ′ are immaterial), if p 0 (C) is v-univalent, there is a process q p 0 such that p 0 (q(C)) is v ′ -univalent, for v ′ v, and for all finite extensions α β of α ending in configuration C ′ , p 0 (C ′ ) is univalent.

Lemma 8. If α is a (v, p 1 , v ′ )-critical execution of A ending in configuration C,
then either some extension of α is ambivalent or some extension of α has a critical extension.

Proof. The proof considers the next steps that p 0 and p 1 are about to take in C. If both p 0 and p 1 access different window registers, or p 1 's step is a read, then p 1 (p 0 (C)) and p 0 (p 1 (C)) are indistinguishable to p 0 . Hence, a solo execution of p 0 after both configurations returns the same value, contradicting the fact that α is

(v, p 1 , v ′ )-critical, that is, p 1 (p 0 (C)) is v-univalent and p 0 (p 1 (C)) is v ′ -univalent.
If p 0 's next step is a read of a window register, then p 1 (p 0 (C)) and p 0 (p 1 (C)) are indistinguishable to all processes other than p 0 , p 1 (p 0 (C)) is v-valent and p 0 (p 1 (C)) is v ′ -valent, so p 1 (p 0 (C)) and p 0 (p 1 (C)) are both ambivalent for all processes other than p 0 .

The remaining case is when both steps are writes to the same window register R. If n = 2, then R is an ordinary register, so p 0 (p 1 (C)) and p 0 (C) are indistinguishable to p 0 . Since α, ending

with C, is (v, p 1 , v ′ )-critical, p 0 (C) is v-valent and p 0 (p 1 (C)) is v ′ - valent, which is a contradiction.
For n > 2, we can prove the following claim: Claim 9. Let α β be a finite extension of α ending in configuration C ′ , such that p 0 and p 1 do not take steps in β and no process writes to R in β. Then p 0 (C ′ ) is v-univalent and p 0 (p

1 (C ′ )) is v ′ -univalent.
Proof. The proof is by induction on the length of β, with a trivial base case when β is empty. Suppose the lemma holds for when the length of β is ℓ, and let us consider an extension α βγ of α, where γ is a single step of some process q {p 0 , p 1 }. Let C ′ be the configuration at the end of α β, and C ′′ be the configuration at the end of α βγ . By the induction hypothesis, p 0 (C ′ ) is v-univalent and p 0 (q(C ′ )) is v ′ -univalent. Note that no process writes to R in βγ .

If q applies a primitive to a window register different than R, then

p 0 (C ′′ ) = p 0 (q(C ′ )) = q(p 0 (C ′ )) is v-univalent and p 0 (p 1 (C ′′ )) = p 0 (p 1 (q(C ′ ))) = q(p 0 (p 1 (C ′ ))) is v ′ -univalent.
Otherwise, since no process writes to R in βγ , q reads R. Then p 0 (C ′′ ) = p 0 (q(C ′ )) and p 0 (C ′ ) are indistinguishable to p 0 . As p 0 (C ′ ) is v-univalent, p 0 (C ′′ ) is v-potent, since the solo executions by p 0 starting from C ′′ and from C ′ are the same, hence both must return v. Moreover, since α is critical, p 0 (C ′′ ) is univalent. Therefore, p 0 (C ′′ ) is v-univalent. Similarly, p 0 (p 1 (C ′′ )) = p 0 (p 1 (q(C ′ ))) and p 0 (p 1 (C ′ )) are indistinguishable to p 0 and p 0 (p 1 (C ′ )) is v ′ -univalent by the induction hypothesis. Hence, p 0 (p 1 (C ′′ )) is v ′ -univalent. □ Assume first that we can let each process p 2 , . . . , p n-1 , in turn, take steps until it is about to write to R, reaching a configuration D in which the next step of every process is a write to R. By Claim 9, p 0 (D) is v-valent and p 0 (p 1 (D)) is v ′ -valent. However, since R is an (n -1)-window register, p n-1 (...(p 2 (p 0 (D)))...) and p n-1 (...(p 2 (p 0 (p 1 (D))))...) are indistinguishable to all processes except p 1 , contradicting the fact that p n-1 (...(p 2 (p 0 (D)))...) is v-valent, whereas p n-1 (...(p 2 (p 0 (p 1 (D))))...) is v ′ -valent.

Otherwise, for some process q p 1 , there is an infinite extension α βγ of α such that q runs solo in γ and no process writes to R in βγ . Let C ′ be the configuration at the end of α β. By Claim 9, for all ℓ ≥ 0, p 0 (q ℓ (C ′ )) is v-univalent and p 0 (p 1 (q ℓ (C ′ ))) is v ′ -univalent, i.e., γ is a critical q-extension of α β. □

We next use a standard valency argument to prove that if A is wait-free, then it has a critical execution. Lemma 10. If A is a wait-free linearizable implementation of the n-LLAA object, then it has a critical execution.

Proof. Since A is linearizable, in a solo execution by p 0 starting from C 0 and completing one output operation, the current position of side 0 must be at least 1 2 . On the other hand, in the execution from C 0 in which p 1 first executes solo two complete output operations and then p 0 runs solo and executes its output operation to completion, the current position of side 0 can be at most 3 8 . It follows that the empty execution (from C 0 ) is bivalent.

Starting with the empty execution as α, we repeatedly extend α to a bivalent execution αα ′′ , such that p 0 executes a step in α ′′ (α ′′ may include steps by other processes). Since A is waitfree, eventually we reach a bivalent execution αα ′ ending with configuration C ′ such that for any extension αα ′ β of αα ′ ending with configuration C ′′ , p 0 (C ′′ ) is univalent. In particular, this holds for the empty β.

It follows that p 0 (C ′ ) is univalent, so it is v-valent for some v. Since αα ′ is bivalent, it has an extension αα ′ β 1 , ending with a configuration C 1 , such that p 0 (C 1 ) is v ′ -valent, for some v ′ v. Let β 2 be the longest prefix of β 1 such that αα ′ β 2 ends with a configuration C 2 for which p 0 (C 2 ) is v-valent. Let q be the process that takes the next step in αα ′ β 1 after the execution of αα ′ β 2 . From our construction, p 0 (C 2 ) is v-valent, p 0 (q(C 2 )) is v ′ -valent for v ′ v, and for any finite extension αα ′ β 3 of αα ′ β 2 , ending with a configuration C 3 , p 0 (C 3 ) is univalent. It follows from Definition 5 that αα ′ β 2 is (v, q, v ′ )-critical. □ Theorem 11. There is no wait-free linearizable implementation of the n-LLAA object, which uses only (n -1)-window registers. (Note that this includes read and write registers.) Proof. Assume, by way of contradiction, that A is a wait-free linearizable implementation of the n-LLAA object. By Lemma 10, A has a critical execution α. By Lemma 8, we have two cases:

Case 1: Some extension α ′ of α, ending with a configuration C ′ , is ambivalent for a process q p 0 . By Definition 3, α ′ is v-valent for some v, and there is a w v and an execution α w , ending with a configuration C w , such that α w is w-univalent and configurations C ′ and C w are indistinguishable to q.

Pick an integer k such that 1 2 k < |v -w |. Let α ′ β q v be an extension of α ′ such that, in β q v , q runs solo and executes to completion k + 3 output operations. Let x be the value returned by the last operation of q. Let α ′ β q v β p 0 v be an extension of α ′ β q v such that, in β p 0 v , p 0 runs solo until it completes its output operation. Since α ′ is v-univalent, p 0 's operation returns v.

Consider a linearization of α ′ β q v β p 0 v . It contains at least k + 3 operations of processes in side 1, including all the ones by q, and one operation by p 0 . Suppose first that the last operation of q is linearized after the operation of p 0 . By Definition

2, |x -v | ≤ 1 2 k +4 < 1 2 k +1 .
Suppose now that the last operation of q is linearized before the operation of p 0 . Let k ′ denote the number of operations in side 1 linearized between the last operation of q and the operation of p 0 and let y be the value returned by the operation linearized right before the operation of p 0 . By Definition 2,

|x -v | ≤ |x -0| + |0 -y| + |y -v | ≤ 2 -(k+3) + 2 -(k+3+k ′ ) + 2 -(k +3+k ′ +1) < 2 -(k +1) .
Let α w β q w be an extension of α w such that, in β q w , q runs solo after α w and executes to completion k + 3 output operations. Since α ′ and α w are indistinguishable to q, β q w = β q v and so q's (k + 3)'th output operation in β q w also returns x. Now consider the extension α w β q w β p 0 w such that, in β p 0 w , p 0 runs solo until it completes its output operation. Since α w is w-univalent, p 0 's output operation returns w. Consider a linearization of α w β q w β p 0 w . Using a similar reasoning as above, we can show that |w -x | < 2 -(k+1) . Therefore,

|w -v | ≤ |w -x | + |x -v | < 2 2 k+1 = 1 2 k
, which is a contradiction. Case 2: Some extension α ′ of α, ending with configuration C ′ , has a critical q-extension. That is, there are two processes q q ′ , different from p 0 , and two values v w, such that for all ℓ ≥ 0, p 0 (q ℓ (C ′ )) is v-univalent and p 0 (q ′ (q ℓ (C ′ ))) is w-univalent.

The rest of the reasoning is similar to the previous case. Pick an integer k such that 1 2 k < |v -w |. Let α ′ β be an extension of α ′ ending in a configuration C ′′ , such that in β, q runs solo and executes k + 3 output operations to completion. Let x be the value returned by q's last operation.

Let α ′ βγ v and α ′ βγ w be two extensions of α ′ β such that, in γ v , p 0 runs solo until it completes its output operation, returning v, since p 0 (C ′′ ) is v-univalent; and in γ w , q ′ executes a single step and then p 0 runs solo until it completes its output operation, returning w, since p 0 (q ′ ((C ′′ ))) is w-univalent. Considering a linearization of α ′ βγ v and a linearization of α ′ βγ w , it can be shown that

|v -w | ≤ |v -x | + |w -x | < 2 2 k+1 = 1 2 k
, which is a contradiction. □

SUMMARY AND FUTURE WORK

This paper shows a computational separation between lockfreedom and wait-freedom, two dominant progress conditions of concurrent algorithms: while there is no wait-free implementation of the n-LLAA object from k-window registers, with k < n (whose consensus number is exactly k), there is a lock-free implementation of the n-LLAA object using read/write primitives and (n-1)-process consensus objects. To the best of our knowledge, this is the first time such a separation is shown. An interesting open question is whether there exists an n-LLAA implementation from x-process consensus objects for x < n -1, e.g., reads and writes, which would strengthen the separation. Noting that the n-LLAA object is non-deterministic, a second avenue for future research is to investigate whether or not the separation that we have shown holds also for deterministic long-lived objects. Finally, the n-LLAA specification assumes that the object "knows" the ID of the process invoking an operation on it. It would be interesting to see if the separation holds also for objects that do not assume this.

Proof. The proof of the lemma is based on the following two claims. Claim 14. For every finite execution α, I α i ⊆ prev α i .

Proof Sketch. By induction on the length of the prefixes of α, one can prove that me α i .pos ∈ prev α i and the distance between me α i .pos and any extreme of prev α i is at least 1/2 me α i .r ound +you α i .r ound . This invariant proves the lemma when M α [i].pos = me α i .pos, because then I α i ⊆ prev α i by definition. Otherwise, it must be that the last step of p i in α is a read step in line 05 that modifies its position me i .pos after executing lines 11-15, in which case we consider the execution α ′ obtained from α by removing the last step of p i and proceed as in the first case. □ Claim 15. For every finite execution αe, prev α e i ⊆ prev α i .

Proof. We prove the claim by induction on the length of the prefixes of αe. Note that the first step f in αe must be a write in line 02, which does not change the value of any local variable, and hence prev f i = prev ϵ i , where ϵ is the empty execution. This is the base of the induction. Suppose that prev

β f i ⊆ prev β i , for a prefix β f of α. We show that prev β f д i ⊆ prev β f
i , where д is the next step in αe. If д is not a step of p i or is a write step of p i (in line 02 or line 04), then such a step does not change the local variables of p i , and prev

β f д i = prev β f i .
Otherwise, д is a read step of p i (Line 05) and the local variables of p i might change when p i executes lines 07-15. The claim clearly holds if p i does not decide, since it executes line 07 and then lines 11-15; therefore, prev i is not modified, namely, prev

β f д i = prev β f i .
If p i decides, that is, the condition of line 08 is satisfied, then note that p i does not modify its position after the read step, hence me Now, since the last step in α is a read by p i in line 05 that makes P k i decided, p i executes lines 07-10 at the end of α, and so we have that me α i .pos is the center of prev α i , rad(prev α i ) = 1/2 m+k , me k i .pos = me α i .pos and prev k i = prev α i . We prove that me m j .pos ∈ prev α i , which implies that dist(me k i .pos, me m j .pos) ≤ 1/2 m+k . Let λ be the shortest prefix of α β in which P m j is decided (hence α is a prefix of λ). The last step of λ is a read step by p j in line 05 that makes P m j decided. Let x = you λ j .round. Thus, P m j decides (by the closeness rule) on the operation P x i , for x ≥ k. At the end of λ, after p j executes lines 07-10, we have that me m j .pos = me λ j .pos. By Lemma 13, I λ i ⊆ prev α i . Since P m j decides by the closeness rule, at the end of λ the condition of line 08 is satisfied when p j checks it, and thus dist(me λ j .pos, you λ j .pos) ≤ 1/2 m+x . Notice that you λ j .pos = M λ [i].pos, and hence me m j .pos ∈ I λ i ⊆ prev α i , which concludes the proof. □

Figure 1 :

 1 Figure 1: A lock-free 2-LLAA algorithm for processes p 0 and p 1 . Code of process p i .

Figure 3 :

 3 Figure 3: An example of the linearization produced by Algorithm Linearize.

Finally, consider the outputs me k- 1 i.pos and me m- 1 j.pos of P k- 1 iand P m- 1 j. Suppose that me k - 1 i.pos ≤ me m- 1 j 1 i.pos, me m- 1 j 1 i

 111111111 .pos (the other case is similar). Let I = [me k -.pos]. It can be shown that me k i .pos, me m i .pos ∈ I. By assumption, P k -

Figure 4 :

 4 Figure 4: An of the last case in the proof of Lemma 3: P k i decides before P m j and outputs c 1 , whose distance to the output of P m-1 j is strictly larger than 1/2 m+k -1 . By (2), the output of P m j is in the interval [c , c 2 ]. This is a contradiction since the distance between any point in [c 0 , c 2 ] and the output of P k -1 i is at most 1/2 m+k -1 , and thus dist (me k i .pos, me m-1 j.pos) >

  Shared variables: M [0, 1][0, . . . , n -1] ← each entry of M [j], j ∈ {0, 1}, initialized to ⟨pos = j, r ound = 0, tmst = 0⟩ S I DE[0, . . . , n -1] ← each entry initialized to ⊥ READS [0, 1][∞] ← bi-dimensional array with infinitely many (n -1)-process consensus objects O P S [0, 1][∞] ← bi-dimensional array with infinitely many (n -1)-

Figure 5 :

 5 Figure 5: A lock-free n-process LLAA object algorithm.

  = M β f [i].pos. By Claim 14, , following the execution of line 07, ranдe β f д = I that the containment may be proper, because youβ f д i .round ≥ you β f i .round) and prev β f д = ranдe β f д i(line 09), and thus prev β f д ⊆ prev β f . □ By Claim 14, I λ i ⊆ prev λ i . By repeatedly applying Claim 15, prev α e 1 e 2 •••e ℓ i ⊆ prev α e 1 e 2 •••e ℓ-1i ⊆ . . . ⊆ prev α . Therefore, I α e 1 e 2

  and M[j].pos = me m-1Now, if no operation of p j overlaps P k i , then if P k i decides by the invalid position rule, it does so in the very first iteration of the while loop, without any change to its position me i .pos, and thus me k i .pos = me k -1

					i	.pos. Hence, me m-1 j	.pos	prev k -1 i	and
	dist(me k -1 i	.pos, me m-1 j	.pos) > 1/2 m+k -2 , implying that either
	P k-1 i	or P m-1 j	(both preceding P k i in Lin(α)) do not satisfy the con-
	vergence requirement, which is a contradiction. And if P k i decides
	by the closeness rule, the code implies that
			dist(me k i .pos, me m-1 j	.pos) ≤ 1/2 m+k -1 ,
	and the convergence requirement holds.
	We are left with the case that operation P m j exists and overlaps
	with P k i (and P m-1 j dist(me k	precedes P k i ). We first prove that

j .pos. i .pos, me m-1 j .pos) ≤ dist(me m j .pos, me k -1 i .pos)

(1)

  process consensus objects

	Local variables:
		mySide ← initialized to 0 or 1
		ot her Side ← 1 -mySide
		me . ⟨pos, r ound, tmst ⟩ ← ⟨mySide, 0, 0⟩
	%% My side's position, round and timestamp
		you . ⟨pos, r ound, tmst ⟩ ← ⟨ot her Side, 0, 0⟩
	%% Other's position, round and timestmp
		pr ev, r anдe ← [mySide ± 1]
		count _r eads, count _ops ← 0
	Function output():
	(23)	if owner = I D then
	(24)	return me .pos
	(25)	decided ← true
	(26)	elseif me .pos < you .pos then
	(27)	me .pos ← me .pos + 1/2 r ound s
	(28)	me .tmst ← me .tmst + 1
	(29)	else
	(30)	me .pos ← me .pos -1/2 r ound s
	(31)	me .tmst ← me .tmst + 1
	(32)	endif
	(33) endwhile
	(34) endwhile
	endFunction

(01) S I DE[I D] ← mySide (02) s ← snapshot(S I DE) (03) if | {I D : s[I D] = mySide } | = n then (04)

return ot her Side (05) while true do (06) me .r ound ← me .r ound + 1 (07) me .tmst ← me .tmst + 1 (08) M [mySide][I D] ← me (09) decided ← false (10) while ¬decided do (11) M [mySide][I D] ← me (12) t ← snapshot(M [ot her Side]) (13) max ← max({tmst ′ : t [I D].tmst = tmst ′ }) (14) pr op ← any t [I D] such that t [I D].tmst = max (15) count _r eads ← count _r eads + 1 (16) you ← READS [mySide][count _r eads].decide(pr op) (17) r ounds ← me .r ound + you .r ound (18) r anдe ← [me .pos ± 1/2 r ound s ] (19) if you .pos ∈ r anдe ∨ you .pos pr ev then (20) pr ev ← r anдe (21) count _ops ← count _ops + 1 (22) owner ← O P S [mySide][count _ops].decide(I D)

  •••e ℓ Lemma 16. Let α be a finite execution. Then, for each i ∈ {0, 1} and j = 1 -i, either M α [i].pos ∈ prev α j or M α [j].pos ∈ prev α i . Proof Sketch. By strong induction on the length of the executions, we can show that either me α i .pos ∈ prev α j or me α j .pos ∈ prev α i . This proves the lemma because if neither M α [i].pos ∈ prev α j nor M α [j].pos ∈ prev α i , then we consider the execution α ′ obtained from α by removing, if necessary, the last read step of each process so that M α ′ [i].pos = me α ′ i .pos and M α ′ [j].pos = me α ′ j .pos, hence reaching a contradiction. □ Proof of Lemma 1. First, we show that if M α [i].pos ∈ prev α j , then P m j must decide by the closeness rule in α β. Note that me α i .pos = M α [i].pos. Assume otherwise towards a contradiction, then P m j decides by the invalid position rule, hence at some point in the execution p j evaluates you j .pos prev j as true in line 08. Thus, there must exist a prefix λ of α β such that p i 's last read in λ (in line 05) results in it executing lines 11-15 and writing to me λ i .pos a value such that me λ i .pos prev λ j (with α a prefix of λ and prev α j = prev λ j ). Observe that p i changes me λ i .pos in order to get closer to p j 's position, hence you λ i .pos = M λ [j].pos prev λ j , implying that I λ j ⊈ prev λ j , contradicting Lemma 13. Thus, P m j cannot decide by the invalid position rule. We prove that M α [i].pos ∈ prev α j , by considering two possibilities. (1) P k i decides by the closeness rule Note that me α i .pos = M α [i].pos and you α i .pos = M α [j].pos. The fact that P k i decides by the closeness rule implies that at the end of α, when p i executes line 08, it sees that M α [j].pos = you α i .pos ∈ ranдe α i . Since the round counter of each process increases monotonically, we have that rad(ranдe α i ) ≤ rad(I α j ), hence M α [i].pos = me α i .pos ∈ I α j . By Lemma 13, I α j ⊆ prev α j , from which follows that M α [i].pos ∈ prev α j . (2) P k i decides by the invalid position rule. Hence, at the end of α, when p i executes Line 08, it sees that you α i .pos = M α [j].pos prev α i . Lemma 16 directly implies that M α [i].pos ∈ prev α j . In both cases, M α [i].pos ∈ prev α j and hence P m j decides by the closeness rule.

	i	⊆ prev α i and the lemma follows.	□	□

Implementations of this kind were initially called nonblocking[START_REF] Herlihy | Wait-free synchronization[END_REF], but we use the more contemporary terminology.

The separation question is trivial if n-process consensus objects are available since they support a wait-free implementation for n-processes of every object with a sequential specification[START_REF] Herlihy | Wait-free synchronization[END_REF].

* Partially supported by the Israel Science Foundation (grant 1749/14). † Partially supported by project PAPIIT UNAM IA102417. ‡ Partially supported by the Israel Science Foundation (grant 1749/14). § Part of this work was done while this author was at the Department of Computer Science, Technion, supported by the Israel Science Foundation (grant 1749/14).

A ADDITIONAL PROOFS FOR SECTION 3

We present additional details for the correctness analysis of Algorithm 1; some technical proofs are omitted for lack of space.

For an execution α, we use the following notation and terminology. If α is finite, v α i denotes the value of local variable v of a process p i at the end of α, while M α denotes the value of the shared array M at the end of α. I α i denotes the interval

If α is finite and ends with a read step of p i that makes its current operation decided, then rad(prev α i ) is the radius of the interval prev α i with center me α i .pos. The following lemma can be easily proved by induction on the length of the execution α.

Lemma 12. In every finite execution α, for i ∈ {0, 1}, M α [i].pos = y/2 me α i .r ound +you α i .r ound , for some integer y ≥ 0. Lemma 13. Let λ = αe 1 e 2 • • • e ℓ be a finite execution. Then, I λ i ⊆ prev α i .


I Perrin

Y Bidel

N Zahzam

C Blanchard

A Bresson

M Cadoret

Proof-of-principle demonstration of vertical gravity gradient measurement using a single proof mass double-loop atom interferometer

We demonstrate a proof-of-principle of direct Earth gravity-gradient measurement with an atom interferometer-based gravity gradiometer using a single proof mass of cold 87 Rb atoms. The atomic gradiometer is implemented in the so-called double-loop configuration, hence providing a direct gravity-gradient dependent phase shift insensitive to DC acceleration and constant rotation rate. The atom interferometer (AI) can be either operated as a gravimeter or a gradiometer by simply adding an extra Raman π-pulse. We demonstrate gravity-gradient measurements first using a vibration isolation platform and second without seismic isolation using the correlation between the AI signal and the vibration signal measured by an auxilliary classical accelerometer allowing to bypass the absence of common-mode vibration noise rejection in a double-loop geometry.The simplicity of the experimental setup (a single atomic source and unique detection) and the immunity of the AI to rotation-induced contrast loss, make it a possible candidate for onboard gravity-gradient measurements.

I. INTRODUCTION

Light-pulse Atom Interferometers (AIs) use short pulses of light to split, redirect, and then recombine cold atoms used as a matter-wave source. Since their advent in the 1990's [1,2], they have demonstrated to be extremely sensitive and accurate sensors very useful in fundamental physics research where they have been used to measure fundamental constants [3][4][5][6], test the equivalence principle [7][8][9][10][11], put bounds on theories of dark energy [12], probe quantum superposition at the macroscopic level [13] as well as measuring gravito-inertial force such as gravity acceleration [14][15][16][17][18], rotations [19][20][21][22] and gravity-gradient [23][24][25][26]. Most of these works consist in laboratory experiments but atom interferometer's inherent long term stability and accuracy have led to a global push towards performing experiments outside laboratory environment [17,27,28]. Moreover, cold atom-based gravity sensors have started to be commercialized, hence targetting out of the lab applications. In this context, development of gravity gradiometers are also particularly attractive as they complement pure gravity measurements and find variety of applications including geodesy [29], geophysics [30] and inertial navigation [31] for which the required performances are around 10 E / √ Hz for terrestrial instruments and around few mE/ √ Hz for space instruments. Whereas an atomic gravimeter sensitivity is often limited by vertical vibration noise, it is not the case in a conventional atomic gradiometer where the gravitygradient is derived from the differential measurement of two simultaneous atom interferometers performed at two locations. However, this requires to use two clouds of * malo.cadoret@lecnam.net cold atoms spatialy separated. This can for example be achieved by using laser-cooled atomic sources originating from two separate 3-dimensional magneto-optical traps (3D-MOT) [23], or by launching the atoms from a single MOT using moving molasses [24] or Bloch oscillations as an atomic elevator [32,33] or using Large Momentum Transfer (LMT) beam splitters combining Bragg pulse and Bloch oscillations [START_REF] Estey | Precision Measurement in Atom Interferometry Using Bragg Diffraction[END_REF]. Although these techniques have proven to work in laboratory environment, their complexity could still be an issue regarding their implementation for onboard applications where simple and compact instruments are required. In this paper, we perform a proof-of-principle experimental demonstration of an alternative method consisting in a direct measurement of the vertical gravity gradient with only one source of cold 87 rubidium atoms in the presence of vibration noise. We use a double-loop four-pulse AI geometry as proposed initially in [START_REF] Clauser | [END_REF] for gravity gradient measurements which was investigated in [23] [START_REF] Chung | Applications of atom interferometry using an improved laser cooling method[END_REF] and now used in several experiments such as rotation rate measurements in atomic fountain configurations [22,[START_REF] Stockton | [END_REF] or for low frequency vibration noise rejection in the context of airborne tests of the Weak Equivalence Principle (WEP) using atom interferometry [27]. We perform vertical gravity gradient measurement with and without a passive isolation vibration platform and show that in the presence of parasitic ground vibrations the correlation of the vibration signal measured by a classical accelerometer [32,38,39] allow to recover the interference fringes and extract the vertical gravity gradient. Moreover, we make a study of the systematics when using this doubleloop AI geometry. The paper is organized as follow: section II presents the double loop four-pulse AI used to measure the vertical gravity gradient. Section III presents the experimental setup. Section IV describes the vertical gravity gradient measurement performing the AI with a passive vibration isolation platform and Section V presents the measurement without seismic isolation, using the correlation technique. SectionVI presents a study of the major systematic effects which affect the measurement. Finally in Section VII, a discusssion on scale factor comparisons between dual cloud AI versus single cloud four-LPAI is made and possible improvements of the measurement are presented.

II. FOUR PULSE ATOM INTERFEROMETER-BASED GRAVITY GRADIOMETER

We consider a four pulse AI. The matter-wave beam splitters and mirrors are based on two-photon counterpropagative Raman transitions between the F = 1 and F = 2 hyperfine ground states of rubidium 87 atoms (see FIG. 1(a)). An atom initially in state |F = 1, p is coupled to state |F = 2, p + hk eff where hk eff is the two-photon momentum transfer. Here

k eff = k 1 -k 2 is the effective wave vector (with || k eff || = || k 1 || + || k 2 ||
for counterpropagative transitions). The AI consists of the light-pulse sequence (π/2 -π -π -π/2) which differs from a usual Mach-Zehnder atomic gravimeter by the presence of an additional π-pulse and a different time sequence. Practically, a first π/2-pulse creates an equal superposition of ground (F = 1) and excited (F = 2) states. Then, two π-pulses redirect the two atomic paths letting the wave packets crossing each other in between, and a final π/2pulse interferes the wavepackets. Thus, this sequence leads to a double-loop geometry. In our configuration, k eff is aligned with the local gravity acceleration g, for all Raman pulses. This sequence allows to measure the time derivative of the acceleration of the free-falling atoms.

Although a symmetric configuration is necessary to fully cancel the phase contribution due to constant acceleration [40], a time asymmetry ∆T is introduced to avoid interference of parasitic Ramsey-Bordé interferometers due to imperfect π pulses [22], see FIG1(b). In the absence of time asymmetry, these parasitic interferometers would close at the same time as the main interferometer and generate amplitude noise and a possible bias on the gravity gradient determination. In the short, intense-pulse limit, the phase shift along the Raman laser direction of propagation, is expressed as [40]:

∆Φ = 4(k eff g -α)T ∆T -(2k eff v z T 3 + 4k eff gT 4 )Γ zz +4k eff a vib T ∆T -2k eff ȧvib T 3 ≡ ϕ g + ϕ grad + ϕ vib (1)
where g is the Earth gravity acceleration along the Raman laser beams, α the radio frequency chirp rate applied to the effective Raman frequency to compensate the Doppler shift induced by the atom free-fall in order to keep resonance, Γ zz the vertical gravity gradient com- ponent, v z the initial atomic velocity along the vertical z axis at the first Raman pulse, a vib the mirror acceleration, ȧvib its time derivative, and T the time between the Raman π/2 and π pulses in absence of timing asymmetry. In Eq.( 1), the contribution to the phase shift contains three separate terms. The first term ϕ g is a remaining sensitivity to gravity acceleration induced by the timing assymetry ∆T . We have embedded the laser phase αT ∆T in this term. The second term is the gravity gradient dependent phase shift ϕ grad , and finally the third term is the phase shift induced by vibrations which we denote ϕ vib . This vibrational phase noise may prevent from discriminating spatial acceleration variations from time varying acceleration variations, and remains an issue for gravity gradient measurements performed in this double-loop geometry. Nevertheless, to circumvent this problem the AI can be operated using a passive vibration isolation platform (ϕ vib 0) or by estimating the ϕ vib phase term induced by the Raman mirror vibration using the acceleration noise recorded by an auxilliary classical accelerometer rigidly fixed to the Raman mirror. We have operated the AI using these two schemes.

2k eff ΓzzvzT 3 2.2 3 × 10 -7 k eff ΓzzvrT 3 1.7 × 10 -2 2 × 10 -9
For both schemes the atomic gradiometer is operated in its most sensitive configuration with T = 38, 6 ms limited by the falling distance (see III), a timing asymmetry ∆T = 300 µs , an initial velocity at first Raman pulse v z = 0.38 m/s, leading to phase shift values reported in Table I. The time asymmetry has been chosen experimentally to avoid the extra RB interferometers to form fringes, thus maximizing the signal-to-noise ratio of the AI. For our application we have neglected the effect of the recoil phase shift.

III. EXPERIMENTAL SETUP

In this section we describe the main parts of the apparatus as well as the time sequence of the experiment.

A. Apparatus overview

Our experimental setup is schematically shown in FIG. 1. It consists of a titanium vacuum chamber where the atoms are produced and interrogated and to which are connected ion pumps, getters and rubidium dispensers. The vacuum chamber is magnetically shielded with two cylindrical layers of µ-metal. The cold atom source is produced at the top of the chamber using a 3D MOT configuration. The falling distance available for interferometry is 20 cm from the MOT. The two counterpropagating Raman beams are obtained with a phasemodulated laser at 6.8 GHz retro-reflected on a mirror (Raman mirror). The Raman laser beams enter the vacuum chamber through the top window. After passing through a quarter wave plate they are retroreflected by the Raman mirror at the bottom of the setup, outside the vacuum, in order to realize the counterpropagating configuration, thus obtaining a lin ⊥ lin configuration in the AI region. In this configuration, two pairs of counterpropagating Raman beams (↑ k 1 , ↓ k 2 and ↓ k 1 , ↑ k 2 ) in the vertical direction are present. Degeneracy between the two pairs of Raman beams is lifted through Doppler shift induced by gravity during free fall of the atoms. In this configuration, only the Raman mirror needs to be isolated from ground vibrations. In our setup the mirror is rigidly linked to a classical accelerometer (Titan Nanometrics) the whole being fixed to a passive vibration isolation platform (Minus-K).

B. Optical setup

The laser system used for cooling, detecting and driving the interferometer pulses is similar to the one descibed in [41]. Basically, it consists in a compact and robust laser system based on a single narrow linewidth Erbium doped fiber laser at 1.5 µm, amplified in a 5 W Erbium doped fiber amplifier (EDFA) and then frequency doubled in a periodically poled lithium niobate (PPLN) crystal. A power of 450 mW is available at 780 nm. The Raman laser and the repumper are generated thanks to a fiber phase modulator at 1.5 µm allowing to be free from any phase lock loop between the two Raman lines.

C. Experimental sequence

The experimental sequence of the atomic gradiometer is the following: first, a cold 87 Rb sample is produced in a 3-dimensional MOT, loaded from a background vapor pressure of ∼ 10 -8 mbar. After 700 ms of trap loading, a stage of optical molasses and a microwave selection, we assemble N at ∼ 5 × 10 7 atoms in the magnetic insensitive groundstate |F = 1, m F = 0 at a temperature Θ = 3 µK. A push beam gets rid of the atoms left in state F = 2. Then, after 38.6 ms of free-fall we apply the AI sequence consisting in four Raman laser pulses of 8,16,16 and 8 µs. This time delay before the first Raman pulse is necessary to first lift degeneracy between the two pairs of Raman beams and second to minimize the impact of parasitic Raman lines (see section VI). During the AI operation a bias magnetic field of 100 mG is applied. We set T = 38.6 ms corresponding to total interrogation time 4T = 154.4 ms. Following the interferometer sequence we measure the proportion of atoms in the two output ports F = 2 and F = 1 of the interferometer using state selective vertical light-induced fluorescence detection. The fluorescence is collected thanks to collimation lenses and photodiodes in the perpendicular direction. The measurement of the proportion of atoms P in the state F = 2 at the exit of the interferometer is a sinusoidal function of the interferometric phase shift:

P = P m + C 2 cos(∆Φ) (2)
where P m is the fringe offset, and C the fringe contrast which is in our case C = 0.1. Interferometric fringes are thus obtained through scanning the interferometric phase. In our experiment we operate the interferometer with and without vibration isolation platform. Therefore, a scanning of the phase is obtained first by varying the frequency chirp rate of the Raman laser and second by letting vibration noise operate a random sampling of the interferometric phase. The repetition rate of the experimental sequence is 1 Hz, including atom loading, state preparation, atom interferometry, and state detection. The whole experimental sequence timing and data aquisition is computer controlled.

IV. GRAVITY GRADIENT MEASUREMENT WITH VIBRATION ISOLATION

In this section we present the vertical gravity gradient measurement when operating the AI with a vibration isolation platform.

A. Measurement method

To measure the vertical gravity gradient we take advantage of the acceleration sensitivity induced by the timing assymetry ∆T of the interferometer. In presence of a vibration isolation platform (ϕ vib ≈ 0), interferometer fringes can be obtained by scanning the frequency chirp α. The interference phase is obtained using the Fringe-Locking Method (FLM) similar to the one described in [17], which determines the frequency chirp nulling the phase. The sign of the radio-frequency chirp is changed every two drops, hence reversing the sign of k eff to cancel some systematic effects. Nevertheless, in our protocol, we supress sensitivity to gravity acceleration by periodically reversing the sign of ∆T (every 5 minutes), hence reversing the sign of the acceleration phase shift in Eq. (1). Nulling the phase shift in both configuration and taking the mean value leads to:

Γ zz = 2T ∆T (α 0 --α 0 + ) 2k eff v z T 3 + 4k eff gT 4 (3)
where α 0 + ,(α 0 -) is the frequency chirp which nulls the phase for ∆T (-∆T ) respectively.

B. Gradiometer sensitivity

We have operated the gravity gradiometer continuously during 2 days using the experimental sequence decribed in (III C). The time assymetry ∆T is changed every 5 minutes. We obtained from equation (3) the uncorrected vertical gravity gradient mean value Γ zz = 7600 E. The Allan Standard Deviation (ADEV) on the gravity gradient measurements is shown on FIG. days of measurements. The stability of the gravity gradient measurement improves as t -1/2 (where t is the measurement time) and reaches 766 E after 2 hours. The sensitivity of the single proof-mass atomic gradiometer still remains beyond state of the art atomic gradiometer using two simultaneous accelerometers with two proofmasses in differential mode [23,24,26]. The sensitivity of our measurement is not limited by the contribution of residual vibration noise which has been measured with our low noise accelerometer at the level of 10000 E/ √ Hz, nor by detection noise which has been estimated at the level of 9500 E/ √ Hz, with a calculated quantum projection noise (QPN) of 4200 E/ √ Hz for ∼ 5 × 10 6 atoms. The other technical noise sources (microwave phase noise, laser frequency noise, Raman pulses intensity fluctuations...)which may limit the sensitivity of the measurement have not been studied. We have investigated the main systematic effects which induce a bias on the gravity gradient measured value using this method. These systematics are presented in section VI.

V. GRAVITY GRADIENT MEASUREMENT USING THE CORRELATION TECHNIQUE

In this section we present gravity gradient measurement in the presence of vertical vibration noise.

A. Measurement method

First the vibration isolation platform on which is fixed the Raman mirror is made non-floating. In the absence of vibration isolation ϕ vib = 0 in Eq.1, thus the conventional FLM used in IV A is not applicable anymore as it requires phase fluctuations to be smaller than π. To circumvent the presence of vibration excess noise which washes out fringe visibility, we perform a correlation-based-technique [38,42] combining the si- multaneous measurements of the output signal P of our interferometer and the one from a classical accelerometer fixed to the Raman mirror (see FIG( 1)). The method is the following: First we held the laser phase fixed by setting the radiofrequency chirp α 0 to its value compensating for gravity acceleration leading to ϕ g = 0. This value of α 0 is determined by operating the interferometer as a conventional 3-pulse Mach-Zehnder interferometer using T = 81.9 ms (Where T is the time between two-consecutive Raman pulses). Second, the AI is operated with the same experimental sequence except that the radiofrequency chirp sign is changed every measurement cycle. The atomic fringes are scanned due to random vibration noise. The probability P of the interferometer is plotted versus the estimated induced vibration-phase ϕ E vib , which is numerically calculated at each cycle by convoluting the mirror acceleration a M (t) measured by the classical accelerometer, with the time response funtion h at (t) of the AI:

ϕ E vib = k eff a M (t)h at (t)dt (4)
where h at is a double triangle-like function represented on FIG.

(3) defined as:

h at (t) =        t T 2 if 0 < t < T + ∆T 2(T +∆T )-t T 2 if T + ∆T < t < 3T + ∆T t-4T T 2 if 3T + ∆T < t < 4T 0
Otherwise.

(5) Finally, we perform a sinusoidal least-square fit of the data using the function:

P = A + B 2 cos ϕ E vib + δφ (6)
where A, B and δφ are free-parameters. Performing a measurement of the transition probability in four configurations ( k eff ↑, ↓, ±∆T ) where reversing the sign of k eff (e.g changing the sign of α) allows to reject some systematics, and reversing the sign of ∆T suppresses residual dependence to constant acceleration, one can obtain the gravity gradient.

B. Experimental results

We performed gravity gradient measurement during two hours integration time. For the measurement, the sign of ∆T was changed after one hour integration time whereas the direction of the effective wavevector was reversed every measurement cycle. Atomic fringes in configuration (±∆T ) are displayed on FIG. 4 when operating the interferometer with total interrogation time 4T = 154.4 ms. We obtained 4 spectra in total corresponding to approximately 1800 points per fringe pattern. δϕ is estimated from the fit to the data points for each fringe pattern. The gravity gradient is extracted from the phase offset δϕ considering the four configurations ( k eff ↑, ↓ , ±∆T ) leading to 4 phases (δϕ ↑,+ , δϕ ↑,-, δϕ ↓,+ , δϕ ↓,-). Considering the experimental protocol one obtains:

Γ zz = 1 4 (δϕ ↑,+ + δϕ ↑,-+ δϕ ↓,+ + δϕ ↓,-) 2k eff v z T 3 + 4k eff gT 4 (7)
corresponding to an uncorrected gravity gradient of Γ zz = 3691 E. The sensitivity of the gradiometer is evaluated from the combined statistical uncertainty from the fitted fringes leading to δΓ zz = 2355 after 2 hours integration time. The sensitivity of the measurement using the correlation technique is degraded by a factor of 3 in comparison with the measurement performed in presence of vibration isolation. First, a decrease by a factor of √ 2 may originate from the use of a Fringe Scanning (FS) method instead of a more sensitive Fringe Locking Method [43]. Second, degradation of the sensitivity may come from non-perfect correlations due to several factors that we did not have time to investigate such as : misalignment between the classical accelerometer and the AI, unprecise knowledge of the mechanical accelerometer scale factor, uncertainty in the accelerometer transfer function, bias drift, among others. We estimate the classical accelerometer self-noise to limit our sensitivity at the level of 2 E/ √ Hz. An improvement of the sensitivity on our measurement is therefore possible. We give in section VII some possible improvements of the method.

Systematic effects are studied in the next section.

VI. SYSTEMATIC EFFECTS

In this section we present a study of the main systematics limiting the measurement of the gravity gradient and their related uncertainties.

A. Effect of a slope on fringe offset

In our experiment, we noticed that the fringes obtained by scanning α have a slope on the offset. This slope is due to a change in the resonance condition which appears because of a relatively large fringe spacing (∝ 1/4T ∆T ) relative to the fringe envelope (∝ 1/τ π/2 ). The effect can be seen on (FIG. 5). This slope is different for each of the four configurations and therefore when the FLM [17] is used, it is responsible of a bias on the gravity gradient measurement equal to:

∆Γ = π 24Ck eff gT 5 ∆T × A ( 8
)
where A is the slope of the fringe offset defined as: A has been measured for the four configurations of the experiment ( k eff ↑, ↓, ±∆T ). From these four measurements one can obtain the value of A to estimate the bias:

P m = P m0 + (α -α 0 )A (9)
A ↑,↓,± = (A ↑,--A ↓,-) -(A ↑,+ -A ↓,+ ) 2 ( 10
)
Using the value of A from equation ( 10), one obtains an estimated bias equal to 4351 E ± 430 E in our configuration.

B. Raman detuning

The non-perfect resonance of the Raman pulses is responsible of a phase shift equal to:

∆Φ res = δτ -atan δ+δ LS1 √ Ω 2 +(δ+δ LS1 ) 2 tan Ω 2 + (δ + δ LS1 ) 2 τ 2 -atan δ+δ LS4 √ Ω 2 +(δ+δ LS4 ) 2 tan Ω 2 + (δ + δ LS4 ) 2 τ 2 ( 11
)
where δ is the two photon Raman detuning in absence of Light-Shift (LS), δ LS1(4) is the one and two photon Light-Shift at the first(last) pulse, Ω is the effective Rabi pulsation and τ is the first and last pulse duration. This expression is given for a pulse separation T , 2T and T defined between the pulse centers. We notice that this expression is different from a standard MZ AI by the sign between the two atan terms and by the additional terms δτ . Thus, contrary to a MZ AI, the effect of Raman detuning does not cancel in a 4 pulses AI. This effect has thus to be evaluated precisely.

Residual sensitivity to atom velocity

By assuming δ Ω, π/2 pulses (Ωτ = π/2) and neglecting LS, one obtains:

∆Φ res = δ(1 - 4 π )τ (12)
A non-zero detuning and thus a non-resonant atom velocity compared to the Raman transition is responsible for a phase shift. This phase shift can be interpreted as a non-closed AI (see FIG. 6). To circumvent this effect, one has to add a time shift δT = 1 µs between the π/2 pulse and the π pulse. Thus, a time compensation δT = 1 µs is added to the sequence to compensate for this effect. Nevertheless, experimental defaults such as non perfect π 2 pulse or pulse shape asymmetry could affect this timing. We thus measured experimentally the phase shift (see FIG. 7). This was done by varying the time delay at which the radiofrequency chirp α used to compensate the Doppler shift is switched on. One obtains a slope of 3000 E/ms. The uncertainty on the atom velocity is estimated at 1 mm/s leading to an uncertainty on the gravity gradient equal to 300 E.

Light shift

In our experiment, the one photon light-shift is largely canceled by adjusting the intensity ratio between the Raman lasers and using the effective wave vector reversal protocol. Nevertheless, sensitivity to laser detuning remains through two-photon light-shift (TPLS) [START_REF] Cladé | [END_REF].

In our experiment the TPLS is estimated by measuring the gravity gradient as a function of the π/2 pulse duration keeping effective Rabi frequency constant. For the measurements, the mirror pulses are kept constant to preserve the interferometer's contrast. One can see on equation (11), that the phase shift goes to zero when the pulse duration goes to zero regardless the detuning and the effective Rabi frequency. Numerical simulation taking into account the velocity distribution of the atoms shows a linear dependence with the pulse duration with our experimental parameters. Moreover, as the contrast changes with the pulse duration, the measurements are corrected from the slope effect (see FIG. 8). From the linear fit of the measurements we obtained a bias of ∆Γ = -4351 E ±2019 E (uncertainty from the fit).

C. Additional Raman laser lines

Our method of generating the Raman laser by modulation leads to the presence of additional laser lines inducing a supplementary phase shift which if not corrected, induces an error on the gravity gradient measurement. We can numerically calculate this supplementary phase shift according to [46] and transposing to the case of a four-pulse AI. In the symmetric configuration of the interferometer (∆T = 0) it is possible to find an AI configuration where this phase shift is equal to zero. This corresponds to the case where the distance between the position of the atoms at the moment of the four Raman pulses are multiples of the microwave wavelength Λ = c/2ω HF S . According to [46] and transposing to the four pulse AI the conditions on interrogation time T and initial velocity of the atoms are given by:

T = nΛ 3g and v z = n Λ -1 2 gT 2 T with n, n ∈ N (13)
Considering the available free-fall height of 20 cm one finds n = 2 and n = 1 leading to T = 38.6 ms and initial atomic velocity at first Raman pulse v z = gT = 0.38 m.s -1 . However, timing assymetry ∆T = 300 µs required to avoid the presence of extra RB interferometers, changes the atoms position and prevents from operating the interferometer in this optimal configuration. We have numerically calculated the error on the gravity gradient for time assymetry ∆T = 300 µs. This error is a periodic function of the atom-mirror position z M and is comprised between -300 E and 180 E.

D. Verticality

In our setup, verticality can be ensured with an error of about δθ = 80 µrad. As a consequence, supplementary terms in the phase shift arise from the projection of gravity on the horizontal axis which leads to a transverse velocity of the atoms δv = gδθT and a sensitivity to rotation rate with respect to horizontal axis Ω y . According to [40] this supplementary phase shift is expressed as φ = 4kΩ y δvT 2 = 0.14 mrad corresponding to an uncertainty of ±67 E on gravity gradient with Ω y the Earth rotation rate.

E. Drift of classical accelerometer

The gravity gradient measurement using the correlation technique is sensitive to errors on the measurement of vibrations such as the bias a b of the classical accelerometer and its drift da b dt during the measurement. We have estimated this drift by measuring the output signal of the accelerometer as a function of time during one day. The bias drift has been estimated from a linear fit to the data to da b dt = -0.47 × 10 -9 g/s. From this measurement we have calculated the bias phase induced by the bias drift of our mechanical accelerometer:

ϕ b = 4k eff da b dt T ∆T × T ∆T + 2k eff da b dt T 3 (14)
The first contribution to the bias phase arises from the change in acceleration bias between 2 measurements performed at ∆T and -∆T respectively. In our experimental protocol,the time assymmetry is changed after a time T ∆T = 1 hour leading to a bias phase 1.26 mrad corresponding to a bias ∆Γ = 900 E.

The second effect arises from the contribution of the drift during the interferometer integration time. This term gives rise to a bias on the gravity gradient measurement of ∆Γ = da b /dt 2gT = 62 E.

F. Effect of magnetic field

Our interferometer sequence is applied to atoms selected in the m F = 0 state. Nevertheless, a quadratic Zeeman shift and an inhomogeneity in the bias magnetic field applied to the atoms during the interferometer induces an additional phase shift and a bias on the gravity gradient measurement that can be calculated using [47]. Thanks to our effective wave vector reversal protocol, this effect is mainly canceled and the associated bias is ∆Γ = 100 E ± 100 E.

G. Self attraction effect

Because our experimental setup is not massless, one has to take into account the gravitationnal attraction of the upper part and lower part of the titanium vaccuum chamber on the atomic sensor. The mass difference between the two parts is estimated to ∆m = 1.5 kg. Thus, using a point mass calculation approximation, one can estimate this mass difference to induce an artificial gravity gradient effect of the form ∆Γ = 2G∆m r 3 where G = 6.67 × 10 -11 N.m 2 kg -2 is the gravitational constant and r the distance between the masses. Assuming the distance from the atoms to be between 5 cm and 10 cm the effect is comprised between 1600 E and 200 E respectively.

H. Conclusion on systematic effects

The results of the main systematics are summarized in Table II. We finally obtained the gravity gradient values Γ

VII. DISCUSSION AND POSSIBLE IMPROVEMENTS

We have compared the scale factor (S = ∂∆Φ/∂Γ) of our four pulse AI with the one of a conventional atomic gradiometer using two pairs of Mach-Zehhnder-like atom accelerometers in differential mode. For this comparison we have adressed both Earth-based, and space-based (e.g microgravity) issues. The calculation assumes a total interrogation time T int and apparatus length L. We have neglected the recoil effect term. The recoil term is responsible of a displacement of the atoms that we have assumed to be small compared to the length of the apparatus for our interrogation time. Nevertheless, this term should be considered for long interaction time where the atom displacement is larger. Results are presented in table III. From III, in a microgravity environment, a dual Mach-Zehnder atom accelerometer geometry has a scale factor 8 times larger than the one of a four-pulse AI. However, using a single cloud atomic gradiometer for terrestrial applications could be of interest as the reduction in its scale factor is only a factor of 2. This scale factor reduction has to be put in balance with the ease of implementation of such an experimental setup which only requires (i) one atomic source, (ii) an additional Raman π-pulse with respect to a conventional Mach-Zehnder atomic gravimeter.

One can calculate the gravity gradient sensitivity δΓ that can be obtained using the correlation technique and considering an Earth based gravity gradient measurement with an interrogation time T int = 4T corresponding to a 1 meter length apparatus. We have taken the case where the atoms are not launched.

Assuming that the ultimate phase resolution is quantum projection noise limited δ(∆Φ) ≈ 1/ √ N at the singleshot gradiometer sensitivity is given by:

δΓ ≈ 2 6C √ N at k eff gT 4 (15)
Assuming 10 6 detected atoms, a total interrogation time of 4T 452 ms, a contrast of C = 0.5 wich can be obtained with a thermal atomic sample using adiabatic passage technique [48] one obtains δΓ ≈ 13 E/ √ Hz. This sensitivity can be obtained at the condition that the correlation technique used to bypass the absence of commonmode vibration noise discussed in [23] is not limited by the mechanical accelerometer's sensitivity. The mechanical accelerometer's self-noise has been estimated to ≈ 1 E/ √ Hz, and is therefore not limiting the sensitivity for a typical laboratory environment. We can expect an improvement of our atomic gradiometer. When using the correlation technique, an increase in sensitivity could be obtained (i) by changing the sign of the timing assymetry ∆T at the repetition rate of the experiment, hence reducing the effect of the classical accelerometer drift by a factor of 3600,(ii) replacing the fringe fitting procedure by a more sensitive FLM technique using the signal of the classical accelerometer to compensate in real time the phase shift of the AI as in [39]. When measuring the gravity gradient using the vibration isolation platform, applying a phase step δϕ on the Raman laser phase rather than changing the chirp rate α when performing the FLM technique, would allow to cancel the slope effect as the same slope would appear for each of the four fringe patterns. In the scope of field applications, using a single-cloud double-loop AI geometry allows to be insensitive to Coriolis force [49] which is responsible of both a bias and mostly a severe loss of contrast when performing the AI on a boat [28] or a plane [27] if no rotation compensation is used such as a tip-tilt mirror [50] or a gyrostabilized platform.

VIII. CONCLUSION

In conclusion, we have demonstrated an experimental proof-of-principle measurement of the vertical gravity gradient using a single proof mass of cold 87 Rb atoms and a four-pulse double-loop AI. We performed the measurements first using a vibration isolator and then demonstrating the correlation technique in presence of vibration noise. The results obtained using both methods are in fair agreement despite a reduced sensitivity in comparison with state-of-the-art atomic gradiometers [23,24,26], due to a rather short interrogation time (4T = 154.4 ms) and absence of common-mode rejection in a doubleloop AI geometry. Better performances of the four-pulse gradiometer are expected with larger interrogation time. Moreover, efficient atom optics techniques such as adiabatic spin-dependent kicks (SDK) [48] could allow enhancement of the gradiometer'sensitivity without need for a colder atomic sample, thus relaxing the complex-ity of the setup. However, these adiabatic passage techniques still need to be investigate as they may induce uncontrolled phase shifts and therefore additional biases. Finally, in the context of onboard applications, we demonstrated the possibility, in a strap down configuration, to bypass the absence of vibration noise rejection using a correlation technique in combination with a simple experimental setup (one single proof-mass and unique detection) with the possibility to switch easily from a gravimeter to a gradiometer immune to constant rotation rate. Despite a reduced sensitivity compared to state of the art setups [51], investigating further the limits of this technique could be of interest for the realization of instruments dedicated to gravity or gradiometry measurements in noisy environments.

FIG. 1 .

 1 FIG. 1. (a) Left: Energy level scheme of rubidium D2line. Two-photon Raman transitions performed on a single cloud of 87 rubidium atoms in vertical configuration.(∆ is the one photon detuning from the electronic transition.) Right: Schematic of the experimental setup. The Raman laser beams are aligned along gravitational acceleration g.PD: Photodiode.(b) Space-time recoil diagram in the absence of gravity of the four pulse double-loop AI based gravity gradiometer. A time asymmetry ∆T is implemented to suppress parasitic Ramsey-Bordé interferometers (labeled RB1 and RB2 on figure) (dash line) due to imperfect mirror pulses.

FIG. 3 .

 3 FIG. 3. (a)Four pulse AI response function hat neglecting pulse duration for a symmetric (solid line) and asymmetric (dash line) configuration. (b) Response function of the resisual sensitivity to DC acceleration is obtained from the difference between asymmetric and symmetric four pulse AI response functions.

FIG. 4 .

 4 FIG. 4. Measured transition probabilities versus estimated vibration phase calculated from the signal of the classical accelerometer. The atomic gradiometer operates with total interrogation time 4T=154,4 ms. The solid line is a sinusoidal least-squares fit using equation (6). (a) Interference fringes when using +∆T timing assymetry.(b) Interference fringes obtained in the -∆T configuration. Two other spectra are obtained reversing the sign of the wavevector.

2 FIG. 5 .

 25 FIG. 5. Effect of slope on fringe offset. The blue line is the estimated fringe offset Pm = Pm0 + 2πAα.

FIG. 6 .

 6 FIG. 6. (a): Space-time diagram of atom classical trajectory for the 4 pulses AI in absence of gravity. We consider that the path separation occures at the expect value of the position response during the pulse (tsep = τ 0 fp(t)dt). This separation time corresponds to the moment where the laser phase is imprinted on the atom wave function assuming that the laser phase has a linear time dependance during laser pulse.(b) Position response function fp(t) of the four-pulse AI considering finite Raman pulses [44]. (c) Timing diagram of the four pulse AI defining time with respect to the center of the Raman light-pulse.

FIG. 7 .

 7 FIG. 7. Gravity gradient measurement as a function of the time delay to switch on the radiofrequency chirp. The slope given by the linear fit is ≈ 3000 E/ms.

FIG. 8 .

 8 FIG.8. Variation of the gravity gradient value due to twophoton light shift (TPLS) versus π/2-pulse duration keeping Rabi frequency Ω constant. The Raman π-pulses are kept constant to preserve the interferometer's contrast. All data points are corrected from the effect of the slope on fringe offset. The slope given by the fit is -490 E/µs.

( 1 )

 1 zz = (6069 ± 2459)E and Γ (2) zz = (5173 ± 3428) E

TABLE I .

 I Phase shift terms numerical values assuming the following:k eff = 4π λ = 1.61 × 10 7 m -1 with λ = 780 nm the wavelength of the transition, vertical Earth gravity gradient Γzz = 3.1 × 10 -6 s -2 (assuming a spherical symmetric Earth) with g = 9.81 m.s -2 , interferometer pulse timing asymmetry of ∆T = 300 µs, T = 38.6 ms, initial velocity vz = 0.38 m.s -1 . The last term correponds to the recoil phase shift (vr = 5.89 mm.s -1 ). The gravimeter phase shift term is taken as reference.

	Phase term	Absolute numeric value	Relative phase
		[mrad]
	4k eff gT ∆T	7.3 × 10 6	1
	4k eff ΓzzgT 4	4.3	6 × 10 -7

  2. Each point correponds to the measurements averaged over 10 minutes corresponding to the time necessary to operate th AI in two configurations (+∆T and -∆T ).FIG.2. Allan standard deviation of the gravity gradient measurements. The dash line illustrates the t -1/2 scaling.

				3000
			zz
			Allan Standard Deviation of	1000	65000 E/Hz 1/2
				100
				1000	10000	100000
				t (s)
	sensitivity of 65000 E/	√	A short term Hz is obtained during the two

TABLE II .

 II Correction (Corr.) and uncertainties (u) in Eötvos [E] of the main systematic effects affecting the cold atom gradiometer using two different measurement mehods: (1) vibration isolated (2) Without vibration isolation.

	Source	Corr.	u	Corr.	u
		(1)	(1)	(2)	(2)
	Effect of slope	-4351	430	-	-
	Two-photon light shift	3920	2019	3920	2019
	Sensitivity to initial velocity 0	300	0	300
	Additional laser line	0 [-310;180] 0 [-310;180]
	Verticality	0	67	0	67
	Accelerometer drift	-	-	-1.5	962
	Effect of magnetic field	-100	100	-100	100
	Self attraction effect	-1000	1000	-1000	1000
	Statistical u.	-	766	-	2355
	Total	-1531	2459	2818	3428
	which are statistically in agreement. For both methods
	the dominant systematic uncertainty comes from TPLS
	effect. The correlation technique remains limited by
	statistical uncertainty. Our result is mostly consistent
	with a measurement performed by a calibrated relative
	gravimeter (Scintrex CG-3M and CG5) at the location
	of our experimental setup for different heights which led
	to Γ

zz = 3180 ± 30 E.

TABLE III .

 III Comparison in scale factors S, of Earth-based dual cloud atomic gradiometer with respect to a singlecloud gradiometer. L:apparatus length; g:gravity acceleration; Tint:total interrogation time. Tint = 2T (4T ) for a Mach-Zehnder type geometry and Four-pulse geometry respectively.

	Environment Mach-Zehnder 4-pulse AI Scale factor ratio
		SMZ	S4P	SMZ /S4P
	Microgravity	1 4 kLT 2 int	1 32 kLT 2 int	8
	Earth-based	1 8	kL 2 g	1 16	kL 2 g	2
	Earth-based
	+ atom launch	1 4	kL 2 g	27 256	kL 2 g	≈ 2.37

ACKNOWLEDGMENTS

We thank F. Nez, from Laboratoire Kastler Brossel (LKB), for discussions on the project. M.C. acknowledges funding from ONERA through Research Project CHAMO (Centrale Hybride AtoMique de l'Onera).