Hagit Attiya

Eshcar Hillel
email: eshcar@cs.technion.ac.il

Alessia Milani
email: alessia@cs.technion.ac.il

Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory * (Preliminary Version)

Keywords: D.1.3 [Programming Techniques]: Concurrent Programming; F.2.2 [Analysis of Algorithms and Problems]: Nonnumerical algorithms and problems Theory, Algorithms, Design Transactional memory, disjoint-access parallelism, partial snapshots, lower bound, impossibility result

Transactional memory (TM) is a promising approach for designing concurrent data structures, and it is essential to develop better understanding of the formal properties that can be achieved by TM implementations. Two fundamental properties of TM implementations are disjoint-access parallelism, which is critical for their scalability, and the invisibility of read operations, which reduces memory contention.

This paper proves an inherent tradeoff for implementations of transactional memories: they cannot be both disjointaccess parallel and have read-only transactions that are invisible and always terminate successfully. In fact, a lower bound of Ω(t) is proved on the number of writes needed in order to implement a read-only transaction of t items, which successfully terminates in a disjoint-access parallel TM implementation. The results assume strict serializability and thus hold under the assumption of opacity. It is shown how to extend the results to hold also for weaker consistency conditions, serializability and snapshot isolation.

INTRODUCTION

Transactional memory is an attractive paradigm for programming concurrent applications for multicores. A transaction encapsulates a sequence of operations, and it is guaranteed that if any operation takes place, they all do, and that if they do, they appear to other threads to do so atomically, as one indivisible operation. A transactional memory implementation translates high-level transaction operations to low-level primitive operations on base objects, containing the data and the meta-data needed for the implementation.

Transactional memory is seriously considered as part of software solutions and as a basis for novel hardware designs. It is therefore imperative to understand inherent tradeoffs in the design and implementation of transactional memory.

One property that is considered critical for the scalability of a transactional memory implementation is disjoint-access parallelism: operations on disconnected data should not interfere. Conceptualizing this notion is best done through the conflict graph of transactions that overlap in time. Informally, the vertices of the conflict graph correspond to data items, and there is an edge between data items if they are accessed by the same transaction. Consider, for example, four concurrent transactions: T1 with the data set {ı1, ı2}, T2, T3, and T4 with the data sets {ı2}, {ı3}, and {ı4}, respectively. Figure 1 depicts the conflict graph of the execution interval of these four transactions. This conflict graph contains only one edge connecting the two vertices representing the data items in the data set of T1 (see the formal definition in Section 2).

Several transactional memories, e.g. [START_REF] Avni | Maintaining consistent transactional states without a global clock[END_REF][START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF], guarantee that transactions access the same base object only if their data items are connected in the conflict graph. In particular, there is no concurrent access to the shared memory by transactions that access disjoint parts of the data. In such implementations, the transactions T1, T3, and T4 in the example above, do not access the same base object, since no path connects their data items in the conflict graph.

Another important goal is to optimize read-only transactions, i.e., transactions that access the memory only through read operations. It is desirable that in their implementations, read-only transactions do not execute primitive write operations to the memory, so as to reduce memory contention; implementations of read-only transactions that do not write to the memory are called invisible. Moreover, since read-only transactions do not write to data items, it seems plausible they should eventually be able to obtain a consistent view of the data, provided previous versions are kept (as is done in multi-version implementations [START_REF] Napper | Lock-free serializable transactions[END_REF][START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF][START_REF] Riegel | Snapshot isolation for software transactional memory[END_REF]). Thus, read-only transactions should (eventually) terminate successfully, regardless of concurrent transactions; such transactions are called wait-free.

None of the existing transactional memory implementations is both disjoint-access parallel and has invisible, waitfree read-only transactions. Some are disjoint-access parallel and have invisible but not wait-free read-only transactions [START_REF] Avni | Maintaining consistent transactional states without a global clock[END_REF][START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF], while others have invisible, wait-free read-only transactions but are not disjoint-access parallel [START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF].

Consider, for example, the four transactions above, and assume T1 is a read-only transaction, while T2, T3, and T4 all write to their data items. In the algorithm given in [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF], which is disjoint-access parallel and has invisible read-only transactions, T1 reads ı1 and ı2, then T2 writes to ı2, finally T1 validates its read set at commit time. The value of ı2 has changed since T1 read it, and T1 aborts. In the algorithm given in [START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF], which has invisible, wait-free read-only transactions, T1, T3, and T4 all access a common counter (T1 reads it, while T3 and T4 write to it), thus violating disjoint-access parallelism.

This paper shows that there is an inherent tradeoff-no transactional memory implementation can be disjoint-access parallel and have invisible, wait-free read-only transactionsand one of these desirable properties must always be compromised. In fact, we prove a stronger result, showing that in a disjoint-access parallel transactional memory implementation with wait-free read-only transactions, a transaction reading t data items must apply non-trivial primitives (e.g., writes) to at least t -1 base objects. Thus, a read-only transaction must perform one low-level write essentially for each item in its read set.

The wait-freedom requirement might seem too restrictive for practical purposes; however, we can prove a similar result where a read-only transaction repeatedly aborts and never terminates successfully; see further discussion in Section 6. For read-dominated applications, this implies too much wasted work.

The consistency condition commonly used for transactional memory is opacity [START_REF] Guerraoui | On the correctness of transactional memory[END_REF]; very roughly stated, opacity requires all transactions to appear to execute sequentially in an order that agrees with the order of non-overlapping transactions. This is similar to requiring strict view serializability [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF] applied to all transactions (included aborted ı1 ı2 ı4 ı3 T1 Figure 1: Example of a simple conflict graph: ı1 and ı2 are the data items of T1; ı2, ı3, and ı4 are the data items of T2, T3, and T4, respectively. ones), extended to allow operations other than reads and writes. Our results only assume strict serializability [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF], and hence hold also under the assumption of opacity. In fact, the results also hold for weaker consistency conditions, serializability and snapshot isolation.

The rest of the paper is organized as follows: Section 2 introduces basic definitions and in particular, the notion of disjoint-access parallelism. Section 3.1 presents an impossibility result showing that in a disjoint-access parallel STM implementation with invisible read-only transactions, some read-only transaction may never terminate successfully; this result is proved using only three processes. Section 3.2 strengthens this result and shows that a read-only transaction on t items (in a disjoint-access parallel STM implementation with wait-free read-only transactions) must apply non-trivial primitives to t -1 base objects; this result requires t + 1 processes. Section 4 extends the results to hold even with the weaker conditions of serializability and snapshot isolation. We discuss related work in Section 5, and conclude in Section 6.

PRELIMINARIES

A transaction is a sequence of operations executed by a single process on a set of data items shared with other transactions; all data items are initially 0. We assume data items are accessed by simple read and write operations; our impossibility results clearly hold for transactional memory that also supports other operations. A complete interface of transactional memory also includes commit and abort operations, which we do not model here, since they are not needed for our impossibility results.

The collection of data items accessed by a transaction is the transaction's data set; in particular, the items written by the transaction are its write set, and the items read by the transaction are its read set. A transaction whose write set is empty, is said to be a read-only transaction. We assume the transaction's read set and write set are provided at the start of the transaction, and do not elaborate further on the manner a transaction issues its operations; this only makes our impossibility results stronger.

An implementation of software transactional memory (abbreviated STM ) provides data representation for transactions and data items using base objects, and algorithms, specified as primitive operations on the base objects, which asynchronous processes have to follow in order to execute the operations of transactions. In addition to ordinary read and write primitives, we allow arbitrary read-modify-write primitives, even those accessing several locations simultaneously. In particular, the implementation may use a cas(o, exp, new) that writes the value new to location o if its value is equal to exp, and returns a success or failure indication.

A primitive is non-trivial if it may change the value of the object, e.g., a write or cas; otherwise, it is trivial, e.g., a read.

An event is a computation step by a process consisting of local computation and the application of a primitive to base objects, followed by a change to the process's state, according to the results of the primitive. A configuration is a complete description of the system at some point in time, i.e., the state of each process and the state of each shared base object. There is a unique initial configuration in which every process is in its initial state and every base object contains its initial value.

An execution interval α is a finite or infinite alternating sequence C0, φ0, C1, φ1, C2, . . ., where C k is a configuration, φ k is an event and the application of φ k to C k results in C k+1 , for every k = 0, 1, . . .. An execution is an execution interval in which C0 is the initial configuration.

Two executions α1 and α2 are indistinguishable to a process p, if p goes through the same sequence of state changes in α1 and in α2; in particular, this implies that it goes through the same sequence of events.

We point out that the model encompasses two levels of abstraction: The high level has transactions, each of which is a sequence of operations accessing data items. At the low level, these transactions are translated into executions in which a sequence of events apply primitive operations (or primitives) to base objects, containing the data and the meta-data needed for the implementation.

STM Properties. The interval of a transaction T is the execution interval that starts at the first event of T and ends at the last event of T , if there is one, taken by the process executing the algorithm for T . If T does not have a last event in the execution, then the interval of T is the (possibly infinite) execution interval starting at the first event of T . Two transactions overlap if their intervals overlap. A configuration C is quiescent if no transaction is pending in C, i.e., it is not inside the interval of any transaction.

An STM is serializable if transactions appear to execute sequentially, one after the other [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF]; we assume that the serialization preserves the per-process order, i.e., transactions of the same process maintain their order. An STM is strictly serializable if this order preserves the order of non-overlapping transactions [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF]; this notion is called orderpreserving serializability in [START_REF] Weikum | Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery[END_REF], and is the analogue of linearizability [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF] for transactions. Note that strict serializability is implied by the opacity correctness condition, recently defined for transactional memory [START_REF] Guerraoui | On the correctness of transactional memory[END_REF].

We assume that a transaction terminates successfully if it runs alone from a quiescent configuration. This property is satisfied by obstruction-free STM implementations, in which a process that eventually runs alone for long enough makes progress, i.e., transactions terminate successfully when eventually executing solo [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF]. This property is also satisfied by STM implementations that are weakly progressive [START_REF] Guerraoui | The semantics of progress in lock-based transactional memory[END_REF], in which a transaction that does not encounter conflicts has to terminate successfully; note that blocking STM implementations like TL2 [START_REF] Dice | Transactional locking II[END_REF] are weakly progressive.

Memory disjoint-access parallelism. An important property STM implementations have to provide is allowing unrelated transactions to progress independently, even if they are concurrent. Below, we formally define what it means for two transactions to be unrelated through a conflict graph that represents the relations between transactions. Then we define disjoint-access parallelism, a property that captures the intuition that an implementation should not cause two transactions, which are unrelated at the high-level, to simultaneously access the same low-level shared memory.

The conflict graph of an execution interval I is an undirected graph in which vertices represent data items and edges connect data items if they are accessed by the same transaction. If I overlaps the execution interval of a transaction T , and the data items ı1 and ı2 are in the data set of T , the graph includes an edge between the vertices representing ı1 and ı2.

Two transactions T1 and T2 are disjoint-access if there is no path between an item in the data set of T1 and an item in the data set of T2, in the conflict graph of the minimal execution interval containing the intervals of T1 and T2.

Two events contend on a base object o if they both access o, and at least one of them applies a non-trivial primitive to o. Two processes concurrently contend on a base object o if they have pending events at the same configuration that contend on o. Definition 1. An STM implementation is weakly disjointaccess parallel if two processes p1 and p2, executing transactions T1 and T2, concurrently contend on the same base object, only if T1 and T2 are not disjoint-access.

This definition captures the first condition of the disjointaccess parallelism property of Israeli and Rappoport [START_REF] Israeli | Disjoint-access-parallel implementations of strong shared memory primitives[END_REF], in accordance with most of the literature (cf. [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF]). Our definition is weaker than their definition, as it allows two processes to apply a trivial primitive on the same base object, e.g., read, when executing two transactions even if they are disjoint-access. Moreover, our definition only prohibits concurrent contending accesses, allowing transactions to contend on a base object o at different points of the execution; we shall see in Lemma 2 that, under some conditions, these transactions can be made to concurrently contend on o.

The original definition [START_REF] Israeli | Disjoint-access-parallel implementations of strong shared memory primitives[END_REF] also restricts the impact of concurrent transactions on the step complexity of a transaction; our results do not rely on this additional condition, making them stronger.

STRICTLY SERIALIZABLE STMS

Impossibility of Invisible Read-Only Transactions

A read-only transaction is invisible if its algorithm only applies trivial primitives to base objects. We prove that in a disjoint-access parallel STM implementation with invisible read-only transactions, some read-only transaction will not terminate successfully in a finite number of steps; this is formally stated in Theorem 4.

Specifically, we construct an infinite execution of a readonly transaction. This execution consists of a single readonly transaction with one complete update transaction between any pair of consecutive steps by the read-only transaction; an update is a transaction with a singleton write set and an empty read set. We first define a special (finite) execution of this form, called flippable, and show that such a read-only transaction cannot terminate successfully. Then we show how a flippable execution can be repeatedly extended to construct successively longer flippable executions.

An execution is called flippable since there are two similar executions in which we flip the position of two update transactions and one of the executions is indistinguishable from the original execution. One type of flipped execution is called a forward flip since it moves an update transaction forward in the execution, while other is called a backward flip since it defers the execution of an update transaction. Formally: by processes p0, . . . , pt-1 executing update transactions and process q executing a read-only transaction, which reads and returns the value of t data items ı0 . . . ıt-1. The execution E k satisfies all the following conditions:

Definition 2. A flippable execution of length k with t updaters is a finite execution E k = U0s1U1 . . . s k U k executed q : s1 . . . s l-1 s l . . . s k p0 : U0 . . . U l-1 . . . U k p1 : U1 . . . U l . . . (a) E k . q : s1 . . . s l-1 s l . . . s k p0 : U0 . . . U l-1 . . . U k p1 : U1 . . . U l . . . (b) Forward flip: U l is performed before U l-1 s l . q : s1 . . . s l-1 s l . . . s k p0 : U0 . . . U l-1 . . . U k p1 : U1 . . . U l . . . (c) Backward flip: U l-1 is performed after s l U l .
1. for j = 1, . . . , k, sj is a single step by q, 2. for j = 0, . . . , k, Uj is a solo execution of a complete update transaction, in which process p h ∈ {p0, . . . , pt-1}, writes j + 1 to the data item ı h 3. consecutive updates are executed by different processes, and 4. for any l, 0 < l ≤ k, the execution

E k = U0s1U1 . . . s l-1 U l-1 s l U l . . . s k U k
is indistinguishable to all processes from one of the following executions: This definition, and the structure of our proof, is similar to the lower bound of Attiya, Ellen and Fatourou [START_REF] Attiya | The complexity of updating multi-writer snapshot objects[END_REF] on the step complexity of update operations in implementations of atomic snapshot objects. The main difference is that our definition of a flippable execution has two types of flipped executions, and t processes executing update transactions instead of just two.

← - F l = U0s1U1 . . . s l-1 U l U l-1 s l . . . s k U k in which the update transaction U l is executed before U l-1 s l instead of after U l-1 s l ( forward flip) or - → F l = U0s1U1 . . . s l-1 s l U l U l-1 . . . s k U k in which the update transaction U l-1 is executed after s l U l instead of before s l U l ( backward flip).
The next lemma is proved by arguments similar to those applied in [START_REF] Attiya | The complexity of updating multi-writer snapshot objects[END_REF], extended to handle the possibility of two kinds of flips (forward and backward).

Lemma 1. The read-only transaction in a flippable execution does not terminate successfully.

Proof. Let E k = U0s1U1 . . . s k U k be a flippable execution. Assume, towards a contradiction, that q successfully terminates its read-only transaction in E k , with a result v = (v0, . . . , vt-1). Since the update transactions in the execution E k do not overlap, they must be serialized in the order U0, . . . , U l . Since all steps of the read-only transaction by q are after U0 and before U k , it has a unique serialization point between U l-1 and U l , for some l, 1 ≤ l ≤ k. Let ı h be the item written by U l-1 , and recall that U l-1 writes l to ı h ; hence v h = l.

The execution E k is indistinguishable to process q from F l , which is either the forward flip ← -

F l = U0s1U1 . . . s l-1 U l U l-1 s l s l+1 . . . U k in which update U l is executed before U l-1 s l instead of after U l-1 s l ; or the backward flip -→ F l = U0s1U1 . . . s l-1 s l U l U l-1 s l+1 . . . U k in which update U l-1 is executed after s l U l instead of before s l U l .
Hence, the read-only transaction executed by q in F l returns the same result, v, as in E k . Since the update transactions do not overlap in F l , they are serialized in the order U0, . . . , U l , U l-1 , . . . , U k , that is, the same as for E k , except that U l-1 and U l are flipped. Since two consecutive update transactions are on different items, the values of {ı0, . . . , ıt-1} are the same after both update transactions have been executed, no matter which has been executed first. Hence, at all points in the serialization of F l , except between U l and U l-1 , the value of all items {ı0, . . . , ıt-1} is the same as its value in the corresponding points in the serialization of E k . Thus, the read-only transaction of q can only serialized after U l and before U l-1 in F l . However, since U l-1 is the first write of l to ı h , the value of ı h is not l before U l-1 , and hence, the read-only transaction executed by q cannot be serialized between U l and : : ... U l-1 . This contradicts the assumption that the read-only transaction terminates successfully.

U jh p h ′ p h α h U j h ′ φ h ′ φ h α h ′ (a)
α h p h ′ p h φ h α h ′ φ h ′ (b) Overlapping execution of U j h and U j h ′ from configura- tion C
Lemma 3 (below) proves that when read-only transactions are invisible, we can inductively construct a flippable execution. The crux of this lemma is quite different from [START_REF] Attiya | The complexity of updating multi-writer snapshot objects[END_REF], as it relies on weakly disjoint-access parallelism. A critical step in the proof is provided by the next lemma, showing that in a weakly disjoint-access parallel STM, two consecutive updates by different processes on different items cannot contend on the same base objects.The proof of the lemma shows that two such consecutive updates can be perturbed to concurrently contend on the same base object.

Lemma 2. Given a weakly disjoint-access parallel STM implementation and a quiescent configuration C, consider the consecutive execution of two update transactions U j h U j h ′ , executed by a process p h on an item ı h and by process p h ′ on an item ı h ′ , h = h ′ , respectively, from C. Then p h and p h ′ do not contend on the same base object when executing Uj h and U j h ′ .

Proof. Assume, towards a contradiction, that p h and p h ′ contend on a base object when executing Uj h Uj h ′ from a quiescent configuration C. If in U j h , p h applies a nontrivial primitive to a base object on which they contend, let φ h be the last event in U j h in which p h applies such a primitive, say, to base object o. Let φ h ′ be the first event in Uj h ′ that accesses o. Otherwise, p h only applies trivial primitives in U j h to base objects on which it contends with p h ′ in U j h ′ ; let φ h ′ be the first event in U j h ′ in which p h ′ applies a non-trivial primitive to some base object, say, o, on which they contend. Let φ h be the last event of p h in Uj h that accesses o. In both cases, denote by α h φ h the prefix of the execution of U h from C and by α h ′ φ h ′ the prefix of the execution of U h ′ after U h (see Figure 3(a)).

We now consider an overlapping execution of the update transactions Uj h and Uj h ′ , by processes p h and p h ′ , from C. We argue that p h and p h ′ perform the same steps up to the events φ h and φ h ′ , and as shown in Figure 3(b), p h and p h ′ concurrently contend on base object o.

In more detail, consider the execution α h α h ′ from C, in which p h executes Uj h until it is about to perform φ h , and then p h ′ executes U j h ′ until it is about to perform φ h ′ . Clearly, p h is about to perform φ h also after α h α h ′ . By construction, the execution interval α h α h ′ from C is indistinguishable to p h ′ from the execution interval U j h α h ′ from C. Hence, p h ′ is about to perform the event φ h ′ also after α h α h ′ , that is, p h ′ and p h concurrently contend on o. However, the conflict graph of the execution interval α h α h ′ φ h ′ φ h does not contain a path between the data sets of U j h and U j h ′ , contradicting the assumption that the implementation is weakly disjoint-access parallel.

Since two consecutive updates do not contend on the same base object, we can construct an execution where either the previous update is deferred or the next update is moved forward in the execution without affecting the single step of the read-only transaction in between them. This allows us to inductively construct a flippable execution, in the proof of the next lemma. Lemma 3. For every k ≥ 0, every weakly disjoint-access parallel implementation of an STM with invisible read-only transactions, has a flippable execution E k = U 0 s 1 U 1 s 2 . . . U k with two updaters p 0 and p 1 , which is indistinguishable to p 0 and p 1 from the execution E ′ k = U 0 U 1 . . . U k in which only p0 and p1 take steps.

Proof. The proof is by induction on the length k of the flippable execution E k executed by a process q and two updaters p 0 and p 1 on two items {ı 0 , ı 1 }. In the base case, k = 0, the lemma holds with a solo execution of U0, an update transaction by p0 that writes 1 to ı0. U0 successfully terminates since it runs solo from a quiescent configuration.

For the induction step, consider a flippable execution of length k, E k = U 0 s 1 U 1 s 2 . . . U k . By Lemma 1, the read-only transaction does not terminate successfully in E k . Let s k+1 be the next step by q. Assume U k is executed by p h ′ and let h = 1h ′ ; note that h = h ′ . Let E k+1 = E k s k+1 U k+1 , where process p h writes k + 2 to ı h in the update transaction U k+1 . Note that U k+1 terminates successfully, by our progress condition; although the configuration at the end of E k+1 = E k s k+1 is not quiescent, it is indistinguishable from the quiescent configuration at the end of E ′ k . Since the read-only transaction by q is invisible, E k+1 is indistinguishable to p 0 and p 1 from the execution E ′ k U k+1 . It remains to prove that for every l, 0 < l ≤ k + 1, the execution E k+1 is indistinguishable to all processes from either ← -F l or -→ F l . For every l, 0 < l ≤ k, by the inductive assumption, the execution

E k = U 0 s 1 U 1 . . . s l-1 U l-1 s l U l . . . s k U k is indistinguishable to all processes from the flipped execu- tion F l which is either ← - F l = U0s1U1 . . . s l-1 U l U l-1 s l . . . U k or - → F l = U0s1U1 . . . s l-1 s l U l U l-1 . . . s k U k .
In particular, the configurations at the end of the two executions E k and F l are the same. Hence, E k+1 = E k s k+1 U k+1 and F l s k+1 U k+1 are indistinguishable to all processes.

To prove the condition for l = k + 1, let C ′ k-1 be the configuration at the end of E ′ k-1 ; C ′ k-1 is quiescent, and Lemma 2 implies that p h ′ and p h do not contend on the same base object when executing U k followed by The impossibility result follows from Lemmas 1 and 3.

U k+1 from C ′ k-1 ,
Theorem 4. There is no weakly disjoint-access parallel implementation with invisible read-only transactions of a strictly serializable STM, in which read-only transactions always terminate successfully.

The impossibility result stated in Theorem 4 holds also for opaque STMs [START_REF] Guerraoui | On the correctness of transactional memory[END_REF], since opacity implies strict serializability.

Lower Bound for Read-Only Transactions

The technique of the previous section can be extended to prove that a read-only transaction of t items in a disjointaccess parallel STM implementation, which successfully terminates in a finite number of steps, must apply non-trivial primitives to t -1 base objects; this assumes that there are at least t + 1 processes.

The proof of Lemma 1-showing that the read-only transaction in a flippable execution cannot terminate successfullydoes not rely on the fact that the read-only transaction is invisible, and the lemma continues to hold. On the other hand, we must modify the proof showing the existence of the flippable execution.

This result relies on a stronger notion of disjoint-access parallelism, which requires two transactions to be connected (in the conflict graph) even if they both just apply a trivial primitive to the same base object. (This is the definition in [START_REF] Israeli | Disjoint-access-parallel implementations of strong shared memory primitives[END_REF].) Two processes concurrently access a base object o if both have a pending access to o at some configuration. Definition 3. An STM implementation is disjoint-access parallel if two processes p1, p2 concurrently access the same base object when executing transactions T1 and T2, respectively, only if T1 and T2 are not disjoint-access.

Since we now put a stronger requirement on disjoint-access parallel STM implementations, Lemma 2, assuming a weaker requirement, still holds.

We first show (in Lemma 5) that, in a disjoint-access parallel STM implementation, two update transactions executed by different processes on different items do not access a common base object when each of them runs solo from a quiescent configuration. This is used in Lemma 6 to prove the existence of a flippable execution, when a read-only transaction of t data items applies non-trivial primitives to at most t -2 base objects.

α h p h : U jh φ h (a) Solo execution of Uj h from configuration C U j h ′ p h ′ : α h ′ φ h ′ (b) Solo execution of U j h ′ from configuration C ... ... p h : α h p h ′ : α h ′ φ h φ h ′ (c) Overlapping execution of U j h and U j h ′ from configura- tion C
Figure 4: Illustration for the proof of Lemma 5.

Lemma 5. Given a disjoint-access parallel STM implementation and a quiescent configuration C, consider the execution of an update transaction U j h to the item ı h by process p h , and an update transaction Uj h ′ to the item ı h ′ by process p h ′ , h = h ′ , from C. Then, p h and p h ′ do not access a common base object when executing U j h and U j h ′ , respectively.

Proof. Assume, towards a contradiction, that p h and p h ′ access the same base object while executing U j h and U j h ′ , respectively, from C. Let o be the first base object accessed by p h that is also accessed by p h ′ . Let α h φ h be the prefix of the execution of U j h from C, where φ h is the first event in which p h accesses o (see Figure 4(a)). Let α h ′ φ h ′ be the prefix of the execution of U j h ′ from C, where φ h ′ is the first access of p h ′ to o (see Figure 4(b)).

Consider the execution α h α h ′ from C, where p h executes U j h until it is about to access o, and then p h ′ executes U j h ′ until it is about to access o (see Figure 4(c)). By construction, the execution α h α h ′ from C is indistinguishable to p h and p h ′ from the corresponding executions α h and α h ′ from C. Thus, p h ′ has the event φ h ′ pending and p h has the event φ h pending after α h α h ′ ; thus, p h ′ and p h have concurrently pending accesses to o. However, in the conflict graph of the execution interval α h α h ′ φ h ′ φ h from C, there is no path between the data sets of Uj h and Uj h ′ , contradicting the assumption that the implementation is disjoint-access parallel.

We show that at any point during the execution of the read-only transaction, there is a process that can write to its item without accessing any base object to which q applies non-trivial primitives, thus making the read-only transaction "invisible" to the other processes. Note that, by the definition of a flippable execution, each process always updates the same item. We prove such a process exists by applying a "pigeon hole" argument to show that the process does not access any base object to which the read-only transaction applies non-trivial primitives. Since there are t -1 processes to choose from, each accessing a different item, and since the read-only transaction applies non-trivial primitives to at most t-2 base objects, at least two update transactions by different processes access the same base object, which can be shown to violate disjoint-access parallelism. Lemma 6. For every k ≥ 0, a disjoint-access parallel implementation of an STM in which a read-only transaction of t data items applies non-trivial primitives to at most t -2 base objects, has a flippable execution E k = U0s1U1s2 . . . U k with t updaters, which is indistinguishable to p0, . . . , pt-1 from the execution E ′ k = U0U1 . . . U k in which only p0, . . . , pt-1 take steps.

Proof. The proof is by induction on the length k of the flippable execution E k . The base case is when k = 0. The lemma holds with a solo execution of an update transaction, U0, by process p0 that writes 1 to ı1. U0 successfully terminates since it runs solo from a quiescent configuration.

For the induction step, consider a flippable execution of length k, E k = U0s1U1s2 . . . U k , which is indistinguishable to p0, . . . , pt-1 from the execution E ′ k = U0U1 . . . U k . By Lemma 1, the read-only transaction does not terminate successfully in E k . Let s k+1 be the next step by q and let C k+1 denote the configuration at the end of E k s k+1 ; also, let C ′ k+1 be the configuration at the end of E ′ k . The process p h to execute U k+1 is chosen from p0, . . . , pt-1 such that p h did not execute U k and a solo execution of U k+1 from C k+1 by p h does not access any base objects to which q applies non-trivial primitives in E k s k+1 . Note that this transaction must terminate successfully, by our progress condition; although C k+1 is not quiescent, it is indistinguishable from C ′ k+1 , which is quiescent. We claim such a process exists. Assume, towards a contradiction, that for every process p h k+1 , h k+1 = h k , the solo execution by p h k+1 from C k+1 of the update transaction that writes k+2 to ı h k+1 accesses a base object to which q applies a non-trivial primitive in E k s k+1 . We consider t -1 possible processes, each writing to a different item. Since the readonly transaction applies non-trivial primitives to at most t -2 base objects, at least two update transactions executed by different processes p h and p h ′ to different items ı h and ı h ′ , starting from configuration C k+1 , access the same base object in their first access to a base object to which q applies a non-trivial primitive. Recall that C ′ k+1 is quiescent. Since the execution E k s k+1 is indistinguishable to processes p h and p h ′ from the execution E ′ k , they access the same base object also when executing the update transactions from C ′ k+1 , which by Lemma 5, violates the assumption that the implementation is disjoint-access parallel.

Pick some process p h k+1 , h k+1 = h k , that does not access any base objects to which q applies non-trivial primitives in E k s k+1 ; let U k+1 be an update by p h k+1 that writes k + 2 to ı h k+1 and denote

E k+1 = E k s k+1 U k+1 .
Next, we prove that the execution E k+1 is indistinguishable to p0, . . . , pt-1 from the execution E ′ k+1 . This holds for processes other than p h k+1 by the inductive assumption and since these processes take no steps in the suffix of this execution. For p h k+1 , this holds by the inductive assumption and since the solo execution U k+1 of an update transaction by p h k+1 does not access base objects to which q applies a non-trivial primitive in E k s k+1 .

It remains to prove that for every l, 0 < l ≤ k + 1, the execution E k+1 is indistinguishable to all processes from the flipped execution F l which is either ← -F l or -→ F l , as defined in Definition 2. For every l, 0 < l ≤ k, by the inductive assumption, the execution

E k = U0s1U1 . . . s l-1 U l-1 s l U l . . . s k U k is indistinguishable to all processes from the flipped execu- tion F l which is either ← - F l = U0s1U1 . . . s l-1 U l U l-1 s l . . . U k or - → F l = U0s1U1 . . . s l-1 s l U l U l-1 . . . s k U k .
In particular, the configurations at the end of the two executions E k and F l are the same. Hence, the executions E k+1 = E k s k+1 U k+1 and F l s k+1 U k+1 are indistinguishable to all processes. For l = k + 1, consider the flipped executions ← -F k+1 and -→ F k+1 . The configuration C ′ k-1 at the end of E ′ k-1 is quiescent. Any STM implementation which is disjoint-access parallel is also weakly disjoint-access parallel, hence we can apply Lemma 2 to deduce that p h k and p h k+1 do not contend on, and hence do not access the same base object while executing U k and U k+1 from C ′ k-1 . The indistinguishability property implies that p h k and p h k+1 do not access the same base object while executing U k and U k+1 also in E k+1 .

Moreover, if q applies a trivial primitive to some base object o in s k+1 , then either at least one of the two processes p h k+1 and p h k does not access o in U k+1 and in U k respectively, or they both apply a trivial primitive to o. In the former case, if p h k+1 does not access in U k+1 any object that q accesses in s k+1 , then

← - E k+1 = U0s1U1 . . . s k U k+1 U k s k+1
is indistinguishable to all processes from E k+1 , while if p h k does not access in U k any object that q accesses in s k+1 , then

- → E k+1 = U0s1U1 . . . s k s k+1 U k+1 U k
is indistinguishable to all processes from E k+1 . If p h k+1 and p h k apply a trivial primitive to o, then both flipped executions are indistinguishable to all processes from E k+1 .

The lower bound follows:

Theorem 7. In a strict serializable disjoint-access parallel STM implementation for t + 1 processes, where all readonly transactions terminate successfully, some read-only transaction of t ≥ 2 data items applies non-trivial primitives to at least t -1 base objects. This lower bound holds also for opaque STMs, since opacity implies strict serializability.

EXTENDING THE RESULTS TO WEAKER CONSISTENCY CONDITIONS

In this section, we show that both Theorem 4 and Theorem 7 hold for weaker consistency conditions, namely, serializability and snapshot isolation. This uses an additional process.

Recall that an STM is serializable if transactions appear to execute sequentially, one after the other; we further require that transactions of the same process preserve their order (per-process order).

Given a flippable execution E k = U0s1U1 . . . s k U k , we construct an augmented flippable execution

b E k = U0s1S * 1 U1 . . . s k S * k U k
, where an additional process q ′ performs invisible read-only transactions. For every j ∈ {1, . . . , k}, q ′ performs solo a q : sequence S * j of read-only transactions after the event sj by process q and before the update Uj. Each read-only transaction in S * j accesses the items ı f j-1 and ı f j updated by Uj-1 and Uj. The result of the last read-only transaction in the sequence S * j , denoted Sj, is the value written by Uj-1 to ı f j-1 and the last value of ı f j before Uj updates it.

s1 . . . s l-1 s l . . . s k p0 : U0 . . . U l-1 . . . U k p1 : U1 . . . U l . . . q ′ : S *
Figure 5 shows the augmented flippable execution obtained by augmenting the flippable execution E k of Figure 2 with sequences of read-only transactions performed by an additional process q ′ . We apply the per-process ordering of transactions to prove that the read-only transactions of q ′ must eventually read the latest value written in Uj-1, and thus, S * j is finite.

Lemma 8. Consider an augmented flippable execution of length k ≥ 0, b

E k = U0s1S * 1 U1 . . . s k S * k U k .
In any serialization of b E k that preserves the per-process order, U0, U1, . . . , U k appear in their order of execution.

Proof. We show, by induction on ℓ, that U0, U1, . . . , U ℓ appear in their order of execution. The base case is trivial.

For the induction step, consider U ℓ+1 . By the induction assumption, the updates U0, U1, . . . , U ℓ are serialized by their execution order in b E k . By construction S * ℓ+1 accesses the items ı f ℓ and ı f ℓ+1 repeatedly up to a read-only transaction S ℓ+1 , which returns the value written by U ℓ and the last value of ı f ℓ+1 before the one written by U ℓ+1 .

S * ℓ+1 is finite since the STM is serializable and so, eventually, some transaction must return the latest values written to ı f ℓ and ı f ℓ+1 , and by the induction assumption, U ℓ is the last to write to ı f ℓ . Moreover, S ℓ+1 completes before U ℓ+1 starts, so it cannot return the value written by U ℓ+1 , since due to serializability, a read operation can not return a value not written.

Since each data item is written by a different process, and due to per-process order, U ℓ+1 can not be serialized before the last update of ı f ℓ+1 preceding U ℓ+1 .

Moreover, U ℓ+1 can not be serialized after this update and before S ℓ+1 , since S ℓ+1 does not return the value written by U ℓ+1 . Hence, U ℓ+1 is serialized after S ℓ+1 .

We use Lemma 8 to prove the analogue of Lemma 1.

Lemma 9. Consider an augmented flippable execution of length k ≥ 0 with t updaters, b

E k = U0s1S * 1 U1 . . . s k S * k U k .
If the read-only transactions by process q ′ are invisible, then the read-only transaction by process q does not terminate successfully.

Proof. Assume, towards a contradiction, that the readonly transaction of process q in b E k terminates successfully and returns a value v = (v0, . . . , vt-1), which does not violate serializability. Let the augmented flippable execution b

E k = U0s1S * 1 U1 . . . s k S * k U k correspond to a flippable execu- tion E k = U0s1U1 . . . s k U k .
By Lemma 8, the updates in b E k are serialized in the order U0, U1, . . . , U k . The value v determines where q's read-only transaction is serialized. In particular, for some l, 0 < l ≤ k, the read-only transaction of q is serialized after U l-1 and before U l , and for each item ı f in {ı0 . . . ıt-1}, either v f is zero and no update wrote to ı f before U l , or the last update to ı f before U l wrote v f to ı f . Let S be the serialization of execution b E k . Since the read-only transactions executed by process q ′ are invisible, b

E k and E k are indistinguishable to p0, . . . , pt-1 and q. Thus, they will execute the same steps in both executions. Note that S is a serialization also for E k . Since S preserves the real-time order among transactions, E k is a flippable execution where the read-only transaction terminates and strict serializability is preserved, contradicting Lemma 1.

As discussed before the lemma, the existence of a flippable execution (guaranteed by Lemma 3) implies there is an augmented flippable execution, and hence, Lemma 9 implies the following impossibility result: Theorem 10. There is no weakly disjoint-access parallel STM implementation with invisible read-only transactions of a serializable STM, in which read-only transactions always terminate successfully.

When a read-only transaction of t ≥ 2 data items applies non-trivial primitives to at most t-2 base objects, the readonly transactions of q ′ in the augmented flippable execution are, in fact, invisible since their read set contains only two data items. As discussed before Lemma 9, the existence of a flippable execution (guaranteed by Lemma 6) implies there is an augmented flippable execution, and hence, Lemma 9 implies the following lower bound: Theorem 11. In a serializable disjoint-access parallel STM implementation for t+2 processes, where all read-only transactions terminate successfully, some read-only transaction of t ≥ 2 data items applies non-trivial primitives to at least t-1 base objects.

Snapshot isolation [START_REF] Lu | Correct execution of transactions at different isolation levels[END_REF][START_REF] Riegel | Snapshot isolation for software transactional memory[END_REF][START_REF] Weikum | Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery[END_REF] decouples the consistency of the reads and the writes, and guarantees a snapshot of the read set not older than the start of the transaction. The proof can be adapted to hold also when the consistency condition of the STM is snapshot isolation.

RELATED WORK

Many STM implementations are centralized; in particular, to determine a unique commit timestamp for transactions, the Lazy Snapshot Algorithm (LSA) [START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF] relies on a single shared monotonically increasing counter, while Transactional Locking II (TL2) [START_REF] Dice | Transactional locking II[END_REF] relies on a global clock. Both approaches introduce a single hot-spot accessed by all transactions, regardless of their data sets, and are therefore not disjoint-access parallel.

More recently, two STM implementations without a centralized hot-spot have been proposed. Avni and Shavit [START_REF] Avni | Maintaining consistent transactional states without a global clock[END_REF] present a thread-local clock mechanism that provides a decentralized solution for maintaining a consistent view. The key idea is using Lamport clock (scalar causal timestamps) instead of the real-time global clock. Integrated with TL2, this mechanism provides an STM supporting invisible readonly transactions, without a centralized contention point. A drawback of this algorithm is that transactions that terminated long before the current one may cause it to fail since the timestamp recorded for them is not current enough. Thus, read-only transactions are not wait-free. Imbs and Raynal [START_REF] Imbs | A lock-based protocol for software transactional memory[END_REF] propose an opaque lock-based STM with no centralized hot-spot but their solution has visible reads.

Guerraoui and Kapalka [START_REF] Guerraoui | On obstruction-free transactions[END_REF] prove that obstruction-free implementations of software transactional memory cannot ensure strict disjoint-access parallelism. This property requires transactions with disjoint data sets not to access a common base object. This notion is stronger than the one originally proposed by Israeli and Rappoport [START_REF] Israeli | Disjoint-access-parallel implementations of strong shared memory primitives[END_REF], and commonly used in the literature [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF], where two transactions with disjoint data sets are allowed to access the same base objects, provided they are connected via other transactions. All other transactions have to progress in parallel, even if they are concurrent. Their definition of strict disjoint-access parallelism, like our first definition (Definition 1), allows concurrent reads to the same base objects even by transactions that are not connected in the conflict graph.

Our lower bound applies to the notion of disjoint-access parallelism as originally defined in [START_REF] Israeli | Disjoint-access-parallel implementations of strong shared memory primitives[END_REF]. In contrast, the result of [START_REF] Guerraoui | On obstruction-free transactions[END_REF] does not hold for this weaker notion. Indeed, Herlihy et al. [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF] present an obstruction-free and disjoint-access parallel STM. Obstruction-freedom does not prevent interfering concurrent processes from starving each other and thus, the implementation presented in [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF] does not guarantee that a read-only transaction eventually terminates successfully.

Elsewhere, Guerraoui and Kapalka [START_REF] Guerraoui | On the correctness of transactional memory[END_REF] prove a lower bound on the number of steps a process takes to successfully terminate a transaction, for every implementation that uses invisible reads, is single-version, and never aborts a transaction unless it conflicts with another live transaction. Our lower bound allows multi-version implementations, but requires read-only transactions to terminate successfully, regardless of overlapping transactions.

Serializability provides a weaker guarantee on the ordering of transactions (it does not have to respect the real-time order of non-overlapping ones). Nevertheless, our impossibility results hold also for serializable STMs that preserve the per-process order. Indeed, none of the serializable STM implementations presented in the literature, e.g. [START_REF] Aydonat | Serializability of transactions in software transactional memory[END_REF][START_REF] Gramoli | Towards a theory of input acceptance for transactional memories[END_REF][START_REF] Napper | Lock-free serializable transactions[END_REF][START_REF] Riegel | From causal to z-linearizable transactional memory[END_REF], provides disjoint-access parallelism and wait-free, invisible read-only transactions. In fact, the impossibility results hold also for STMs that satisfy the even weaker condition of snapshot isolation known from the database literature [START_REF] Lu | Correct execution of transactions at different isolation levels[END_REF][START_REF] Weikum | Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery[END_REF] and suggested as an efficient alternative to serializability for STMs [START_REF] Riegel | Snapshot isolation for software transactional memory[END_REF].

Riegel et al. [START_REF] Riegel | From causal to z-linearizable transactional memory[END_REF] proposed an STM implementation that supports invisible reads and is disjoint-access parallel, but it provides only causal serializability; moreover, read-only transactions may abort infinitely many times. Causal serializability is weaker than serializability since it allows different processes to have a different view of the system. This leaves open the question of whether our results holds for causally serializable STMs, or whether the algorithm of [START_REF] Riegel | From causal to z-linearizable transactional memory[END_REF] can be extended to have wait-free read-only transactions.

A read-only transaction can be considered as a partial scan operation [START_REF] Attiya | Partial snapshot objects[END_REF]: a partial snapshot objects is an atomic snapshot object [START_REF] Afek | Atomic snapshots of shared memory[END_REF], where processes can scan any subset of the components. In the wait-free algorithm for partial snapshot objects [START_REF] Attiya | Partial snapshot objects[END_REF], scanners announce which components they are currently attempting to scan, i.e., read-only transactions are visible.

Our proof techniques draw ideas from the lower bounds on the step complexity of update operations in snapshot objects. Israeli and Shirazi [START_REF] Israeli | The time complexity of updating snapshot memories[END_REF] prove an Ω(m) lower bound on the number of steps to update a component in an mcomponent single-writer snapshot objects, implemented from single-writer registers. Attiya, Ellen and Fatourou [START_REF] Attiya | The complexity of updating multi-writer snapshot objects[END_REF] extend this lower bound to implementations of m-component multi-writer objects from base objects of any type.

DISCUSSION

This paper shows that no transactional memory implementation can be disjoint-access parallel and have invisible, wait-free read-only transactions. There are implementations that are disjoint-access parallel and have invisible but not wait-free read-only transactions [START_REF] Avni | Maintaining consistent transactional states without a global clock[END_REF][START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF], while others have invisible, wait-free read-only transactions but are not disjointaccess parallel [START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF]. In principle, the invisibility of read-only transactions can also be sacrificed in order to keep them wait-free, and the implementation disjoint-access parallel. This can be done by treating the read set together with the write set and adapting a dynamic disjoint-access parallel implementation of multi-location synchronization operator, e.g., [START_REF] Harris | A practical multi-word compare-and-swap operation[END_REF]. (This algorithm is not wait-free, but it seems that it can be made wait-free without sacrificing the other properties.) Thus, each of the assumptions made in our impossibility result is necessary, since removing either of them admits an implementation with the two remaining properties.

Our work joins recent efforts to explore the boundaries of STM implementations, so as to guide algorithm designers in their attempt to find better and more efficient implementations. Such boundaries demonstrate which directions are futile and which might lead to performance gains. It would be interesting to derive additional quantitative results on the complexity of transactions, and in particular, read-only transactions.

Our proof shows that the read-only transaction cannot terminate successfully, but it is possible to terminate it unsuccessfully, by aborting it; however, this abort is not justified by data conflicts. Moreover, when the read-only transaction is retried, it is possible to continue the construction and force it to abort again. An implementation is permissive with respect to a safety property [START_REF] Guerraoui | Permissiveness in transactional memories[END_REF] if it never aborts a transaction unless necessary for ensuring correctness. Our proof shows that a disjoint-access parallel implementation with invisible read-only transactions that always terminate-however, not always successfully-is not permissive with respect to opacity, strict serializability, serializability or snapshot isolation. We would like to further investigate the connections between our results and the study of unnecessary aborts [START_REF] Gramoli | Towards a theory of input acceptance for transactional memories[END_REF][START_REF] Guerraoui | Permissiveness in transactional memories[END_REF] or wasted work in STM implementations.

Figure 2 :

 2 Figure 2: A flippable execution of length k with two updaters: Figure 2(a) shows a flippable execution E k ; Figure 2(b) shows the forward flip execution of E k, where the update transaction U l by process p1 is executed before the update transaction U l-1 by process p0 and before the step s l of the read-only transaction; Figure2(c)shows the backward flip execution of E k , where the update U l-1 by process p0 is deferred after the update transaction U l by process p1 and after the step s l of the read-only transaction.

Figures 2 (

 2 Figures 2(b) and 2(c) present the forward and the backward flips of the execution in Figure 2(a).This definition, and the structure of our proof, is similar to the lower bound of Attiya, Ellen and Fatourou[START_REF] Attiya | The complexity of updating multi-writer snapshot objects[END_REF] on the step complexity of update operations in implementations of atomic snapshot objects. The main difference is that our definition of a flippable execution has two types of flipped executions, and t processes executing update transactions instead of just two.The next lemma is proved by arguments similar to those applied in[START_REF] Attiya | The complexity of updating multi-writer snapshot objects[END_REF], extended to handle the possibility of two kinds of flips (forward and backward).

  Serial execution of Uj h and Uj h ′ from configuration C ... : :

Figure 3 :

 3 Figure 3: Illustration for the proof of Lemma 2

Figure 5 :

 5 Figure 5: An augmented flippable execution b E k derived from the flippable execution E k of Figure 2.

  namely, in the suffix of E ′ k+1 . By the indistinguishability of E ′ k+1 and E k+1 , p h ′ and p h do not contend on the same base object while executing U k and U k+1 also in the execution E k+1 . Moreover, if q accesses a base object o in s k+1 , then either at least one of the two processes p h or p h ′ does not access o in U k+1 or U k , respectively, or they both apply a trivial primitive to o. In the former case, if p h does not access o in U k+1 then ← -F k+1 = U0s1U1 . . . s k U k+1 U k s k+1 is indistinguishable to all processes from E k+1 , while if p h ′ does not access o in U k , then -→ F k+1 = U0s1U1 . . . s k s k+1 U k+1 U k is indistinguishable to all processes from E k+1 . If both p h and p h ′ apply a trivial primitive to o, then both flipped ex-

	ecutions,	← -F k+1 and	-→ F k+1 , are indistinguishable to all pro-
	cesses from E k+1 .

Acknowledgements. We would like to thank Rachid Guerraoui, Michal Kapalka and Martin Vechev for helpful comments.

* This research is partially supported by the Israel Science Foundation (grant number 953/06) and Intel Corporation. † Supported in part by a scholarship from the Israel Ministry of Science. ‡ On leave from Sapienza, Universitá di Roma, Dipartimento di Informatica e Sistemistica, "Antonio Ruberti"; supported in part by a fellowship from the Lady Davis Foundation and by a grant MUR, FIRB Italia-Israele RBIN047MH9


Hagit Attiya

Vincent Gramoli

Alessia Milani

A Provably Starvation-Free Distributed Directory Protocol ⋆

This paper presents Combine, a distributed directory protocol for shared objects, designed for large-scale distributed systems. Directory protocols support move requests, allowing to write the object locally, as well as lookup requests, providing a read-only copy of the object. They have been used in distributed shared memory implementations and in data-flow implementations of distributed software transactional memory in large-scale systems. The protocol runs on an overlay tree, whose leaves are the nodes of the system; it ensures that the cost of serving a request is proportional to the cost of the shortest path between the requesting node and the serving node, in the overlay tree. The correctness of the protocol, including starvation freedom, is proved, despite asynchrony and concurrent requests. The protocol avoids race conditions by combining requests that overtake each other as they pass through the same node. Using an overlay tree with a good stretch factor yields an efficient protocol, even when requests are concurrent.

Introduction

Distributed applications in large-scale systems aim for good scalability, offering proportionally better performance as the number of processing nodes increases, by exploiting communication to access nearby data [START_REF] Nussbaum | Scalability of parallel machines[END_REF].

An important example is provided by a directory-based consistency protocol [START_REF] Chaiken | Directory-based cache coherence in large-scale multiprocessors[END_REF]; in such a protocol, a directory helps to maintain the coherence of objects among entities sharing them. To access an object, a processor uses the directory to obtain a copy; when the object changes, the directory either updates or invalidates the other copies. In a large-scale system, the directory manages copies of an object, through a communication mechanism supporting the following operations: A writable copy of the object is obtained with a move request, and a read-only copy of the object is obtained with a lookup request.

A directory-based consistency protocol is better tailored for large-scale distributed systems, in which remote accesses require expensive communication, several orders of magnitude slower than local ones. Reducing the cost of communication with the objects and the number of remote operations is crucial for achieving good performance in distributed shared memory and transactional memory implementations. Several directory protocols for maintaining consistency have been presented in the literature, e.g., [START_REF] Agarwal | The MIT Alewife machine: A large-scale distributed-memory multiprocessor[END_REF][START_REF] Censier | A new solution to coherence problems in multicache systems[END_REF][START_REF] Chaiken | Directory-based cache coherence in large-scale multiprocessors[END_REF][START_REF] Demmer | The Arrow directory protocol[END_REF]. (They are discussed in Section 6.)

In large-scale systems, where the communication cost dominates the latency, directory protocols must order the potentially large number of requests that are contending for the same object. Rather than channeling all requests to the current location of the object, some directory protocols, e.g., [START_REF] Demmer | The Arrow directory protocol[END_REF], implement a distributed queue, where a request from p gets enqueued until the object gets acquired and released by some predecessor q, a node that p detects as having requested the object before. This paper presents Combine, a new directory protocol based on a distributed queue, which efficiently accommodates concurrent requests for the same object, and non-fifo message delivery. Combine is particularly suited for systems in which the cost of communication is not uniform, that is, some nodes are "closer" than others. Scalability in Combine is achieved by communicating on an overlay tree and ensuring that the cost of performing a lookup or a move is therefore proportional to the cost of the shortest path between the requesting node and the serving node (its predecessor), in the overlay tree. The simplicity of the overlay tree, and in particular, the fact that the object is held only by leaf nodes, facilitates the proof that a node finds a previous node holding the object.

To state the communication cost more precisely, we assume that every pair of nodes can communicate, and that the cost of communication between pairs of nodes forms a metric, that is, there is a symmetric positive distance between nodes, denoted by δ(., .), which satisfies the triangle inequality. The stretch of a tree is the worst case ratio between the cost of direct communication between two nodes p and q in the network, that is, δ(p, q), and the cost of communicating along the shortest tree path between p and q.

The communication cost of Combine is proportional to the cost of the shortest path between the requesting node and the serving node, times the stretch of the overlay tree. Thus, the communication cost improves as the stretch of the overlay tree decreases. Specifically, the cost of a lookup request by node q that is served by node p is proportional to the cost of the shortest tree path between p and q, that is, to δ(p, q) times the stretch of the tree. The cost of a move request by node p is the same, with q being the node that will pass the object to p.

When communication is asynchronous and requests are concurrent, however, bounding the communication cost does not ensure that a request is eventually served (starvation-freedom). It remains to show that while p is waiting for the object from a node q, a finite, acyclic waiting chain is being built between q and the node owning the object (the head of the queue). Possibly, while the request of p is waiting at q, many other requests are passing over it and being placed ahead of it in the queue, so p's request is never served. We prove that this does not happen, providing the first complete proof for a distributed queue protocol, accommodating asynchrony and concurrent requests.

A pleasing aspect of Combine is in not requiring fifo communication links. Prior directory protocols [START_REF] Demmer | The Arrow directory protocol[END_REF][START_REF] Herlihy | Distributed transactional memory for metric-space networks[END_REF][START_REF] Zhang | Relay: A cache-coherence protocol for distributed transactional memory[END_REF] assume that links preserve the order of messages; however, ensuring this property through a link-layer protocol can significantly increase message delay. Instead, as its name suggests, Combine handles requests that overtake each other by combining multiple requests that pass through the same node. Originally used to reduce contention in multistage interconnection networks [START_REF] Kruskal | Efficient synchronization of multiprocessors with shared memory[END_REF][START_REF] Pfister | hot spot" contention and combining in multistage interconnection networks[END_REF], combining means piggybacking information of distinct requests in the same message.

Organization: We start with preliminary definitions (Section 2), and then present Combine in Section 3. The termination proof and analysis of our protocol are given in Section 4. Section 5 discusses how to construct an overlay tree. Finally, related work is presented in Section 6 and we conclude in Section 7.

Preliminaries

We consider a set of nodes V , each with a unique identifier, communicating over a complete communication network. If two nodes p and q do not have a direct physical link between them, then an underlying routing protocol directs the message from p to q through the physical communication edges.

The cost of communication between nodes is non-uniform, and each edge (p, q) has a weight which represents the cost for sending a message from p to q, denoted δ(p, q). We assume that the weight is symmetric, that is, δ(p, q) = δ(q, p), and it satisfies the triangle inequality, that is, δ(p, q) ≤ δ(p, u) + δ(u, q).

The diameter of the network, denoted ∆, is the maximum of δ(p, q) over all pairs of nodes.

We assume reliable message delivery, that is, every message sent is eventually received. A node is able to receive a message, perform a local computation, and send a message in a single atomic step.

We assume the existence of a rooted overlay tree T , in which all physical nodes are leaves and inner nodes are mapped to physical nodes.

Let d T (p, q) be the number of hops needed to go from a leaf node p up to the lowest common ancestor of p and leaf node q in T , and then down to q (or vice versa); δ T (p, q) is the sum of the costs of traversing this path, that is, the sum of δ(., .) for the edges along this path.

The stretch of an overlay tree T is the ratio between the communication cost over T and the direct communication cost. That is, stretch T = max p,q δ T (p,q) δ(p,q) . Section 5 presents ways to construct overlay trees with small stretch.

The depth of T , denoted D T , is the number of hops on the longest path from the root of T to a leaf; the diameter of T , denoted ∆ T , is the maximum of δ T (p, q), over all pairs of nodes. (f) Object is moved from p to q Fig. 1. A move request initialized by node q when the object is located at p.

The Combine Protocol

The protocol works on an overlay tree. When the algorithm starts, each node knows its parent in the overlay tree. Some nodes, in particular, the root of the overlay tree, also have a downward pointer towards one neighbor (other than its parent).

The downward pointers create a path in the overlay tree, from the root to the leaf node initially holding the object; in Figure 1(a), the arrows indicate downward pointers towards p.

A node requesting the object x tries to find a predecessor : a nearby node waiting for x or the node currently holding x. Initially, p, the node holding the object is this predecessor.

We combine multiple requests, by piggybacking information of distinct requests in the same message, to deal with concurrent requests.

-A node q obtains the current value of the object by executing a lookup request. This request goes up in the overlay tree until it discovers a pointer towards the downward path to a predecessor; the lookup records its identifier at each visited node. When the request arrives at this predecessor, it sends a read-only copy directly to q. Each node stores the information associated to at most one request for any other node. -A node q acquires an object by executing a move request. This request goes up in the overlay tree until it discovers a pointer towards the downward path to a predecessor. This is represented by the successive steps of a move as indicated in Figure 1. The move sets downward pointers towards q while going up the tree, and resets the downward pointers it follows while descending towards a predecessor. If the move discovers a stored lookup it embeds it rather than passing over it. When the move and (possibly) its embedded lookup reach a predecessor p, they wait until p receives the object. After p receives the object and releases it, p sends the object to q and a read-only copy of the object to nodes who issued the embedded lookup requests.

Since the downward path to the object may be changing while a lookup (or a move) is trying to locate the object, the lookup may remain blocked at some intermediate node u on the path towards the object. Without combining, a move request could overtake a lookup request and remove the path of pointers, thus, preventing it from terminating. However, the identifier stored in all the nodes a lookup visits on its path to the predecessor allows an overtaking move to embed the lookup. This guarantees termination of concurrent requests, even when messages are reordered. Information stored at the nodes ensures that a lookup is not processed multiple times.

We now present the algorithm in more detail. The state of a node appears in Algorithm 1. Each node knows its parent in the overlay tree, except the root, whose parent = ⊥. A node might have a pointer towards one of its children (otherwise it is ⊥); the pointer at the root is not ⊥. Each node also maintains a variable lookups, holding information useful for combining.

Algorithm 1 State and Message

lookups, a record of embedded lookup entries

The lookup() operation: A lookup request r issued by a node q carries a unique identifier including its sequence number, say ts = τ , and its initiator, id = q. Its pseudocode appears in Algorithm 2. A lookup can be in three distinct states: it is either running and no move overtook it (not-served), it is running and a move request overtook and embedded it (passed), or it is over (served).

The lookup request proceeds in two subsequent phases. First, its initiator node sends a message that traverses its ancestors up to the first ancestor whose pointer indicates the direction towards a predecessor-this is the up phase (Lines 1-8). Second, the lookup message follows successively all the downward pointers Algorithm 2 Lookup of object x at node u 1: Receiving up, lookup, q, τ, * from v:

✄ Lookup up phase 2:
if ∄ q, τ1, * ∈ u.lookups : τ1 ≥ τ then ✄ Not a stale message? if ∃rq = q, τ2, * ∈ u.lookups : τ2 < τ then ✄ First time we hear about?

4: u.lookups ← u.lookups \ {rq} ∪ { q, τ, not-served } ✄ Overwrite stored lookup 5: else u.lookups ← u.lookups ∪ { q, τ, not-served } ✄ Store lookup 6: if u.pointer = ⊥ then 7:
send up, lookup, q, τ, ⊥ to u.parent

✄ Resume up phase 8:
else send down, lookup, q, τ, ⊥ to u.pointer ✄ Start down phase 9: Receiving down, lookup, q, τ, * from v:

✄ Lookup down phase 10: if ∄ q, τ1, * ∈ u.lookups : τ1 ≥ τ then 11: if ∃rq = q, τ2, * ∈ u.lookups : τ2 < τ then 12: u.lookups ← u.lookups \ {rq} ∪ { q, τ, not-served } 13: else u.lookups ← u.lookups ∪ { q, τ, not-served } 14:
if u is a leaf then 15:

send x read-only to q ✄ Blocking send (i.e., executes as soon as u releases x)

16:
else send down, lookup, q, τ, ⊥ to u.pointer ✄ Resume down phase down to a predecessor-this is the down phase (Lines 9-16). The protocol guarantees that there is a downward path of pointers from the root to a predecessor, hence, the lookup finds it (see Lemma 2).

A node keeps track of the lookups that visited it by recording their identifier in the field lookups, containing some lookup identifiers (i.e., their initiator identifier id and their sequence number ts) and their status. The information stored by the lookup at each visited node ensures that a lookup is embedded at most once by a move. When a new lookup is received by a node u, u records the request identifier of this freshly discovered lookup. If u had already stored a previous lookup from the same initiator, then it overwrites it by the more recent lookup, thus keeping the amount of stored information bounded (Lines 3-4).

Due to combining, the lookup may reach its predecessor either by itself or embedded in a move request. If the lookup request r arrives at its predecessor by itself, then the lookup sends a read-only copy of the object directly to the requesting node q (Line 15 of Algorithm 2).

The move() operation: The move request, described in Algorithm 3, proceeds in two phases to find its predecessor, as for the lookup. In the up phase (Lines 1-11), the message goes up in the tree to the first node whose downward pointer is set. In the down phase (Lines 12-26), it follows the pointers down to its predecessor. The difference in the up phase of a move request is that an intermediate node u receiving the move message from its child v sets its u.pointer down to v (Line 8). The difference in the down phase of a move request is that each intermediary node u receiving the message from its parent v resets its u.pointer to ⊥ (Line 16).

For each visited node u, the move request embeds all the lookup requests stored at u that need to be served and marks them as served in u (Lines 3-6, 17-20 of Algorithm 3). for all ra = a, τ, not-served ∈ u.lookups do for all ra = a, τ, not-served ∈ u.lookups do Along its path, the move may discover that either some lookup r it embeds has been already served or that it overtakes some embedded lookup r ′ (Line 29 or Line 31, respectively, of Algorithm 3). In the first case, the move just erases r from the lookups it embeds, while in the second case the move marks, both in the tuple it carries and locally at the node, that the lookup r ′ has been passed (Line 30 or Lines 32-33, respectively, of Algorithm 3).

Once obtaining the object at its predecessor, the move request first serves all the lookup requests that it embeds (Lines 23, 24), then sends the object to the node that issued the move (Line 25) and finally deletes the object at the current node (Line 26).

If the object is not at its predecessor when the request arrives, the request is enqueued and its initiator node will receive the object as soon as the predecessor releases the object (after having obtained it).

Concurrent request considerations: Note that a lookup may not arrive at its predecessor because a concurrent move request overtook it and embeds it, that is, the lookup r found at a node u that u.pointer equals v, later, a move m follows the same downward pointer to v, but arrives at v before r. The lookup detects the overtaking by m and stops at node v (Line 13 of Algorithm 3, and Lines 2 and 10 of Algorithm 2). Finally, the move m embeds the lookup r and serves it once it reaches its predecessor (Lines 23, 24 of Algorithm 3 and Lines 31, 32 of Algorithm 3).

Additionally, note that no multiple move requests can arrive at the same predecessor node, as a move follows a path of pointers that it immediately removes. Similarly, no lookup arrives at a node where a move already arrived, unless embedded in it. Finally, observe that no move is issued from a node that is waiting for the object or that stores the object.

Analysis of Combine

A request initiated by node p is served when p receives a copy of the object, which is read-only in case of a lookup request. This section shows that every request is eventually served, and analyzes the communication cost. We start by considering only move requests, and then extend the analysis to lookup requests.

Inspecting the pseudocode of the up phase shows that, for every ℓ > 1, a move request m sets a downward pointer from a node u at level ℓ to a node u ′ at level ℓ -1 only if it has previously set a downward pointer from u ′ to a node at level ℓ -2. Thus, assuming no other move request modifies these links, there is a downward path from u to a leaf node. The proof of the next lemma shows that this path from u to a leaf exists even if another move request redirects a pointer set by m at some level ℓ ′ ≤ ℓ. Lemma 1. If there is a downward pointer at a node u, then there is a downward path from u to a leaf node.

Proof. We prove that if there is a downward pointer at node u at level ℓ, then there is a path from u to a leaf node. We prove that this path exists even when move requests may redirect links on this path from u to a leaf node.

The proof is by induction on the highest level ℓ ′ such that no pointer is redirected between levels ℓ ′ and ℓ. The base case, ℓ ′ = 1, is obvious.

For the inductive step, ℓ ′ > 1, assume that there is always a path from u to a leaf node, even if move requests change any of the pointers set by m at some level below ℓ ′ -1. Let m ′ be a move request that redirects the downward pointer at level ℓ ′ , that is, m ′ redirects the link at node u ′ to a node v at level ℓ ′ -1. (Note that the link redirection is done atomically by assumption, so that two nodes can not redirect the same link in two different directions.) However, by the inductive hypothesis (applied to m ′ ), this means that there is a downward path from v to a leaf node. Hence, there is a downward path from u ′ to a leaf node, and since no pointer is redirected at the levels between ℓ ′ and ℓ, the inductive claim follows.

⊓ ⊔ Lemma 2. At any configuration, there is a path of downward pointers from the root to a leaf node.

Proof. Initially, the invariant is true by assumption. The claim follows from Lemma 1, since there is always a downward pointer at the root.

⊓ ⊔

Observation 1 A move request is not passed by another move request, since setting of the link and sending the same request in the next step of the path (upon receiving a move request) happen in an atomic step.

We next argue that a request never backtracks its path towards the object.

Lemma 3. A move request m does not visit the same node twice.

Proof. Assume, by way of contradiction, that m visits some node twice. Clearly, a move request does not backtrack during its down phase. Then, let u be the first node that m visits twice during its up phase. Since m does not visits the same node twice during the down phase, m does not find a downward link at u, when visiting u for the first time. Thus, m continues to u ′ , the parent of u.

If m finds a downward link to u at u ′ , then we obtain a contradiction, by Observation 1 and since the only way for this downward link to exist is that m has been passed by another move request. Otherwise, m does not find a downward link at u ′ , and due to the tree structure, this contradicts the fact that u is the first node that m visits twice.

⊓ ⊔

A node p is the predecessor of node q if the move message sent by node p has reached node q and p is waiting for q to send the object. Lemma 4. A move request m by node p reaches its predecessor q within d T (p, q) hops and δ T (p, q) total cost. Proof. Since there is always a downward pointer at the root, Lemma 1 and Observation 1 imply that the request m eventually reaches its predecessor q. Moreover, by Lemma 3 and the tree structure, the up-phase eventually completes by reaching the lowest common ancestor of p and q. Then m follows the path towards q using only downward pointers. Thus, the total number of hops traversed by m during both phases is d T (p, q) and the total cost is δ T (p, q). ⊓ ⊔ This means that D T is an upper bound on the number of hops for a request to find its predecessor.

Lemma 4 already allows to bound the communication cost of a request issued by node q, that is, the cost of reaching the node p from which a copy of the object is sent to q. Observe that once the request reaches p, the object is sent directly from p to q without traversing the overlay tree.

Theorem 1. The communication cost of a request issued by node q and served by node p is O(δ T (p, q)).

Clearly, embedding lookup requests in move requests does not increase the message complexity, but it might increase the bit complexity. In [START_REF] Attiya | Combine: An improved directory-based consistency protocol[END_REF], we measure the total number of bits sent on behalf of a request, and show that combining does not increase the number of bits transmitted due to a lookup request. (The argument is straightforward for move requests, which are never embedded.)

Note that finding a predecessor does not immediately imply that the request of p does not starve, and must be eventually served. It is possible that although the request reaches the predecessor q, q's request itself is still on the path to its own predecessor. During this time, other requests may constantly take over p's request and be inserted into the queue ahead of it. We next limit the effect of this to ensure that a request is eventually served.

For a given configuration, we define a chain of requests starting from the initiator of a request m. Let u 0 be the node that initiated m; the node before u 0 is its predecessor, u 1 . The node before u 1 is u 1 's predecessor, if u 1 has reached it. The chain ends at a node that does not have a predecessor (yet), or at the node that holds the object.

The length of the chain is the number of nodes in it. So, the chain ends at a node whose request is still on its way to its predecessor, or when the node holds the object. In the last case, where the end of the chain holds the object, we say that the chain is complete.

Observe that at a configuration, a node appears at most once in a chain, since a node cannot have two outstanding requests at the same time.

For the rest of the proof, we assume that each message takes at most one time unit, that is, d hops take at most d time units. Lemma 5. A chain is complete within at most n • D T time units after m is issued.

Proof. We show, by induction on k, that after k •D T time units, the length of the chain is either at least k, or the chain is complete. Base case, k = 0, is obvious. For the induction step, consider the head of the chain. If it holds the object, then the chain is complete and we are done. Otherwise, as it has already issued a request, by Lemma 4, within at most D T hops, and hence, time units, it finds its predecessor, implying that the length of the chain grows by one.

Since a node appears at most once in a chain, its length, k, can be at most n, and hence, the chain is complete within n • D T time units.

⊓ ⊔

Once a chain is complete, the position of r in the queue is fixed, and the requests start waiting.

Assume that the time to execute a request at a node is negligible, and that the object is sent from one node in the chain to its successor within one hop. Thus, within n hops the object arrives at i 0 , implying the next theorem.

Theorem 2 (No starvation).

A request is served within n • D T + n time units.

We now discuss how to modify the proof to accommodate a lookup request r. Lemma 1 (and hence, Lemma 2) does not change since only move requests change the downward paths. For Lemma 3, the path can be changed only if r is passed by m, so r stops once at u ′ . The move request m that embeds r will not visit u twice, as argued above. Hence, the claim follows. For Lemma 4, if a lookup request is passed at a node u, then a move request m embeds the lookup at a node u ′ , that is, the parent or the child of u, respectively, if m passed the lookup in the up or down phase. Thus, the move request will reach its predecessor, which is also the predecessor of the lookup. A read-only copy of the object will be sent to the lookup before the object is sent to the node that issued the move request that embeds the lookup.

The lookup and move requests can be used to support read and write operations, respectively, and provide a linearizable read/write object [START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF], in a manner similar to Arrow [START_REF] Demmer | The Arrow directory protocol[END_REF].

Constructing an Overlay Tree

Constructing an overlay tree with good stretch is the key to obtaining good performance in Combine. One approach is a direct construction of an overlay tree, in a manner similar to [START_REF] Herlihy | Distributed transactional memory for metric-space networks[END_REF]. Another approach is to derive an overlay tree T from any spanning tree ST , without deteriorating the stretch. The rest of this section describes this approach.

Pick a center u of ST as the root of the overlay tree. (I.e., a node minimizing the longest hop distance to a leaf node.)

Let k be the level of u in the resulting rooted tree. By backwards induction, we augment ST with virtual nodes and virtual links to obtain an overlay tree T where all nodes of ST are leaf nodes, without increasing the stretch of the tree. (See Figure 2.) The depth of T , D T , is k. At level k -1 we add to T a duplicate of the root u and create a virtual link between this duplicate and u itself. Then, for every level ℓ < k -1, we augment level ℓ of the spanning tree with a virtual node for each (virtual or physical) node at level ℓ + 1 and create a virtual link between a node at level ℓ and its duplicate at level ℓ + 1. To see why the stretch of the overlay tree T is equal to the stretch of the underlying spanning tree ST , note that we do not change the structure of the spanning tree, but augment it with virtual paths consisting of the same node, so that each becomes a leaf. Since the cost of sending a message from a node u to itself is negligible compared with the cost of sending a message from u to any other node in the system, the cost of these virtual paths (which have at most k hops) is also negligible.

There are constructions of a spanning tree with low stretch, e.g., [START_REF] Emek | Approximating minimum max-stretch spanning trees on unweighted graphs[END_REF], which can be used to derive an overlay tree with the same stretch.

Related Work

We start by discussing directory protocols that are implemented in software, and then turn to hardware protocols.

Arrow [START_REF] Demmer | The Arrow directory protocol[END_REF] is a distributed directory protocol, maintaining a distributed queue, using path reversal. The protocol operates on spanning tree, where all nodes (including inner ones) may request the object. Every node holds a pointer to one of its neighbors in the tree, indicating the direction towards the node owning the object; the path formed by all the pointers indicates the location of a sink node either holding the object or that is going to own the object. A move request redirects the pointers as it follows this path to find the sink, so the initiator of the request becomes the new sink. In this respect, Arrow and Combine are quite similar; however, the fact that in Combine only leaf nodes request the object, allows to provide a complete and relatively simple proof of the protocol's behavior, including lack of starvation.

The original paper on Arrow analyzes the protocol under the assumption that requests are sequential. Herlihy, Tirthapura and Wattenhofer [START_REF] Herlihy | Competitive concurrent distributed queuing[END_REF] analyze Arrow assuming concurrent requests in a one-shot situation, where all requests arrive together; starvation-freedom is obvious under this assumption. Kuhn and Wattenhofer [START_REF] Kuhn | Dynamic analysis of the arrow distributed protocol[END_REF] allow requests at arbitrary times, but assume that the system is synchronous. They provide a competitive analysis of the distance to the predecessor found by a request (relative to an optimal algorithm aware of all requests, including future ones); it seems that this analysis also applies to Combine. The communication cost of Arrow is proportional to the stretch of the spanning tree used. Herlihy, Kuhn, Tirthapura and Wattenhofer [START_REF] Herlihy | Dynamic analysis of the arrow distributed protocol[END_REF] merge these works in a complex competitive analysis of Arrow for the asynchronous case. The difference with our analysis is twofold. First, they do not prove starvation freedom yet they analyze latency by assuming that requests are assigned a fixed location in the queue. In contrast, we consider worst-case scenarios where a request finds its predecessor before its predecessor finds its own predecessor, in which the requests order is undefined. Second, they restrict their analysis to exclusive accesses, and it does not handle the shared read-only requests discussed in [START_REF] Demmer | The Arrow directory protocol[END_REF]the reason is that requests get reordered due to message asynchrony, delaying arbitrarily read-only requests. Combine provides shared and exclusive requests and we provide a simple proof that they do not starve despite asynchrony.

More recently, Zhang and Ravindran [START_REF] Zhang | Relay: A cache-coherence protocol for distributed transactional memory[END_REF] presented Relay, a directory protocol that also runs on a spanning tree. In Relay, pointers lead to the node currently holding the object (rather than to a node that is already waiting for the object), and they are changed only after the object moves from one node to another. (This is similar to the tree-based mutual exclusion algorithm of Raymond [START_REF] Raymond | A tree-based algorithm for distributed mutual exclusion[END_REF].) When requests are concurrent, they are not queued one after the other, and a request may travel to a distant node currently holding the object, while it ends up obtaining the object from a nearby node (which is going to receive the object first). (See [START_REF] Attiya | Combine: An improved directory-based consistency protocol[END_REF].)

Ballistic [START_REF] Herlihy | Distributed transactional memory for metric-space networks[END_REF] assumes a hierarchical overlay structure, whose leaves are the physical nodes; this structure is similar to the overlay tree used in Combine, but it is enriched with shortcuts, so that a node has several parents in the level above. Requests travel up and down this overlay structure in a manner similar to Combine; since requests might be going over parallel links, however, performance may deteriorate due to concurrent requests. It is possible to construct a situation where a request travels to the root of the structure, but ends up obtaining the object from a sibling node (see [START_REF] Attiya | Combine: An improved directory-based consistency protocol[END_REF][START_REF] Sun | The Ballistic Protocol: Location-aware Distributed Cache Coherence in Metric-Space Networks[END_REF]). Sun's thesis [START_REF] Sun | The Ballistic Protocol: Location-aware Distributed Cache Coherence in Metric-Space Networks[END_REF] discusses this problem and suggests a variant that integrates a mutual exclusion protocol in each level. The cost of this variant depends on the mutual exclusion algorithm chosen, but it can be quite high since many nodes may participate in a level. Sun's thesis also includes a proof that requests do not starve, but it relies on a strong synchrony assumption, that all messages on a link incur a fixed delay.

The next table compares the communication cost of a request by node p, served by node q. In the table, δ ST (p, q) denotes the (weighted) distance between p and q on a spanning tree; while ∆ ST is the (weighter) diameter of the spanning tree. The construction of Section 5 implies that they are not better (asymptotically) than the distance and diameter of the overlay tree (δ T (p, q) and ∆ T ). In hardware cache coherent systems, a directory is used to store the memory addresses of all data that are present in the cache of each node. It maintains access coherence by allowing cache hits or by (re)reading a block of data from the memory. In [START_REF] Censier | A new solution to coherence problems in multicache systems[END_REF], blocks have three states indicating whether they are shared, exclusive or invalid. A block is either invalidated when some specific action may violate coherence or upon receiving an invalidation broadcast message [START_REF] Archibald | An economical solution to the cache coherence problem[END_REF]. In addition, the directory can maintain information to restrict the broadcast to affected nodes, as suggested in [START_REF] Agarwal | An evaluation of directory schemes for cache coherence[END_REF]. Finally, the directory size can be reduced by linking the nodes that maintain a copy of the block [START_REF] James | Scalable coherent interface[END_REF]. Upon invalidation of a block, a message invalidates successively the caches of all linked nodes.

The design principle of this later approach is similar to the distributed queue that is maintained by our protocol except that we use it for passing exclusive accesses and not for invalidating read-only copies.

Discussion

We have proposed Combine to efficiently solve a key challenge of a directory protocol in highly-contended situations: ensuring that all requests eventually get served. Some prior protocols prove that requests do not starve under the assumption that requests execute one by one and / or that communication is synchronous. Others have high communication complexity as they require that conflicting requests run additional mutual exclusion algorithms or because concurrent requests may result in an unbounded number of message exchanges. Our combining technique does not incur any communication overhead to handle concurrency. It can be easily adapted to tolerate unreliable communication, by a traditional retransmission technique based on timeouts and acknowledgements.

Consistency protocols play an important role in data-flow distributed implementations of software transactional memory (DTM) in large-scale distributed memory systems [START_REF] Herlihy | Distributed transactional memory for metric-space networks[END_REF]. The consistency protocols of existing DTMs [START_REF] Bocchino | Software transactional memory for large scale clusters[END_REF][START_REF] Couceiro | D2STM: Dependable distributed software transactional memory[END_REF][START_REF] Manassiev | Exploiting distributed version concurrency in a transactional memory cluster[END_REF] seem less suited for large-scale systems than directory-based consistency protocols. They follow a lazy conflict detection strategy either by acquiring a global lock [START_REF] Manassiev | Exploiting distributed version concurrency in a transactional memory cluster[END_REF] or by broadcasting [START_REF] Bocchino | Software transactional memory for large scale clusters[END_REF][START_REF] Couceiro | D2STM: Dependable distributed software transactional memory[END_REF], at commit-time-two techniques that do not scale well when the number of nodes grow.

We leave to future work the interesting question of integrating the directory protocol into a full-fledged distributed transactional memory.

1 : 4 : 8 :

 148 State of a node u: 2: parent ∈ N ∪ {⊥}, representing the parent node in the tree 3: pointer ∈ N ∪ {⊥}, the direction towards the known predecessor, initially ⊥ lookups a record (initially empty) of lookup entries with fields: 5: id ∈ N, the identifier of the node initiating the request 6: ts ∈ N, the sequence number of the request 7:status ∈ {not-served, served, passed}, the request status Message type: 9: message a record with fields: 10: phase ∈ {up, down} 11: type ∈ {move, lookup} 12: id ∈ N, the identifier of the request 13:ts ∈ N, the sequence number of the request 14:

6 Algorithm 3 1 :

 631 Move of object x at node u Receiving m = up, move, q, τ, lookups from v:

4 :✄ Set downward pointer 9 :

 49 if ∄ a, τ ′ , * ∈ m.lookups : τ ′ ≥ τ then 5: m.lookups ← m.lookups ∪ {ra} ✄ Embed non-served lookups 6: u.lookups ← u.lookups \ {ra} ∪ { a, τ, served } ✄ Mark lookups as served 7: oldpointer ← u.pointer 8: u.pointer ← v if oldpointer = ⊥ then 10: send up, move, q, τ, m.lookups to u.parent ✄ Resume up phase 11: else send down, move, q, τ, m.lookups to oldpointer ✄ Start down phase 12: Receiving m = down, move, q, τ, lookups from v: ✄ Move down phase 13: clean(m)

18 :else✄

 18 if ∄ a, τ ′ , * ∈ m.lookups : τ ′ ≥ τ then 19: m.lookups ← m.lookups ∪ {ra} 20: u.lookups ← u.lookups \ {ra} ∪ { a, τ, served } 21: send m to oldpointer ✄ Resume down phase 22: Predecessor is reached 23:for all a, τ, status ∈ m.lookups : ∄ a, τ ′ , * ∈ u.lookups with τ ′ ≥ τ do 24: send x read-only to a ✄ Blocking send of read-only copy 25: send x to q ✄ Blocking send of object 26: delete(x) ✄ Remove object local copy 27: clean(m): ✄ Clean-up the unused information 28: for all a, τ, not-served ∈ m.lookups do 29: if ∃ a, τ ′ , status ∈ u.lookups : (status = served ∧ τ ′ = τ ) ∨ (τ ′ > τ ) then 30: m.lookups ← m.lookups \ { a, τ, not-served } 31: if a, τ, * / ∈ u.lookups then 32: m.lookups ← m.lookups \ { a, τ, not-served } ∪ { a, τ, passed } 33:u.lookups ← u.lookups ∪ { a, τ, passed }

Fig. 2 .

 2 Fig. 2. Deriving an overlay tree from a spanning tree.

⋆ Hagit Attiya is partially supported by the Israel Science Foundation (grant number 953/06). Alessia Milani is financed by ANR grant R-DISCOVER.