Hagit Attiya

Eshcar Hillel

Alessia Milani

Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory

Keywords: Transactional memory, disjoint-access parallelism, partial snapshots, lower bound, impossibility result

Transactional memory (TM) is a popular approach for alleviating the difficulty of programming concurrent applications; TM guarantees that a transaction, consisting of a sequence of operations, appear to be executed atomically. Two fundamental properties of TM implementations are disjointaccess parallelism and the invisibility of read operations. Disjoint access parallelism ensures that operations on disconnected data do not interfere, and thus it is critical for TM scalability. The invisibility of read operations means that their implementation does not write to the memory, thereby reducing memory contention.

This paper proves an inherent tradeoff for implementations of transactional memories: they cannot be both disjoint-access 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, snapshot isolation and serializability.

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 on data items 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 represent transactions; an edge connects two conflicting transactions, i.e., two transactions that access the same item. Consider, for example, four concurrent transactions: T 1 accessing data items ı 1 , ı 2 , T 2 accessing data items ı 2 , ı 3 , T 3 accessing data item ı 3 , and T 4 accessing data item ı 4 . Figure 1 depicts the conflict graph of the execution interval of these four transactions. This conflict graph contains two edges connecting T 2 with the transactions with which it has conflicts, T 1 and T 3 . (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 they are connected in the conflict graph. In particular, there is no concurrent access to the shared memory by transactions without common data items. In these implementations, the transactions T 1 and T 4 in the example of Figure 1, should not access the same base object, since they are not connected in the conflict graph. On the other hand, transactions T 1 and T 3 may access the same base object although they do not have a common data item.

Another important goal is to optimize read-only transactions, i.e., transactions that access the memory only through read operations. It is desirable

T 1 T 2 T 4 T 3
Fig. 1 Example of a simple conflict graph: T 1 accesses ı 1 and ı 2 ; T 2 accesses ı 2 and ı 3 ; T 3 accesses ı 3 ; and T 4 accesses ı 4 .

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 that 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 disjointaccess parallel and has invisible, wait-free 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 T 1 is a read-only transaction, while T 2 , T 3 , and T 4 all write to their data items. The algorithm given in [START_REF] Herlihy | Software transactional memory for dynamic-sized data structures[END_REF], is disjoint-access parallel and has invisible read-only transactions. In some execution, T 1 reads ı 2 then T 1 stops taking steps and T 2 writes to ı 2 . The transaction T 2 runs solo without interruption and since the algorithm is obstruction-free T 2 completes successfully. Then, T 1 resumes, reads ı 1 , and finally validates its read set at commit time. The value of ı 2 has changed since T 1 read it, and T 1 aborts.

The algorithm given in [START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF] is a multiversioned transactional memory, with invisible, wait-free read-only transactions, which uses a common counter to totally order committed transactions writing different versions of the same data item. This allows each read-only transaction to return a consistent snapshot of the memory, despite concurrent writing transactions. Due to the common counter, this is not disjoint-access parallel: In the example of Figure 1, it is possible that all the transactions access the counter, some of them for writing, 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 transactions-and one of these desirable properties must always be compromised. In fact, we prove a stronger result, showing that in a disjointaccess 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 (including each aborted transaction, separately), extended to allow operations other than reads and writes. Our proofs 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, snapshot isolation and serializability.

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 transactional memory 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 transactional memory implementation with wait-free read-only transactions) must apply write 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 snapshot isolation and serializability. 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 (abbreviated primitives) 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 (low level) primitives, we allow arbitrary read-modify-write primitives, like cas, even those accessing several locations simultaneously.

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 C 0 , φ 0 , C 1 , φ 1 , C 2 , . . ., 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 C 0 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, p executes the same sequence of computation steps, which return the same results.

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 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 this serialization order preserves the perprocess order, i.e., transactions of the same process maintain their order. Since infinite executions also have to be serializable, it follows that if transactions by the same process read a data item, they eventually return the last value written to it. Traditional definitions of serializability (e.g., [START_REF] Weikum | Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery[END_REF][START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF]) apply only to finite executions, and hence, admit trivial implementations, where read operations always return the initial values of the data items.

An STM is strictly serializable if the serialization order preserves the order of non-overlapping transactions [START_REF] Papadimitriou | The serializability of concurrent database updates[END_REF]; this notion is called order-preserving 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, lock-based 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, where vertices represent transactions; an edge connects two transactions that access the same item. Two transactions T 1 and T 2 are disjoint-access if there is no path between them in the conflict graph of the minimal execution interval containing the intervals of T 1 and T 2 .

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 disjoint-access parallel if two processes p 1 and p 2 , executing transactions T 1 and T 2 , concurrently contend on the same base object, only if T 1 and T 2 are not disjoint-access. This definition captures the first condition of the disjoint-access 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 requirement is weaker than theirs, as we allow 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 1.

Specifically, we construct an infinite execution of a read-only transaction. This execution consists of a single read-only 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 an update transaction is moved forward in the execution, while other is called a backward flip since an update transaction is deferred in the execution. Formally:

Definition 2 A flippable execution of length k with t updaters is a finite ex- ecution E k = U 0 s 1 U 1 . . . s k U k executed
by processes p 0 , . . . , p t-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:

1. for j = 1, . . . , k, s j is a single step by q, 2. for j = 0, . . . , k, U j is a solo execution of a complete update transaction, in which process p h ∈ {p 0 , . . . , p t-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 = 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 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 = U 0 s 1 U 1 . . . 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 = U 0 s 1 U 1 . . . 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). q : s 1 . . . s l-1 s l . . . s k p 0 : U 0 . . . U l-1 . . . U k p 1 : U 1 . . . U l . . . (a) E k . q : s 1 . . . s l-1 s l . . . s k p 0 : U 0 . . . U l-1 . . . U k p 1 : U 1 . . . U l . . . (b) Forward flip: U l is performed before U l-1 s l . q : s 1 . . . s l-1 s l . . . s k p 0 : U 0 . . . U l-1 . . . U k p 1 : U 1 . . . U l . . . (c) Backward flip: U l-1 is performed after s l U l .
The next lemma proves that if the implementation has a flippable execution then the read-only transaction in this execution does not terminate; it 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 = U 0 s 1 U 1 . . . 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 0 , . . . , v t-1 ). The proof first fixes the serialization of the update transactions, and then shows that it is not possible to serial the read-only transaction among the update transactions, using the forward and backward flip executions, which are indistinguishable to q from E k .

Since the update transactions in the execution E k do not overlap, they must be serialized in the order U 0 , . . . , U k . Since all steps of the read-only transaction by q are after U 0 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 = U 0 s 1 U 1 . . . 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 = U 0 s 1 U 1 . . . 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 vector, (v 0 , . . . , v t-1 ), as in E k .

Since the update transactions do not overlap in F l , they are serialized in the order U 0 , . . . , 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 to 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 be 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.

⊓ ⊔

It remains to prove that a flippable executions exists. Lemma 3 (below) shows how to inductively construct a flippable execution, when read-only transactions are invisible. 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 Lemma 2, 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. Note that two consecutive update transactions do not contradict weak disjoint-access parallelism since the steps of their executing processes are not interleaved. The proof of the next 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 U j h and U j h ′ .

Proof Assume, towards a contradiction, that p h and p h ′ contend on a base object when executing U j h U j h ′ from a quiescent configuration C. If in U j h , p h applies a non-trivial primitive to a base object on which they contend, let 0000 0000 0000 1111 1111 1111 00000 00000 00000 11111 11111 11111 : :

U jh p h α h p h ′ U j h ′ φ h α h ′ φ h ′ (a)
Serial execution of U j h and U j h ′ from configuration C : ...

... :

p h α h p h ′ α h ′ φ h φ h ′ (b) Overlapping execution of U j h and U j h ′ from configuration C
Fig. 3 Illustration for the proof of Lemma 2 φ 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 U j 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 U j 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 create an overlapping execution of the update transactions U j h and U j 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 illustrated 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 U j 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 p 0 and p 1 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 U 0 , an update transaction by p 0 that writes 1 to ı 0 . U 0 successfully terminates since it runs solo from a quiescent configuration.

For the induction step, consider a flippable execution of length k ≥ 1, E k = U 0 s 1 U 1 s 2 . . . U k , which is indistinguishable to p 0 and p 1 from the execution

E ′ k = U 0 U 1 . . . U k .
We show how to construct a flippable execution of length k + 1, which is indistinguishable from an execution in which only p 0 and p 1 take steps.

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 = 1-h ′ ; 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: The configuration at the end of E k+1 = E k s k+1 is indistinguishable from the configuration at the end of E ′ k , which is quiescent; since the execution of U k+1 from the configuration at the end of E ′ k must terminate successfully, by our progress condition, U k+1 must also terminate successfully when executing from the configuration at the end of E k+1 = E k s k+1 .

Since the read-only transaction by q is invisible, E k+1 U k+1 is indistinguishable to p 0 and p 1 from the execution E ′ k U k+1 . It remains to prove that E k+1 is a flippable execution, i.e., 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 execution F l which is either ← -

F l = U 0 s 1 U 1 . . . s l-1 U l U l-1 s l . . . U k or -→ F l = U 0 s 1 U 1 . . . 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 U k+1 from C ′ k-1 , 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 = U 0 s 1 U 1 . . . 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 = U 0 s 1 U 1 . . . 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 executions, ← -F k+1 and -→ F k+1 , are indistinguishable to all processes from E k+1 .

⊓ ⊔

The impossibility result follows from Lemmas 1 and 3.

Theorem 1 There is no weakly disjoint-access parallel implementation with invisible read-only transactions of a strictly serializable STM, in which readonly transactions always terminate successfully.

The impossibility result stated in Theorem 1 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 readonly transaction of t items in a disjoint-access parallel STM implementation, which successfully terminates in a finite number of steps, must apply nontrivial 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 successfully-does 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 p 1 , p 2 concurrently access the same base object when executing transactions T 1 and T 2 , respectively, only if T 1 and T 2 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 4) that, in a disjoint-access parallel STM implementation, two update transactions executed by different processes on different

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

items do not access a common base object when each of them runs solo from a quiescent configuration. This is used in Lemma 5 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.

Lemma 4 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 U j 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)). We show how to paste the executions so that the events φ h and φ h ′ are concurrently pending. 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 ′ ; that is, p h ′ and p h concurrently access 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 U j h and U j 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 5 For every k ≥ 0, a disjoint-access parallel implementation of an STM in which a read-only transaction of t > 2 data items applies non-trivial primitives to at most t-2 base objects, has a flippable execution E k = U 0 s 1 U 1 s 2 . . . U k with t updaters, which is indistinguishable to p 0 , . . . , p t-1 from the execution E ′ k = U 0 U 1 . . . U k in which only p 0 , . . . , p t-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, U 0 , by process p 0 that writes 1 to ı 1 . U 0 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 , which is indistinguishable to p 0 , . . . , p t-1 from the execution E ′ k = U 0 U 1 . . . U k .
We show how to construct a flippable execution of length k + 1, which is indistinguishable to p 0 , . . . , p t-1 from an execution in which only p 0 , . . . , p t-1 take steps.

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 p 0 , . . . , p t-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 read-only transaction applies nontrivial 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 4, 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 p 0 , . . . , p t-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 = 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 execution F l which is either ← -

F l = U 0 s 1 U 1 . . . s l-1 U l U l-1 s l . . . U k or -→ F l = U 0 s 1 U 1 . . . 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 = U 0 s 1 U 1 . . . 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 = U 0 s 1 U 1 . . . 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 2 In a strict serializable disjoint-access parallel STM implementation for t+1 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.

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 1 and Theorem 2 hold for weaker consistency conditions, namely, snapshot isolation and serializability.

Snapshot Isolation

Snapshot isolation [START_REF] Berenson | A critique of ANSI SQL isolation levels[END_REF][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. Informally, all read operations in a transaction return the value of the most recent value as of the time the transaction starts. In addition, the write sets of any pair of concurrent transactions must be disjoint. For a formal definition, see Definition 10.3].

We prove an analogue of Lemma 1, that is, we show that the read-only transaction by process q in a flippable execution cannot terminate successfully, also when the implementation provides snapshot isolation.

Lemma 6 Consider a flippable execution of length k ≥ 0 with t updaters, E k = U 0 s 1 U 1 . . . s k U k , of an STM that provides snapshot isolation. The readonly transaction by process q does not terminate successfully.

Proof Assume, towards a contradiction, that q successfully terminates its readonly transaction in E k , with a result (v 0 , . . . , v t-1 ). Let ı f l be the item written by U l ; recall that the initial value of all items is zero and that U l writes l + 1 to ı f l . By the definition of snapshot isolation, each read operation from an item in the read-only transaction by q returns the most recent committed write operation that updated this item as of the time the read-only transaction starts. The read-only transaction by q returns the most recent values after U 0 is executed and before any other update is executed. Hence, v f0 = 1, and for every l,

1 ≤ l ≤ t -1, v f l = 0.
The execution E k is indistinguishable to process q from F 1 , which is either the forward flip ← -

F 1 = U 1 U 0 s 1 s 2 U 2 . . . U k or the backward flip -→ F 1 = s 1 U 1 U 0 s 2 U 2 . . . U k .
Hence, the read-only transaction executed by q in F 1 returns the same vector as in E 1 . However, the definition of snapshot isolation requires different results for the read-only transaction in these executions. In ← -F 1 , the read-only transaction returns the most recent values after U 0 and U 1 are executed and before any other update is executed, hence it returns a vector where v f0 = 1, v f1 = 2, and v f l = 0, for every l, 2 ≤ l ≤ t -1. In -→ F 1 , the read-only transaction returns the most recent values before any update is executed, hence it returns a vector where v f l = 0, for every l, 0 ≤ l ≤ t -1. Thus, the read-only transaction cannot terminate successfully.

⊓ ⊔

Arguments similar to Section 3 can be used to derive the following impossibility result and lower bound: Theorem 3 There is no weakly disjoint-access parallel STM implementation with invisible read-only transactions of an STM providing snapshot isolation, in which read-only transactions always terminate successfully.

Theorem 4 In a disjoint-access parallel STM implementation for t + 1 processes providing snapshot isolation, 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.

Serializability

Recall that an STM is serializable if transactions appear to execute sequentially, one after the other; note that we require that transactions of the same process preserve their order (per-process order) and that repeatedly reading the same data item eventually returns a non-initial value.

The proof uses an additional process q ′ . Given a flippable execution E k = U 0 s 1 U 1 . . . s k U k , we construct an augmented flippable execution

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

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 process q ′ . We apply the per-process ordering of transactions to prove that the readonly transactions of q ′ must eventually read the latest value written in U j-1 , and thus, S * j is finite.

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

Proof We show, by induction on ℓ, that U 0 , U 1 , . . . , U ℓ appear in their order of execution. In the base case, k = 0, the serialization of U 0 is trivial.

For the induction step, consider ℓ+1 . By the induction assumption, the updates U 0 , U 1 , . . . , U ℓ are serialized by their execution order in E k . By construction, S * ℓ+1 is a sequence of read-only transactions that access ı f ℓ and ı f ℓ+1 , and the last read-only transaction in S * ℓ+1 , denoted S ℓ+1 , returns the value written by U ℓ and the last value of ı f ℓ+1 before the one written by U ℓ+1 .

The sequence 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 perprocess 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 7 to prove an analogue of Lemma 1.

Lemma 8 Consider an augmented flippable execution of length k ≥ 0 with t updaters,

E k = U 0 s 1 S * 1 U 1 . . . 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 read-only transaction of process q in E k terminates successfully and returns a value (v 0 , . . . , v t-1 ), which does not violate serializability. Let the augmented flippable execution

E k = U 0 s 1 S * 1 U 1 . . . s k S * k U k correspond to a flippable execution E k = U 0 s 1 U 1 . . . s k U k .
By Lemma 7, the updates in E k are serialized in the order U 0 , U 1 , . . . , U k . The vector (v 0 , . . . , v t-1 ) 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 E k .

Since the read-only transactions executed by process q ′ are invisible, E k and E k are indistinguishable to p 0 , . . . , p t-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 8 implies the following impossibility result:

Theorem 5 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 read-only 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 8, the existence of a flippable execution (guaranteed by Lemma 5) implies there is an augmented flippable execution, and hence, Lemma 8 implies the following lower bound: Theorem 6 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.

The impossibility result and lower bound also hold for virtual world consistency, recently proposed by Imbs et al. [START_REF] Imbs | Brief announcement: virtual world consistency: a new condition for STM systems[END_REF]. This consistency condition requires serializability or strict serializability of committed transactions, and ensures that aborted transactions always see a consistent state of the memory, although not necessarily consistent with each other. Since our results do not consider the behavior of aborted transactions, they also hold for virtual world consistency.

Related Work

Many STM implementations are centralized; in particular, Lazy Snapshot Algorithm (LSA) [START_REF] Riegel | A lazy snapshot algorithm with eager validation[END_REF] relies on a single shared monotonically increasing counter to determine a unique commit timestamp for transactions, while Transactional Locking II (TL2) [START_REF] Dice | Transactional locking II[END_REF] relies on a global clock. The former approach introduces a single hot-spot accessed by all transactions, regardless of their data sets, and is therefore not disjoint-access parallel, while the latter approach relies on a single source of synchronous time, which is not realistic for systems, with a larger number of processes.

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 read-only 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 Guerraoui and Kapalka [START_REF] Guerraoui | On obstruction-free transactions[END_REF] does not hold for this weaker requirement. 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 has 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 object 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 algorithms for partial snapshot objects [START_REF] Attiya | Partial snapshot objects[END_REF][START_REF] Imbs | Help when needed, but no more: Efficient Read/Write Partial Snapshot[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 m-component 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 disjointaccess 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 disjoint-access 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. For example, Harris et al. [START_REF] Harris | A practical multi-word compare-and-swap operation[END_REF] give a disjoint-access parallel implementation of a multi-word compare-and-swap operation: an operation acquires locks on the words it needs, one by one; if another operation already holds the lock on a word, the operation helps the conflicting operation, thereby guaranteeing progress. (This algorithm is not wait-free, but additional helping can make it 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.

The multi-word compare-and-swap of [START_REF] Harris | A practical multi-word compare-and-swap operation[END_REF], can be used to atomically validate the read set and update the write set of a transaction; it requires locking all items in the data set of the transaction. This application of a multi-word operation demonstrates our lower bound: A read-only transaction has to lock all items in its read set, and therefore it writes to distinct base objects representing these locks.

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][START_REF] Keidar | On avoiding spare aborts in transactional memory[END_REF] or wasted work in STM implementations.

Fig. 2 A

 2 Fig.2A flippable execution of length k with two updaters: Figure2(a) shows a flippable execution E k ; Figure2(b)shows the forward flip execution of E k , where the update transaction U l by process p 1 is executed before the update transaction U l-1 by process p 0 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 p 0 is deferred after the update transaction U l by process p 1 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 proves that if the implementation has a flippable execution then the read-only transaction in this execution does not terminate; it 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 7

 7 Consider an augmented flippable execution of length k

Acknowledgements We would like to thank Faith Ellen, Panagiota Fatourou, Rachid Guerraoui, Michal Kapalka, Martin Vechev and the referees for helpful comments.

This research is partially supported by the Israel Science Foundation (grant number 953/06) and Intel Corporation. A. Milani is on leave from Sapienza, Universitá di Roma, supported in part by a fellowship from the Lady Davis Foundation and by a grant Progetto FIRB Italia-Israele RBIN047MH9.