Youssef A Albanay

Special theory of relativity for photons By

published or not. The documents may come     special theory of relativity for photons

Introduction

The great success of Maxwellian electrodynamics and QED is based on the hypothesis that the photon should be a particle with zero mass, which has led to an almost total acceptance of the massless photon concept. The possibility of a nonzero photon mass has been studied by De Broglie, Vigier, Bass and Schrödinger [START_REF] De Broglie | Photon Mass and New Experimental Results on Longitudinal Displacements of Laser Beams near Total Reflection[END_REF][3] [START_REF] Bass | Must the Photon Mass be Zero?[END_REF] as well as Okun [START_REF] Okun | The Concept of Mass[END_REF] [START_REF] Yu | On the photon mass[END_REF] and others. The photon mass can be estimated using the uncertainty principle [START_REF] Tu | Experimental tests of Coulomb's Law and the photon rest mass[END_REF] with the knowledge that the age of the universe is approximately years. Many laboratory experiments and astrophysical observations have been performed, using many methods, to check directly or indirectly whether the photon has mass. Table 1 shows several important limits on the photon mass [START_REF] Tu | The mass of the photon[END_REF]. The Particle Data Group lists the mass of the photon to be or [START_REF] Tu | The mass of the photon[END_REF]. There are many consequences of nonzero photon mass: the speed of light would depend on its frequency, the usual Coulomb potential would become a Yukawa potential, Maxwell's equations would be replaced by Proca's equations, the black-body radiation formula would take on a new form, and many other theories would also be affected.

In addition, it seems that a nonzero photon mass would have an impact on the special theory of relativity, because the photon mass would affect the universal constant . In fact, however, this is not necessarily true. We could simply consider that the velocity that is the key quantity in special relativity is not the velocity of light but rather a constant of nature, which is the maximum speed that any object could theoretically attain in space-time.

Although the mass of the photon is very small, any nonzero photon mass would have many consequences at a theoretical level. In this study, we will attempt to derive a dynamical relativistic energy equation for the photon as a particle. We then will see how Lorentz transformations can demonstrate, remarkably, that under certain special conditions, length expansion is also possible. All of these results together provide us with a bizarre new picture of the photon behavior.

Part I Photon mass 1. Maxwell and Proca equations

The photon mass is assumed to be exactly zero in the original Lagrangian density, which is given by [START_REF] Jackson | Classical Electrodynamics[END_REF] where and are the 4-dimensional vector potential and the 4-dimentional vector current density, respectively.

μν is the antisymmetric field stress tensor and is defined as

From the Euler-Lagrange equation, the equations of motion for a massless field are

In the 1930's, Proca added a mass term to the Lagrangian density for the electromagnetic field, modifying the Lagrangian density (1.1) to [START_REF] Jackson | Classical Electrodynamics[END_REF] The equations of motion that correspond to this Lagrangian density are Proca's equations:

The wave equation can be obtained by substituting equation (1.2) into (1.5):

and in the absence of the source, equation (1.6) reduces to This is the Klein-Gordon equation for the photon. Because the extra term could be interpreted as a characteristic length, the Compton wavelength of the photon is [START_REF] Tu | The mass of the photon[END_REF] where is the photon mass. Unfortunately, gauge invariance is lost when . In the presence of a nonzero photon mass, Maxwell's equations will become Proca's equations [START_REF] Tu | The mass of the photon[END_REF]:

Here, is the electric field, is the magnetic field, is the charge density, is the current density, is the scalar potential, is the vector potential, c is the speed of light, and is the Compton wavelength of the photon. It is clear that Proca's equations reduce to Maxwell's equations when .

The solution of equation (1.6) is the electromagnetic field in free space, with where is the wave vector, and is the angular frequency. Then, the group velocity will be or, using (1.8), we can write This is the most important consequence of nonzero photon mass: the speed of light will depend on the frequency of the electromagnetic wave. It is clear that only when or when the frequency approaches infinity, ∞.

Relativistic total energy of the photon

We can derive equation (1.16) in another simple way. If we use the quantum energy formula for photons and the relativistic total energy of particles, we will find, directly, that When it must be that , and will be unknown. Also, only when This means that the photon is in its rest frame. We know that there is no rest frame for the photon if the speed of light does not change. However, if is variable with mass and frequency, we could imagine, theoretically, that the photon could have a rest frame. Then, would be the rest frequency, which would correspond, in some way, to the photon rest mass . Now, we will combine the relativistic Doppler effect with equation (1.17). The relativistic Doppler effect for an observer receding from the light source is given by [START_REF] Rosser | An introduction to the theory of relativity[END_REF] For an observer approaching the light source, it is given by [START_REF] Rosser | An introduction to the theory of relativity[END_REF] where is the rest frequency, and is the velocity of the observer. When we insert equations (1.19) and (1.20) into (1.17), we find, after some algebra, that and Using (1.18) instead, we find and Equation (1.23) shows that the energy of the single photon, treated as a particle, decreases as the observer's velocity increases, whereas equation (1.24) shows that the energy increases with an increase in the observer's velocity.

Equations (1.21) and (1.22) are merely the normal Doppler-shift effect, i.e., (1.19) and (1.20), multiplied by Planck's constant. However, the interpretation of the two sets of equations is entirely different. The Doppler effect treats light as a wave, but equations (1.23) and (1.24) apply to a single photon with a tiny mass . Thus, we must be careful here, because the photon has finite dimensions like other particles.

Part II Photon dimensions 1. Lorentz contraction and Lorentz expansion

Equation (1.23) indicates that space-time has a special character. We know that all kinematical and dynamical phenomena in the special theory of relativity arise as necessary consequences of the nature of space-time and the Lorentz transformations. Diagram 1 illustrates the equations of the special theory of relativity have been carefully constructed in relation to each other.

Diagram 1

where is the proper time, and is the proper velocity.

We have shown, in equation (1.23), that the energy of the photon, when treated as a tiny particle, decreases as the velocity of the light source increases. This phenomenon is familiar from the relativistic Doppler effect, but here, we focused our attention on a single photon, which is clear from the presence of Planck's constant in equations (1.21) and (1.22). Equation (1.23) poses an important and exciting question: are there kinematical and dynamical equations that are consistent with equation (1.23)? Fortunately, just as Lorentz transformations lead to length contraction, we will show that, under very special conditions, Lorentz transformations can also lead to both expansion and invariance in length! Suppose that there is reference frame with spatial coordinates and time . Let ′ be another reference frame with coordinates ′ ′ ′ and time ′ that moves with speed relative to in the positive direction along the axis. The relation between the coordinates and time of an event in the inertial frame and the coordinates and time of the same event as observed in the second inertial frame ′ is given by the following Lorentz transformations [START_REF] Rosser | An introduction to the theory of relativity[END_REF]:

′ ′ ′ ′
where . If ′ instead moves in the negative direction along the axis, we have only to change the sign of the relative velocity because of the symmetry of the equations. Therefore,

′ ′ ′ ′
The famous consequences of the Lorentz transformations are length contraction and time dilation, as revealed by Einstein in his famous paper in 1905 [START_REF] Einstein | On the Electrodynamics of Moving Bodies[END_REF]. However, the Lorentz transformations also lead to other results concerning the relativity of length. Under certain special conditions, Lorentz transformations also result in length invariance and length expansion! This result was demonstrated by Sadanand D. Agashe [START_REF] Agashe | Is the Lorentz contraction inevitable in the special theory of relativity?[END_REF]. Therefore, we will follow his derivation to illustrate how Lorentz transformations can lead to length contraction and then how these transformations can also lead to length invariance and expansion. He wrote the following: "In deducing the Lorentz contraction in such a scenario, most authors talk about a rigid rod lying at rest on the ′ axis of the moving system ′ The ends and of this rod can thus be thought of as a series of events: ′ ′ ′ ′ with ′ ′ , say, so that we can call the constant (in ′ length of the rod, and so we are justified in calling the rod "rigid" in ′ Next, one shows that although the rod is at rest in ′ it is "observed" to be moving in with speed , of course. Further, as it moves in , its length remains constant in , and so it is rigid in also. However, its length in is different from its length in ′, and is, in fact, , which is smaller than . Hence the term "contraction".

Indeed, using [(1.29)...(1.32)], at any time of the coordinates of in are

′ ′ and the coordinates of in are ′ ′ where ′ and ′ in ′ correspond to a common time in and so,

′ ′ ′ ′ (1.33)
The distance between and in at time , and, thus, the length of the rod in at time are given by,

′ ′ ′ ′ ′ ′ ′ ′ = ′ ′ ′ ′ = ′ ′

=

All this is very familiar and is written only to fix the notation and to avoid misunderstanding. Note that one could allow the rod to be anywhere in the space of ′ provided it is parallel to the

′ axis." [6]

He then derived length expansion and invariance, under the title "What happens to a rod moving with an arbitrary velocity?": "Now, this business of considering the rod at rest in a moving frame of reference goes back to the early days of the special theory of relativity. One could have talked about a rod lying at rest in the first-mentioned frame, namely, S, and then considered its history as observed from the second-mentioned frame, namely, ′, assumed to be moving uniformly relative to . (This is, indeed, pointed out by many authors.) Leaving that aside, no authors seem to have considered a rod rigidly moving in and its history in ′ This is what we will do, deriving some surprising consequences. (In one excellent textbook [START_REF] Rosser | An introduction to the theory of relativity[END_REF], in Exercise 3.11, p.135, the possibility of the times and ′ of a moving point being equal is explored.) So, let a point have a history-or motion! -in , given by the series of events thus moves uniformly in with speed in the direction of the positive axis of if and in the opposite direction if . Let another point have the motion with . Thus also moves in with the same speed and in the same direction, and the distance between and remains constant in . We could think of and as the ends of a rod moving in , and that too, rigidly, since its length remains constant in .

What are the motions of and in ′ ? Is the distance between them constant in ′ too, so that the rod remains rigid in ′ ? Indeed the motions of and are uniform in ′ too, since they are given by, Their common speed is given by, The ′ distance between and at a time ′ in ′ is given by where and are related to ′ by,

′

The distance calculates out to be, Thus, the rod is observed to stay rigid in ′ too. But is its length in ′ necessarily smaller than its length observed in ? Denoting the factor multiplying in (1.38) by ), the function has the following values: ∞

∞ with

The case corresponds to the rod being at rest in and its length in ′ is observed to be smaller than its length in , but if the rod is at rest in ′ its length in ′ is observed to be larger than its length in . Further, there is a particular value of , namely: such that , and . Thus, there is speed for which the rod is observed to be moving in both and ′ but its length is observed to be the same in both.

So, we can have not only a contraction but also an expansion and even invariance!" [6]

Agashe analyzed all of these results in detail, and he also carefully discussed Einstein's papers [START_REF] Agashe | Is the Lorentz contraction inevitable in the special theory of relativity?[END_REF][7] [START_REF] Agashe | revisited with some consequences[END_REF]. He considered that [START_REF] Agashe | Is the Lorentz contraction inevitable in the special theory of relativity?[END_REF] […the "change" in length is purely a kinematical fact, arising out of the manner in which the two systems and ′ and their coordinates and times are related, and we need not look for any dynamical reason for the change in either system.

In my opinion, all of these equations may be merely superfluous mathematics, with the exception of equation (1.41). We can relate this result, i.e., length expansion, to the idea of the decrease in the photon energy when the photon is treated as a particle, i.e., to equation (1.23). Via this connection, we can build a full model of the photon as a particle.

Imagine two reference frames: moves with velocity , and ′ moves with velocity with respect to . As Agashe argued, if we consider a rod lying at rest in the frame and then consider its history as observed from the second frame ′, we will obtain many surprising consequences. The rod length may contract, expand, or even remain invariant. We will focus our attention on the phenomenon of expansion. As we have seen, length expansion occurs under very special conditions: when the velocity of frame is equal to the velocity of frame ′ , i.e., when Suppose that frame ′ moves at a speed very close to the speed of light, , but not identical to the absolute universal constant , and frame moves with the same velocity, . Imagine that frame is a single photon with velocity and has a tiny mass . Now, we will consider the history of this single photon, as observed in frame ′ .

If the photon has a mass , then it must also have a dimension in space-time in some sense. According to equation (1.41), the observer in ′ will see the photon become longer than its original length in the direction of the positive axis. We can imagine the single photon as a pulse, with a wavelength (Fig. 1); when the photon expands, it becomes redder and redder, according to the relativistic Doppler-shift effect. Thus, equation (1.41) is well consistent with equation (1.23). As the velocity of frame ′ increases, the length of the single photon in will expand further, and the energy of that photon, treated as a particle, will also decrease further. Of course, we can also imagine the contrasting situation. When the velocity of the single photon exceeds the velocity of frame ′ , i.e., when , the photon will contract and appear bluer as it approaches frame ′ (Fig. 2).

What about the relativistic time?

We know that the length, or, more accurately, space, is working together with time to keep the speed of light a universal constant. In the special theory of relativity, length contraction and time dilation maintain the speed of light at a constant. They also conserve Lorentz invariance. Diagram 1 shows very clearly that the equations of the special theory of relativity depend on one another. Therefore, any change in one of them will lead to a change in all other equations. We derived the new equation of energy; the energy of photons, they are treated as particles, can decrease. We then showed, as derived by Agashe, that the length of a rod can expand or remain invariant, and length expansion is consistent, in principle, with the equation of decreasing energy. Because of this consistency, the proper velocity, the relativistic momentum and all other dynamical quantity must exist. However, the most bizarrely affected quantity is the time. If equation (1.41) is correct and is applied to the length of a rod, time or the clocks used to measure it must be speeding up! We can easily demonstrate the truth of this statement. Consider again (fig. 1), and suppose that there is a particle the frame ′ with a mean lifetime . If equation (1.41) is correct, the length of the rod in frame will expand to In this case, however, to the observer in the particle frame, all space behind the observer will appear to expand according to equation (1.46), not just the rod in frame . Thus, if the time interval between two events as measured in the particle frame ′ is , it will be different in frame . In this frame, the length will not change, so the particle will occupy a smaller distance than in frame ′ , but the two observers must agree on the time at which the particle disappears. For this to happen, there is only one possibility: time must speed up in frame ′ relative to frame ! This means that the equation for the time interval must reverse in frame to obtain the same result for the two reference frames. Therefore, for , time must obey this equation:

Of course, time also speeds up in frame relative to frame ′ . The two equations (1.46) and (1.47) will leave the speed of light, universally, constant, and they satisfy Lorentz invariance and the laws of physics.

In conclusion, we can say that if photons have a mass, albeit a very tiny one, there will be many surprising consequences at the theoretical level. A nonzero photon mass would allow the photon to have a mean lifetime and to decay to lighter particles! If the photon really has a mass and a mean lifetime and if the equations (1.23), (1.46) and (1.47) are correct, using some experimental arrangement that simulates Fig 1, one could verify that time speeds up for the photon and that its energy decreases. Of course, it is very difficult to verify equation (1.46) because there is no direct evidence of length contraction, but we know that it must occur to be consistent with time dilation. The same logic applies for these new results: evidence of one of them is sufficient to know that the others must also be correct.

This model may apply only for photons because of the dual nature of the photon. Space-time, according to this model, does not exhibit only spatial contraction accompanied by time dilation but also spatial expansion accompanied by time speeding up. Space-time may be very elastic. It may be able to contract and expand in both length and time to leave the speed of light universally constant.

Fig. 1

 1 Fig. 1

Fig. 2

 2 Fig. 2

Table 1 Author (date) Experimental approach Upper limit on / g

 1

	Terrestrial results
	Goldhaber et al. (1971)	Speed of light
	Williams et al. (1971)	Test of Coulomb's law
	Chernikov et al. (1992)	Test of Ampere's law
	Lakes (1998)	Static torsion balance
	Luo et al. (2003)	Dynamic torsion balance
	Extraterrestrial results
	De Broglie (1940)	Dispersion of starlight
	Feinberg (1969)	Dispersion of starlight
	Schaefer (1999)	Dispersion of gamma-ray
		bursts
	Davis et al. (1975)	Analysis of Jupiter's magnetic
		field
	Fischbach et al. (1994)	Analysis of Earth's magnetic
		field
	Ryutov (1997)	Solar wind magnetic field and
		plasma
	Gintsburg (1964)	Altitude dependence of
		geomagnetic field
	Patel (1965)	Alfvén waves in Earth's
		magnetosphere
	Hollweg (1974)	Alfvén waves in the
		interplanetary medium
	Barnes et al. (1974)	Hydromagnetic waves
	DeBernadis et al. (1984)	Cosmic background radiation
	Williams et al. (1971)	Galactic magnetic field
	Chibisov (1976)	Stability of the galaxies


Marek Zawirski

Sérgio Duarte

Carlos Baquero

Marc Shapiro

SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine

Keywords: geo-replication, causal consistency, transactional causal+ consistency, eventual consistency, fault tolerance géo-réplication, cohérence causale, cohérence transactionnelle causale+, cohérence finale, tolérance aux pannes

Client-side logic and storage are increasingly used in web and mobile applications to improve response time and availability. Current approaches tend to be ad-hoc and poorly integrated with the server-side logic. We present a principled approach to integrate client-and server-side storage. We support mergeable and strongly consistent transactions that target either client or server replicas and provide access to causally-consistent snapshots efficiently. In the presence of infrastructure faults, a client-assisted failover solution allows client execution to resume immediately and seamlessly access consistent snapshots without waiting. We implement this approach in SwiftCloud, the first transactional system to bring geo-replication all the way to the client machine. Example applications show that our programming model is useful across a range of application areas. Our experimental evaluation shows that SwiftCloud provides better fault tolerance and at the same time can improve both latency and throughput by up to an order of magnitude, compared to classical geo-replication techniques.

Introduction

Cloud computing infrastructures support a wide range of services, from social networks and games to collaborative spaces and online shops. Cloud platforms improve availability and latency by geo-replicating data in several data centres (DCs) across the world [START_REF] Baker | Megastore: Providing scalable, highly available storage for interactive services[END_REF][START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF][START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF][START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF][START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF][START_REF] Thomson | Calvin: fast distributed transactions for partitioned database systems[END_REF]. Nevertheless, the closest DC is often still too far away for an optimal user experience. For instance, round-trip times to the closest Facebook DC range from several tens to several hundreds of milliseconds, and several round trips per operation are often necessary [START_REF] Wittie | Exploiting locality of interest in online social networks[END_REF]. Recall that users are annoyed when interactive latency is above 50 ms [START_REF] Jay | Modeling the effects of delayed haptic and visual feedback in a collaborative virtual environment[END_REF] and increased values turn them away [START_REF] Schurman | Performance related changes and their user impact[END_REF]. Furthermore, mobile clients may be completely disconnected from any DC for an unpredictable period of minutes, hours or days.

Caching data at client machines can improve latency and availability for many applications, and even allow for a temporary disconnection. While increasingly used, this approach often leads to adhoc implementations that integrate poorly with server-side storage and tend to degrade data consistency guarantees. To address this issue, we present SwiftCloud, the first system to bring geo-replication all the way to the client machine and to propose a principled approach to access data replicas at client machines and cloud servers.

Although extending geo-replication to the client machine seems natural, it raises two big challenges. The first one is to provide programming guarantees for applications running on client machines, at a reasonable cost at scale and under churn. Recent DC-centric storage systems [START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF][START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF][START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF] provide transactions, and combine support for causal consistency with mergeable objects [START_REF] Shapiro | Conflict-free replicated data types[END_REF]. Extending these guarantees to the clients is problematic for a number of reasons: standard approaches to support causality in client nodes require vector clocks entries proportional to the number of replicas; seamless access to client and server replicas require careful maintenance of object versions; fast execution in the client requires asynchronous commit. We developed protocols that efficiently address these issues despite failures, by combining a set of novel techniques.

Client-side execution is not always beneficial. For instance, computations that access a lot of data, such as search or recommendations, or running strongly consistent transactions, is best done in the DC. SwiftCloud supports server-side execution, without breaking the guarantees of client-side in-cache execution.

The second challenge is to maintain these guarantees when the client-DC connection breaks. Upon reconnection, possibly to a different DC, the outcome of the client's in-flight transactions is unknown, and state of the DC might miss the causal dependencies of the client. Previous cloud storage systems either retract consistency guarantees in similar cases [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF][START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF][START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF], or avoid the issue by waiting for writes to finish at a quorum of servers [START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF], which incurs high latency and may affect availability.

SwiftCloud provides a novel client-assisted failover protocol that preserves causality cheaply. The insight is that, in addition to its own updates, a client may observe a causally-consistent view of stable (i.e., stored at multiple servers) updates from other users. This approach ensures that the client's updates are not delayed, and that the client's cached state matches the new DC, since it can replay its own updates and the others are known to the DC.

We evaluate our protocols experimentally, and compare them with a classical geo-replication approach. The experiment involves three data centres in two continents, and hundreds of remote clients. Under sufficient access locality, SwiftCloud enjoys order-of-magnitude improvements in both response time and throughput over the classical approach. This is because, not only reads (if they hit in the cache), but also updates commit at the client side without delay; servers only need to store and forward updates asynchronously. Although our fault tolerance approach delays propagation, the proportion of stale reads remains under 1%.

The contributions of this paper are the following:

• The design of a cloud storage system providing geo-replication up to the client nodes.

• The design of scalable, efficient protocols that implement the Transactional Causal+ Consistency model, in a system that includes replicas in the client nodes and in the servers. • Fault-tolerant techniques for ensuring Transactional Causal+ Consistency guarantees, without adding latency to operations. • An application study that shows the approach is useful in practice, and reveals where it falls short. • An experimental evaluation of the system, with different applications and scenarios.

System overview

SwiftCloud is a data storage systems for cloud platforms that spans both client nodes and data center servers (DCs), as illustrated in Figure 1. The core of the system consists of a set of data centres (DCs) that replicate every object. At the periphery, client nodes cache a subset of the objects. If the appropriate objects are in cache, responsiveness is improved and a client node supports disconnected operation.

Programming model

SwiftCloud provides a straightforward key-object API, presented in Figure 2. Applications running in the client can execute sequences of read and update operations, grouped into transactions. Transactions can provide either strong or weak consistency, as discussed next.

A client can request the execution of a stored transaction in the data server. A stored transaction is similar to a stored procedure in a database system, and can return a set of objects. Whereas a stored transaction runs completely in the server, a client-side transaction contacts the server only if there is a cache miss. We expect that common operations will execute asynchronously in the client cache, and that stored transactions and strongly-consistent transactions will be rare. For example, in a social networking application, the user's wall, and those of his friends, can be served directly in the cache, while computing recommendations, which requires accessing a huge number of objects, will be implemented as a stored transaction.

Transactional model

This section outlines our transactional model, Transactional Causal+ Consistency. Intuitively, it offers the following guarantees: every transaction reads a causally consistent snapshot; updates of a transaction are atomic (all-or-nothing) and isolated (no concurrent transaction observes an intermediate state); and concurrently committed updates do not conflict. At the heart of Transactional Causal+ Consistency is the guarantee that state never goes back in time: once a client has read an object version that reflects some update, it cannot observe a state where that update was not applied. As an example, when user A adds friend B to her social network, and later posts something, if B later sees the post, she will also observe that she is A's friend. This example is illustrated by T 1 and T 6 in Figure 3.

Formally, we define a potential causality relation on operations (augmenting the definition of Lloyd et al. [START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF] with transactions):

1. Execution Thread. If a and b are two operations invoked by the same client, and a occurs before b, then a b. 2. Gets From. If u is an update and r is a read that returns the value written by u, then u r. An execution of a system satisfies Transactional Causal+ Consistency if: 1. Every transaction observes a valid snapshot and its own updates: all reads of a transaction observe a state that includes all updates from the same set of committed transactions, and earlier updates of its own transaction, applied in a sequence that is a linear extension of . 2. Every snapshot is causally consistent: the set of observed updates is transitively closed over and includes at least all updates committed earlier in . For instance, after B observes she is a friend of A and C, she cannot observe that she is friend of A only, since successive reads depend on the read that showed B as friend of both A and C.

Note that this weak definition allows different clients to observe the same set of concurrent updates applied in different orders, which poses a risk of yielding different operation outcomes on different replicas or at different times. We address this problem by disallowing non-commutative (order-dependent) concurrent updates. Practically, we enforce this property with two different types of transactions, akin to the model of Walter [START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF] or Red-Blue [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF]:

1. Mergeable transaction can update only objects with commutative operations and always commit.

2. Classic, non-mergeable transaction can perform non-commutative operations, but among concurrent transactions with conflicting updates at most one can successfully commit.

Mergeable transactions

The focus of this paper is the efficient and fault-tolerant support of mergeable transactions, i.e., transactions with updates that commute with all other updates. Mergeable transactions commute with each other and with non-mergeable transactions, which allows to execute them immediately in the cache, commit asynchronously in the background, and remain available in failure scenarios. Read-only transactions are a simple case of mergeable transactions. Concurrent updates are more difficult to handle and often complicated to merge, with many existing systems relying on questionable heuristics, such as last-writer-wins [START_REF] Johnson | The maintenance of duplicate databases[END_REF][START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF][START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF]. Our approach is to permit concurrent update transactions on dedicated mergeable objects. Mergeable data types include last-writer-wins registers, the multivalue registers of Dynamo [START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF], the C-Set of Sovran et al. [START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF], and a number of higher-level Conflict-free Replicated Data Types (CRDT) of Shapiro et al. [START_REF] Shapiro | Conflict-free replicated data types[END_REF][START_REF] Shapiro | Convergent and commutative replicated data types[END_REF]. CRDTs include a rich repertoire of high-level objects, such as replicated counters, sets, maps, graphs, and sequences.

CRDTs encapsulate common concurrency and replication complexity and allow to solve them at the system level once for all. However, real application require either complex custom objects or using multiple objects. The former is impractical, whereas the latter raises new issues, lacking cross-object guarantees [START_REF] Conway | Logic and lattices for distributed programming[END_REF]. Our transactional model introduces simple cross-object ordering guarantees and allows to compose multiple objects in applications. Examples in Section 5 suggest that for many applications mergeable transaction can express the dominant part of the workload. For stronger guarantees, nonmergeable transactions can be used.

Classic, non-mergeable transactions

SwiftCloud supports the traditional strongly-consistent transaction model, in which non-commuting concurrent updates conflict (as determined by an oracle on pairs of updates) and cannot both commit. This primitive allows to implement arbitrarily difficult tasks, e.g., to build atomic registers and enforce strong data invariants when necessary. Inria 3 Algorithms for transactions

Non-mergeable transactions

Non-mergeable transactions execute as stored procedures on the server side. We implement a simple read-one/write-all protocol, using two-phase commit to guarantee that no conflicting concurrent update has previously committed. The commit protocol could be replaced by Paxos Commit [START_REF] Gray | Consensus on transaction commit[END_REF] for improved fault-tolerance.

Mergeable transactions

We present the algorithms used to implement mergeable transactions, first in the failure-free case, and later (in Section 4) in the presence of failures. We assume a classical sequential model where a client executes a single transaction at a time, i.e., a replica has a single thread of execution. Applications interface to the system via a local module called scout; we assume for now that it connects to a single DC. For client-side transactions, the scout is located in the client machine; for stored transactions, the code and the scout both run in the DC.

An application issues a mergeable transaction by interactively executing a sequence of reads and updates, and concludes the transaction with either a commit or rollback. Reads are served from the local scout; on a cache miss, the scout fetches the data from the DC. Updates execute in a local copy. When a mergeable transaction terminates, its updates are applied to the scout cache. Eventually, they will also be committed at its DC. The DC eventually propagates the effects to other DCs and other scouts scouts as needed.

System state

The system ensures the invariant that every node (DC or scout) maintains a causally-consistent set of object versions. A DC replicates all objects (full replication). The DC keeps several recent versions of an object, in order to serve the versions requested by scouts on behalf of their transactions. Old versions can be pruned, i.e., discarded, without impacting correctness.

Each DC maintains a vector clock V DC that summarizes the set of transactions that it has processed. At DC i , entry V DC i [i] counts the number of transactions that DC i committed. Any other entry V DC i [ j] counts the number of transactions committed by DC j that DC i has processed. V DC i ≤ V DC j means that DC i processed a subset of the transactions processed by DC j .

A scout S maintains a vector clock V * S that summarises the transactions reflected by the most recent version of cached objects. V * S includes one entry for each DC, plus an additional entry for the transactions locally committed at S. We denote with V S the same vector clock restricted to the entries for DCs.

At all times, the globally-committed update transactions observed by a scout are a subset of those known by its DC, i.e., V S ≤ V DC . This invariant is obvious in the failure-free case; Section 4 explains how we maintain it in the presence of failures.

Transaction execution at scout

An applications starts a transaction by executing begin. This allocates a vector clock D * T that summarises the causal dependencies of the transaction. It is set by default to the current state of the scout: D * T := V * S . Concurrently, while the transaction executes, V * S increases as S processes committed transactions but D * T does not change. Thus, D * T ≤ V * S is an invariant. begin operation also generates the transaction's Origin Transaction IDentifier (OTID), composed of a monotonically-increasing timestamp and the unique scout identifier. Figure 4 illustrates transaction execution with the run of transaction T 3 (from Figure 3). We will use this as a running example throughout Primitives read and multi_read of the SwiftCloud API, read one or several objects respectively. They return a version of the requested object(s) that satisfies the rules of Transactional Causal+ Consistency. If the corresponding version is not found in the cache, it is fetched from the DC. multi_read is an optimization that allows to fetch multiple missing objects in a single round-trip. If the corresponding version has been pruned away, the read fails, and the client has the option of continuing or aborting the transaction with no effect. update is called when an operation is executed on a previously read object. In our running example, T 3 reads C.frd from the cache but needs to fetch B.frd from the DC before updating it. As D * T = [0, 0|0], the version fetched from the DC still does not include the updates from T 1 , thus having B.frd = {}.

C.frd={} B.frd={} V * S =[0 0|0] A.frd={B} B.frd={A} V DC0 =[1 0] C.frd={} V * S =[0 0|0] C.frd={B} B.frd={C} V * S = [0 0|1] A.frd={B} B.frd={A,C} V DC0 =[ 2
Reads and updates execute against the local copies returned by read/multi_read. Update operations log their effect using the update primitive, so that later, the updates can be transmitted to other replicas.

Our mergeable transactions are interactive, i.e., read sets and write sets are determined on the fly by the transaction's control flow. This enables, for instance, a user to display a consistent view of the network of her friends. This would be difficult in a system with non-interactive transactions such as COPS [START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF] or Eiger [START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF], since the data to browse is not known until the transaction reads the user's friend set.

When a mergeable transaction terminates successfully at the scout, it commits locally. If the transaction was read-only, the story stops there. Update transaction logs its updates (if any) to durable storage, and updates scout S's own entry in V * S with the timestamp part of the transaction's OTID. The application may start a new transaction immediately. Otherwise, its updates are now visible to later transactions at the same scout. In the example of Figure 4, at the end of T 3 , we can see the cache with the updated value for B. f rd and C. f rd and the new value of V * S = [0, 0|1], reflecting the OTID of T 3 . The scout globally-commits the mergeable transaction by sending asynchronously the transaction's OTID, D * T and updates to its DC. This asynchronous commit creates a durability issue, which we discuss in Section 4. We expose the durability status of a transaction in the API so that the application can make use of this information, as suggested by Kraska et al. [START_REF] Kraska | MDCC: Multi-data center consistency[END_REF].

Transaction commit at the DC

When a mergeable transaction is received in a DC, the DC first checks if it satisfies the transaction's dependencies. As long as the scout connects to the same DC, and the connection is FIFO, this will be necessarily the case, since D T ≤ V S ≤ V DC , where D T is the restriction of D * T to only DC entries. If not, Inria the protocol waits until dependencies are satisfied.

Globally-committing a transaction by DC i consists of the following steps: assign it a Global Transaction IDentifier (GTID) (k, DC i ) such that k = V DC i [i] + 1, log its commit record and update the DC replicas, and finally increase V DC i [i] to k, thus making the transaction visible. The commit record contains the transaction's dependence vector D * T , its OTID, its effects, and its GTID. In our running example, T 3 is assigned GTID = (2, DC 0 ), and V DC 0 = [2, 0] is updated accordingly. The set of friends of B is updated by merging the new update into the DC version, by making B.frd = {A,C}.

Later, the DC sends the transaction commit record to other DCs using epidemic propagation [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF]. A receiving DC logs the record durably, and if dependencies are satisfied, it applies the updates to the DC replicas and updates its vector clock. Otherwise, the DC delays processing the transaction until the dependencies are satisfied.

Discussion

A globally-committed mergeable transaction (and the object versions that it generates) is identifiable by both its OTID and GTID. The OTID ensures uniqueness, and the GTID allows to refer to a transaction efficiently in a dependence vector. In some failure cases, a transaction may be assigned multiple GTIDs, but as explained in the next section, they are treated equivalently.

Our protocol encodes the causal status of a whole node (DC or scout) with a vector clock. The scout-DC topology, the small and static number of DCs, and the assumption that transaction processing in a DC is linearisable, all contribute to keeping these vectors small. This very compact data structure summarises the whole past history, i.e., the transitive closure of the current transaction's dependence.

Cache maintenance

A scout maintains a cache containing replicas of a subset of objects (partial replication). An application may ask to pin an object in the cache; otherwise, the scout manages its cache with an LRU policy. The cache may be updated, either as the result of a local transaction commit, or because the cache is notified of a global commit by its DC. A cache is always updated as the result of executing a stored transaction.

The partially replicated subset is guaranteed causally consistent, but not necessarily complete. For instance, assume the following update causal dependencies: a b c; a scout might maintain only objects corresponding to a and c. If a version (in this example, installed by update b) is missing in the cache, it will be fetched from a DC, in accordance to the current transaction's snapshot.

The scout processes global-commit records in causal order and atomically, ensuring that every state satisfies Transactional Causal+ Consistency. The scout may either receive a full update on a cached object modified by the transaction, in which case it installs a new version or just an invalidation. A scout does not need to receive an update for an object that is not cached; if it does, it is treated as a no-op.

Implementation issues

Stored mergeable transactions: Stored mergeable transactions execute using the same approach as transactions executed in the scout, with the difference that transactions access directly the replicas in the data centre and that the clock of the data centre is used as the snapshot vector.

Scaling transaction processing: The transaction processing process in the DC is linearisable as whole and our DC implementation is parallel internally. Data is partitioned across multiple storage nodes, and client requests are processed by multiple proxy nodes. Multiple global-commits can proceed concurrently. It is only the update of the DC's vector clock that needs to be linearised, since this is the step that renders a transaction visible.

A sequencer module at the DC sequentially assigns transaction identifiers. This could become a performance bottleneck as well as a central point of failure. Fault-tolerance can be improved by replicating the sequencer, for instance by using chain replication [START_REF] Van Renesse | Chain replication for supporting high throughput and availability[END_REF] with a short chain. To improve performance, there could be more than one sequencer in each DC, at the expense of larger vectors.

Security: SwiftCloud caches objects and generates updates in the clients. This poses no new major security threat, with access control enforcement at the cloud boundaries addressing the problem.

SwiftCloud does not pose much of new challenges w.r.t. tolerating Byzantine clients. Incorrect operations can be tolerated similarly as in classic server-backed systems. Forged dependence vector of a transaction cause no harm to other transactions, same as client sending a wrong OTID (e.g., using the same OTID twice), as long as the DC keeps track of GTIDs and a summary of updates related to the OTID to detect it.

Fault-tolerant session and durability

We discuss now how SwiftCloud handles network, DC and client faults, focusing on client-side mergeable transactions. Our focus is primarily on our main contribution, mergeable transactions executing on the client side; we mention other cases briefly.

At the heart of mergeable transactions is causal consistency (i.e., session guarantees [START_REF] Brzeziński | From session causality to causal consistency[END_REF][START_REF] Terry | Session guarantees for weakly consistent replicated data[END_REF]), which is easily ensured in the failure-free case, since DCs exchange transactions using causal broadcast, a DC commits a single transaction at a time, and a scout connects to a single DC over a FIFO channel. However, when a scout loses communication with its current DC, due to network or DC failure, the scout may need to switch over to a different DC. The latter's state is likely to be different, and it might have not processed some transactions observed or indirectly observed (via transitive causality) by the scout. In this case, ensuring that the clients' execution satisfies the consistency model and the system remains live is more complex. As we will see, this also creates problems with durability and exactly-once execution.

As a side-effect of tolerating DC faults and fail-over, our protocols also support client disconnection. Obviously, if a disconnected client requires state that is not currently cached, it cannot make progress. Similarly, if the client remains permanently disconnected or loses its durable state before reconnecting, there is not much that can be done. However, in-cache disconnected operation is supported "for free," as long as the scout remains live and eventually reconnects.

Durability and exactly-once execution issue

The scout sends each transaction to its DC to be globally-committed, to ensure that the DC stores it durably, allocates a GTID, and eventually transmits it to every replica. If it does not receive an acknowledgment, it must retry the global-commit, either with the same or with a different DC. However, the outcome of the initial global-commit remains unknown. If it happens that the global commit succeeded with the first DC, and the second DC allocates a second GTID, the danger is that the transaction's effects could be applied twice under the two identities.

For some data types, this is not a problem, because their updates are idempotent, for instance put(key,value) in a last-writer-wins map. For other mergeable data types, however, this is not true: think of executing increment(10) on a counter. Systems restricted to idempotent updates can be much simpler [START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF], but in order to support general mergeable objects with rich merge semantics, SwiftCloud must ensure exactlyonce execution.

In principle, the DC could check that the transaction's unique OTID does not appear in the log. Unfortunately, this is insufficient, since the log might be pruned while a scout was disconnected (e.g., during a long journey).

Inria

Causal dependency issue

When a scout switches to a different DC, the state of the new DC may be unsafe, because some of the scout's causal dependencies are missing. For instance, in Figure 1, suppose that transaction (23, DC 2 ) created some object, and later, the Paris scout updates that object. Vector clock V DC O [2] = 22 reveals that DC 0 has not yet processed the creation transaction. Therefore, committing the update transaction to DC 0 would lead DC into an unsafe state. Unless the scout can find another DC that has processed all the transactions that it depends upon, its only option is to wait until DC 0 receives (23, DC 2 ). This might take a long time, for instance if DC 2 (which committed the missing transaction) is unavailable.

Before presenting our solution in the next section, let us consider some possible approaches. Some geo-replication systems avoid creating dangling causal dependencies by making synchronous writes to multiple data centres, at the cost of high update latency [START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF]. Others remain asynchronous or rely on a single DC, but after failover clients are either blocked like in our example (unavailability) or they violate causal consistency [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF][START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF][START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF]. The former systems trade consistency for latency, the latter trade latency for consistency or availability.

An alternative approach would be to store the dependencies on the scout. However, since causal dependencies are transitive, this might include a large part of the causal history and a substantial part of the database. 1 It would be similar to a peer-to-peer system, every scout being a first-class full replica, with its own component in vector clocks. Traffic and storage requirements would be unbearable in this case.

Finally, a trivial solution would be for a client to observe only its own updates. This would ensure safety but, lacking liveness, would not be useful. To exclude such trivial implementations, we impose the convergence requirement that a client eventually observes all committed updates. Such a relatively weak property does not preclude serving the client with an old safe version, the freedom we use in our approach.

Fault-tolerant causal consistency

Our approach is to make scouts co-responsible for the recovery of missing session causal dependencies at the new DC. Since, as explained earlier, a scout cannot keep track of all transitive dependencies, we restrict the set of dependencies. We define a transaction to be K-durable at a DC, if it is known to be durable in at least K DCs, where K is a configurable threshold. Our protocols let a scout observe only the union of: (i) its own updates, in order to ensure the "read-your-writes" session guarantee [START_REF] Terry | Session guarantees for weakly consistent replicated data[END_REF], and (ii) the K-durable updates made by other scouts, to ensure other session guarantees, hence causal consistency. In other words, the client depends only on updates that the scout itself can send to the new DC, or on ones that are likely to be found in a new DC. The set of K-durable updates is causally consistent, i.e., it is transitively closed over the relation. When failing over to a new DC, the scout helps out by checking whether the new DC has received its recent updates, and if not, by repeating the commit protocol with the new DC.

The scout can switch to a DC, as long as this new DC ensures that the scout continues to observe a monotonically-growing set of K-durable updates. This is possible, since the scout's own updates that are not K-durable cannot depend on updates from another scout that are themselves not K-durable.

SwiftCloud prefers to serve a slightly old but K-durable version, instead of a more recent but more risky version. Instead of the consistency and availability vs. latency trade-off of previous systems, Swift-Cloud trades availability for staleness. Since our system relies on gossiping between DCs, to some extent, the larger the parameter K, the higher the probability that an update that is K-durable at some DC will be found K-durable in another random DC. However, higher values of K cause updates to take longer to become visible and may increase the risk that an update is blocked by a network partition. On the other hand, lower values may increase the chance that a scout will not be able to find a suitable DC to fail-over to. In particular, K = 1 corresponds to the original blocking session-guarantees protocol of Terry et al. [START_REF] Terry | Session guarantees for weakly consistent replicated data[END_REF].

In practice, K ≥ 2 is a good compromise, as it ensures session guarantees without affecting liveness in the common case of individual DC failures or disconnections [START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF]. Our implementation uses K = 2, tolerating a single fault. A better approach might be K = 3, to tolerate a single fault when a DC is closed for scheduled maintenance [START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF].

By delaying visibility, rather than delaying writes like some previous works, we move the cost of causal consistency from the domain of commit-time latency, into the domain of data staleness. Our evaluation in Section 6 shows that our approach improves latency, with a negligible impact on staleness. The staleness increases concurrency of updates in the system, which is tolerable, since SwiftCloud uses mergeable objects to handle that seamlessly.

Discussion

Mahajan et al. [START_REF] Mahajan | Consistency, availability, and convergence[END_REF] establish that causal consistency2 is the strongest achievable consistency in an alwaysavailable convergent system. The practical problem of ensuring similar guarantees in the presence of partial replicas, or of clients switching servers, was not addressed before. We demonstrated how to ensure Transactional Causal+ Consistency for clients under this new assumption, at the price of weaker liveness property.

Fault-tolerant exactly-once execution

We now address the remaining issue of ensuring that each update is delivered exactly once at each replica, a problem that arises with any commit protocol that allows retries. Simply repeating the global-commit protocol until the scout receives an acknowledgment takes care of one half of the problem, i.e., at-leastonce delivery. We now consider the other half, eliminating duplicates in the presence of failures and pruning.

Our approach separates the concerns of tracking causality and of uniqueness, following by the insight of Preguiça et al. [START_REF] Preguiça | Brief announcement: Decoupling version identification from causality tracking information in distributed storage systems[END_REF]. Recall (Section 3.2.4) that a transaction has both a client-assigned OTID, and one or more DC-assigned GTIDs. The OTID identifies it uniquely, whereas a GTID is used when a summary of a set of transactions is needed. Whenever a scout globally-commits a transaction at a DC, and the DC does not have a record of this transaction already having a GTID, the DC assigns it a new GTID. This approach makes the system available, but may assign several GTID aliases for the same transaction. All alias GTIDs are equivalent in the sense that, if updates of T ′ depend on T , then T ′ comes after T in the causality order, no matter what GTID T ′ uses to refer to T .

When a DC processes a commit record for an already-known transaction with a different GTID, it adds the alias GTID to its commit record on durable storage.

To provide a reliable test whether a transaction is already known, each DC maintains durably a map of the last OTID received from each scout, noted maxOTID i [S] for scout S and DC i . 3 Thanks to causal consistency, maxOTID i [S] is monotonically non-decreasing.

When a DC i receives a global-commit message from scout S, it checks that its OTID is greater than maxOTID i [S]; if so, it allocates a new GTID, logs the commit record, and returns the GTID to the scout. If it is not greater, this means that this transaction has already been delivered to this DC. In this case, the DC searches its log for a commit record with the same OTID. If one is found, the DC returns the corresponding GTID to the scout.

Otherwise, this means that the commit record has been pruned. This raises the question of how the client will refer to the transaction in causal dependencies of subsequent transactions. It turns out this is not necessary: as only transactions that were processed by all DCs are pruned, such dependencies will be always satisfied; therefore, a null GTID is returned to the client.

Note that scouts do not need to worry about exactly-once delivery, since a scout will communicate with a DC only if the latter has processed a superset of the K-durable transactions that the scout has observed.

Fault tolerance on server-side

The fault tolerance algorithm just described is not directly applicable to update transactions executing on the server (DC) side, issued by exec_stored_proc call. We discuss briefly possible fault tolerance options here; these were not implemented in our prototype.

In the case of non-mergeable transactions, it is sufficient to tag a request with OTID and eliminate duplicate execution using existing concurrency-control, treating duplicates as concurrent conflicting transactions.

A similar technique can be applied to mergeable transactions executing on the server-side. In this case, however, the OTID is augumented with a dependency vector D * T . As long as client uses the same OTID and D * T for reissued transaction requests and the transaction processing is deterministic w.r.t. a database version, duplicate execution of the transaction can only result in producing updates with the same identity, which is addressed by the technique in Section 4.4.

Building applications

The SwiftCloud approach is designed to fit best applications with sufficient locality to run in a small cache even if the total database size is large, and that use mergeable transactions mostly. We demonstrate the applicability of our application and consistency model by implementing a range of applications that meet these characteristics. Evaluating the performance of these applications is the focus of Section 6.

SwiftSocial social network

The SwiftSocial application is our port of WaltSocial, a simple social network prototype [START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF]. The port was straightforward, using the data types from the CRDT library and transactions. The SwiftSocialspecific code consists of approximately 680 Java LOC with few comments.

SwiftSocial maps (using a CRDT map) a user to his profile information (a LWW-Register) and to set CRDTs containing his wall messages, events, and friendship requests. The event set records every action involving the user, and thus grows linearly in the number of updates.

Update transaction types include registering a user, login (fetches the user's profile and checks his password; subscribes to updates), logout (unsubscribes), posting a status update on the user's wall, and sending a message to another user's wall or accepting friendship request. Read-only transactions view another user's wall, or list his friends. The workloads used in Section 6 consist of user sessions running a mix of these transactions.

Transaction's atomicity ensures that accepting a friendship request updates both users' friendship sets consistently or a notification event is added together with a wall post. Causality naturally helps user-experience, for example when a user follows a conversation thread, replies appear after the original messages. It also helps programming in some cases, since, in the same case, reply to a message does need to be processed (e.g. rendered) without a message.

We found that only the user registration transaction should preferably be of a non-mergeable type, in order to name users uniquely. A more advanced social network application could benefit from some server-side procedures, e.g., for searching user, content or suggesting advertisements.

SwiftDocs collaborative documents

Collaboration tools are typical applications that benefit from low-latency, highly-available client-side access to data, including offline. Our SwiftDocs application implements a mergeable file-system hierarchy with mergeable file types that allows to share documents and edit them concurrently. SwiftDocs subsumes some of the functionality of a DVCS like Git or Mercurial, and of online collaborative editors such as Google Docs.

SwiftDocs consists of a naming tree of directories, implemented using CRDT map objects. A directory maps unique keys, which are strings of the form name ! type, to objects of arbitrary CRDT type. This hierarchical structure provides a variety of semantically different data objects for collaboration. For instance, foo.txt ! lww refers to a file managed as untyped blob with LWW-Register semantics, whereas foo.txt ! seq is a text file with fine-grained automatic merging of updates, managed as a conflict-free sequence [START_REF] Weiss | Logoot-undo: Distributed collaborative editing system on P2P networks[END_REF]. A family can edit their family tree without conflict by storing it as a CRDT object of type graph, e.g., The_Simpsons_family_tree ! graph.

Transactions ensure consistency across multiple object and updates. For instance, a user might snapshot a subtree, perform updates throughout it (e.g., replace the word "SwiftCloud" in all files with another name), copy it to a different place, and delete the original, all as a single transaction.

Concurrent updates are merged using the following heuristic. Concurrently creating and populating two directories under the same name takes the union of elements; elements with the same name ! type are merged recursively. The semantics of merging two files is given by the merge method of their type. Embedding the type in the lookup key ensures that only files of the same type are merged.

Removing a directory recursively calls the remove interface of its elements. If remove is concurrent with another user's update, remove wins and update is lost. However, the second user's work can be accessed by recreating a snapshot that does not include the deletion. Furthermore, she can reinstate the missing file under its original unique key using a version of create().

The move operation is implemented as a mergeable transaction that takes a snapshot of the source subtree, copies it recursively, then recursively removes the source subtree. Anomalies may occur if the source is modified concurrently. To implement the Posix rename semantics, re-linking a subtree at a different location, would require using a classical serialisable transaction; otherwise cycles might appear [START_REF] Bjørner | Models and software model checking of a distributed file replication system[END_REF].

SwiftDocs operations exhibit good locality: caching a subtree and a global map may be often sufficient for good latency and disconnected support.

TPC-W benchmark

The TPC-W benchmark simulates an online book store. Simulated clients browse items, interact with shopping carts, and check out. We ported an existing open-source Java implementation [START_REF] Gomes | TPC-W benchmark[END_REF] to Swift-Cloud. Our objectives were to demonstrate porting an existing application, and to provide the reader of this paper with a familiar point of reference.

Transactions are essential in TPC-W but most can be mergeable, with checkout being an exception that needs synchronous execution in the DCs. Checkout atomically pays for, and adjusts the stock of, each item in the shopping cart.

We model TPC-W database with CRDTs. For instance, a CRDT set represents the shopping cart, thus avoiding the anomalies of the Amazon shopping cart [START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF]. We index product records using CRDT sets. A CRDT counter is used to track the stock of each item. The benchmark specification allows stock to Inria become negative, as long as is eventually replenished. If desired, enforcing non-negative stock could be achieved by using non-mergeable transactions.

TPC-W can display some problems when naively ported to being executed at the edge. Namely, operations involving large read sets, such as queries to the whole product database, tend to perform poorly in the client cache. SwiftCloud can tackle this sort of issue by leveraging stored transactions.

Evaluation

This section presents an experimental evaluation of SwiftCloud based on the applications described in the previous section. The aim of this study is to assess the relative strengths and weaknesses of executing application logic at the two opposite ends provided by the SwiftCloud platform. Namely, we will compare our caching approach, executing both reads and updates at the client, against the standard approach of doing updates in the DC. As such, the horizontal scalability of DCs is not evaluated; in fact, all the (parallel) components of a SwiftCloud DC run on a single server in these experiments.

Experimental setup

SwiftCloud is written in Java. Approximate code sizes, including javadoc, are as follows: whole system, 20K LOC; DC-specific, 3.5K LOC; scout-specific, 3K LOC; CRDT library 5K LOC. It runs over a preexisting communication, serialisation, and DHT package of approximately 12K LOC. Durable state is stored in a Berkeley DB database.

We run DCs in three Amazon EC2 availability zones, and clients on 96 PlanetLab machines located geographically near the DCs. Figure 5 describes their approximate geographical locations and round-trip times (RTTs). EC2 machines are equivalent to a single core 64-bit 2.0 GHz Intel Xeon virtual processor (2 ECUs) with 3.75 GB of RAM and run Java OpenJDK 64-bit IcedTea7 (Server) above Linux 3.2. Plan-etLab nodes have heterogeneous specifications and latencies. We use default system settings throughout.

We compare configurations with one DC (Ireland), two (+ Oregon) and three DCs (+ North Virginia). Within an experiment, we vary parameters but keep constant the set of PlanetLab nodes. We vary the number of clients by adding more independent client threads per PlanetLab node, thus keeping the network latency distribution invariant.

A state-of-the-art geo-replication configuration is achieved by co-locating SwiftCloud scouts (with a cache size set to zero) within the DC. Its non-fault-tolerant "Cloud-noFT" configuration performs its updates at a single DC synchronously, and propagates them asynchronously to the others. The "Cloud-FT" configuration writes to two DCs synchronously, simulating disaster-tolerant geo-replication systems such as a configuration of Walter [START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF].

In the fault-tolerant "SwiftCloud" configurations, each client thread has a co-located scout, with a dedicated cache size of 512 objects, and uses the asynchronous global-commit protocol. In the alternative "SwiftCloud-naiveFT" configuration, commit is synchronous and returns only when durable in at least two DCs.

All configurations evaluated, including Cloud-FT and Cloud-noFT, leverage the same codebase. They represent the extremes of the SwiftCloud system application logic distribution spectrum. The Cloud-FT/noFT configurations correspond to the classical approach where most or the entire application logic runs at the server in the DC, whereas the SwiftCloud configurations strive for the opposite, moving as much as possible to the client. Our evaluation emphasises the impact on performance of these two opposites.

Latency

We first evaluate the responsiveness of end-user operations, using the SwiftSocial benchmark. It simulates 25,000 users, each one associated to 25 friends uniformly at random, simulating user sessions as described in Section 5.1. 10% of transactions involve modifications; the rest are read-only. 90% of transactions involve data of the current user and his friends, and hit the cache once it is warm; the other 10% target (uniformly) random users and produce cache misses.

Figure 6(a) plots the CDF of the perceived latency of executing a transaction. In the SwiftCloud default configuration, around 90% of transactions have near-zero latency, the remaining 10% having variable latencies. This corresponds nicely to the 90/10% that respectively hit/miss in the cache; the cost of a miss depends on the RTT to the closest DC, which varies between PlanetLab nodes. Remember that, with mergeable data, updates occur in cache, not just reads.

In the Cloud-noFT configuration, transaction latency is proportional to the client-DC RTT. Cloud-FT suffers additional latency for writing to a quorum. These classical configurations provide worse latency for both reads and writes, when compared with SwiftCloud. Fault-tolerant approaches requiring writing to a quorum of replicas synchronously penalise writes heavily, when compared with SwiftCloud client assisted failover approach. The same happens with the SwiftCloud-naiveFT configuration for the same reason.

Figure 6(b) shows the operation latency experienced by a particular client (other clients have a similar pattern, with the lines being shifted right or left depending on their RTT to the DC).

In Cloud-noFT and Cloud-FT, submitting a request costs a single RTT to the DC. With the SwiftCloud approach, each miss costs one RTT. When the benchmark accesses a non-friend, a cache miss fetches the first read, followed by several others (usually a read followed by a multi_read). For applications relying highly on client-side execution, the main drawback is that cache misses can be costly. It can be mitigated by moving execution of the most offending code paths to the server. To further address this issue in systematic a manner, we are implementing a mechanism to automatically switch to DC-side execution upon a cache miss.

Figure 6(c) plots the CDF of the perceived latency increasing the cache miss ratio by increasing the ratio of operations over non-friends. We can see that 90% of read-write transactions have zero latency, as writes are always on cached data, i.e., objects from the user or from friends. The ratio of read-only transactions experiencing zero latency is directly proportional to the cache hit ratio, as cache misses must be served from the DC. These results are compatible with the results obtained for TPC-W browsing workload with 95% read-only transactions, in a similar deployment, and a system configuration that exhibits 76% hit ratio (Figure 7). This result also shows that the checkout operation (buy confirm), requiring synchronous execution in the DC, presents high latency, as expected.

Throughput vs. latency

We now investigate how SwiftCloud performance compares with classical geo-replication approaches and how it scales with the number of DCs. Figure 8(a) plots throughput vs. latency, comparing SwiftCloud with Cloud-noFT, running the same SwiftSocial benchmark as before. It shows configurations with one, two and three DCs. In each configuration, we increase the load by adding more simulated clients. As the load increases, initially throughput improves while latency does not change; however, as the system saturates, throughput ceases to improve and latency becomes worse. Eventually, throughput decreases as well. We use a log-log scale; down and to the right is better. The plot shows that, at equal hardware cost, SwiftCloud has order-of-magnitude better response time and better throughput, than the classical geo-replication approach, even though SwiftCloud is fault tolerant and Cloud-noFT is not. The explanation is simple: SwiftCloud absorbs 90% of transactions in its cache. Recall that even updates are cached.

Interestingly, although adding a third DC to SwiftCloud improves latency and throughput at first, it does not improve peak performance at saturation, in contrast to the DC-based approach. The reason is that DCs are fully replicated, i.e., every DC processes every update transaction. In the Cloud case, additional DCs allow to process more read-only transactions in parallel, but for SwiftCloud this effect is negligible because read-only transactions were already absorbed by the client-side cache. In this benchmark, 10% of the transactions are read-only transactions that access the DC because of a miss, and 10% are updates that must global-commit in the DC. With a single DC, there is an equal number of both. With two DCs, each DC processes only half of the reads but all of the updates. Thus, the impact of adding a DC is less than in the Cloud setup. Additionally, the faster read transactions execute, the faster additional commits are sent to the DCs. This trend continues when adding additional DCs.

We confirm this explanation by increasing the amount of cache misses to 50% in Figure 8(b). The ratio is now five read-only transactions for one update transaction. This larger ratio is expected to enable SwiftCloud to scale with the number of DCs, as more read-only transactions will benefit from executing in a closer DC. This hypothesis is confirmed by the plot.

In summary, client-side caching of mergeable data enables scalable shared storage with a potentially reduced, cheaper DC infrastructure.

Staleness due to fault-tolerance

We showed in Section 6.2 that our approach to fault tolerance minimises the latency perceived by endusers, compared to the alternatives. However, it slows down propagation of updates; our next experiment aims to quantify by how much. A read will be considered stale if it returns a (K-durable) version, and a more recent (non-K-durable) one exists and satisfies Transactional Causal+ Consistency. Preliminary work (not shown here) showed that with the benchmarks used so far, the number of stale reads is negligible. The reason is that the window of vulnerability -the time it takes for a transaction to become K-durable -is very small, approximately the RTT to the closest DC. We run the SwiftSocial benchmark with 190 PlanetLab nodes spread across Europe and five clients per node, connected to the Ireland DC and replicated in the Oregon DC. To further increase the probability of staleness, we make transactions longer by setting the cache size to zero, requiring reads to contact a DC, and commit to the farthest-away DC, with a RTT of around 170 ms. Figure 6.3 shows the occurrence of stale read operations, and of transactions containing a stale read, for different sizes of the database. We have 950 concurrent clients; with 2,500 simulated users, at any time approximately 40% of the users are actively executing operations concurrently. Even in this case, stale reads and stale transactions remain under 1% and 2.5% respectively. This number decreases as we increment the size of the database, as expected. This shows that even under high contention, accessing a slightly stale snapshot has very little impact on the data read by transactions.

Behaviour during faults

Our final experiment studies the behaviour of SwiftCloud when a DC becomes disconnected or fails. In this case, clients fail-over to another DC. The scatterplot in Figure 10 plots the latency of transactions at an individual client as its scout switches DCs, while running the SwiftSocial benchmark. Each dot represents the latency of an individual transaction. Starting with a cold cache, latency quickly drops to near zero for most transactions, those hitting in the cache, and to around 110 ms for those that perform remote reads due to cache misses. Approximately 33 s into the experiment, the scout is diverted to another DC in a different continent. The new latency pattern reflects the increased cost of cache misses, due to the higher RTT to the DC, which also causes a visible drop in throughput (sparser dots). At 64 s, the client switches back the initial data centre, and performance smoothly recovers to the initial pattern. Note that there are no significant gaps associated with switching, showing that the protocol incurs negligible disruption to the client.

Related work

Cloud storage systems provide a wide range of consistency models. Some systems [START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF][START_REF] Van Renesse | Chain replication for supporting high throughput and availability[END_REF] provide strong consistency [START_REF] Herlihy | Linearizability: a correcteness condition for concurrent objects[END_REF], at the cost of unavailability when a replica is unreachable (network partitions) [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF]. At the opposite end of the spectrum, some systems [START_REF] Terry | Managing update conflicts in Bayou, a weakly connected replicated storage system[END_REF] provide only eventual consistency (EC), but allow any replica to perform updates even when the network is partitioned. Other systems' consistency models lie between these two extremes.

Weak consistency: Causal consistency strengthens EC with the guarantee that if a write is observed, all previous writes are also observed. Mahajan et al. [START_REF] Mahajan | Consistency, availability, and convergence[END_REF] show that, in the presence of partitions, this is the strongest possible guarantee in an always-available, one-way convergent system. To cope with concurrent updates, Causal+ Consistency incorporate mergeable data. This is the model of COPS [START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF], Eiger [START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF], ChainReaction [START_REF] Almeida | ChainReaction: a causal+ consistent datastore based on chain replication[END_REF] and Bolt-On [START_REF] Bailis | Bolt-on causal consistency[END_REF]. These systems merge by last-writer-wins. Some also support an application-provided merge function; for instance Sporc [START_REF] Feldman | SPORC: Group collaboration using untrusted cloud resources[END_REF] relies on operational transformation.

COPS and ChainReaction implement read-only transactions that are non-interactive, i.e, the read set is known from the beginning. Eiger additionally supports non-interactive write-only transactions. SwiftCloud extends these works with interactive transactions, integrated mergeable types support and support for DC failover. A similar approach, including the study of session guarantees and atomicity, was discussed by Bailis et al. [START_REF] Bailis | HAT, not CAP: Highly Available Transactions[END_REF]. Burckhardt et al. [START_REF] Burckhardt | Eventually consistent transactions[END_REF] and Orleans [START_REF] Bykov | Orleans: cloud computing for everyone[END_REF] also provide a model of transactions for EC that uses a branch-and-merge model with main revision, suitable for smaller databases.

Dynamo [START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF] and similar systems [START_REF] Klophaus | Riak Core: building distributed applications without shared state[END_REF][START_REF] Lakshman | Cassandra, a decentralized structured storage system[END_REF] ensure EC and per-key causality. The timeline consistency of PNUTS [START_REF] Cooper | Pnuts: Yahoo!'s hosted data serving platform[END_REF] and the snapshot consistency of Megastore [START_REF] Baker | Megastore: Providing scalable, highly available storage for interactive services[END_REF] enforce a total order on updates, but improve performance by allowing applications to read stale data. Walter [START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF] and Gemini [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF] support both weak and strong consistency in the same system, for disjoint sets of objects and of operations respectively. Our support for non-mergeable transactions uses Gemini's approach.

Concurrent updates: The last-writer-wins (LWW) rule [START_REF] Johnson | The maintenance of duplicate databases[END_REF] for for managing concurrent updates selects between concurrent versions the one with the highest timestamp [START_REF] Almeida | ChainReaction: a causal+ consistent datastore based on chain replication[END_REF][START_REF] Bailis | Bolt-on causal consistency[END_REF][START_REF] Lakshman | Cassandra, a decentralized structured storage system[END_REF][START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF][START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF]. Depot [START_REF] Mahajan | Depot: Cloud storage with minimal trust[END_REF], Dynamo [START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF] and CAC [START_REF] Mahajan | Consistency, availability, and convergence[END_REF] maintain all concurrent versions, letting the application merge them somehow.

The theoretical basis for mergeable data is commutativity and lattice theory. Conflict-free Replicated Data Types (CRDTs) [START_REF] Shapiro | Conflict-free replicated data types[END_REF][START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF], proved to be mergeable using montonic semi-lattice or commutativity, provide abstractions such as sets, graphs, maps, counters and sequences. Bloom L uses program analysis to check that a program's state progresses monotonically in a semi-lattice, and if not inserts a synchronisation point [START_REF] Conway | Logic and lattices for distributed programming[END_REF]; in comparison, our model does not enforces determinism w.r.t. program input and avoids certain synchronisation points, but puts more work on application programmer to design transactions.

SwiftCloud offers CRDTs because several useful abstractions are available, richer yet subsuming LWW. CRDTs were recently added to Riak [START_REF] Klophaus | Riak Core: building distributed applications without shared state[END_REF] and Walter uses a set-like CRDT. SwiftCloud is the first mergeable-data system to support transactions that span multiple CRDT types.

Fault-tolerance: With respect to tolerating DC faults, from the perspective of an end-client, previous geo-replication systems fall into two categories. Synchronous replication [START_REF] Corbett | Spanner: Google's globally-distributed database[END_REF][START_REF] Cowling | Granola: low-overhead distributed transaction coordination[END_REF] can ensure that clients observe a monotonic history in the presence of DC faults, but at the cost of update latency.

Existing asynchronous replication systems ensure fault-tolerant causal consistency only within the boundaries of the DC [START_REF] Bailis | Bolt-on causal consistency[END_REF][START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF][START_REF] Lloyd | Don't settle for eventual: scalable causal consistency for wide-area storage with COPS[END_REF][START_REF] Lloyd | Stronger semantics for low-latency georeplicated storage[END_REF][START_REF] Sovran | Transactional storage for geo-replicated systems[END_REF]. Their clients do not keep sufficient information to ensure causal consistency when a failure causes them to switch DCs. These approaches trade low update latency for consistency or availability. To the best of our knowledge, SwiftCloud is the first low-latency, highly-Inria available system that guarantees convergent causal consistency with transactions all the way to resourcepoor end clients.

Bailis et al. [START_REF] Bailis | Bolt-on causal consistency[END_REF] observe that causal consistency can be decomposed into separate safety and liveness components and that presenting clients with stale versions can eliminate waiting for safety dependencies. We stretch this idea to the client that is not a full replica.

Session guarantee protocols [START_REF] Terry | Session guarantees for weakly consistent replicated data[END_REF] implement the safety component of causal consistency. Brzeziński et al. [START_REF] Brzeziński | K-resilient session guarantees synchronization protocol for mobile ad-hoc networks[END_REF] propose a protocol using K-durability. This allows the client to change server, but their protocol is synchronous and does not ensure exactly-once delivery.

Depot [START_REF] Mahajan | Depot: Cloud storage with minimal trust[END_REF] is the system most similar to SwiftCloud. Depot ensures causal consistency and high availability to clients, even in the presence of server faults. Clients can communicate directly with one another. Depot is designed to tolerate Byzantine faults, a more difficult class of faults than SwiftCloud. However it is not designed to scale to large numbers of clients, to co-locate data with the user without placing a server in the user's machine, nor does it support transactions.

Conclusion

We presented the design of SwiftCloud, the first system that brings geo-replication to the client machine, providing a principled approach for using client and data centre replicas. SwiftCloud allows applications to run transactions in the client machine, for common operations that access a limited set of objects, or in the DC, for transactions that require strong consistency or accessing a large number of objects. Our evaluation shows that the latency and throughput benefit can be huge when compared with traditional cloud deployments for scenarios that exhibit good locality, a property verified in real workloads [START_REF] Benevenuto | Characterizing user behavior in online social networks[END_REF].

SwiftCloud also proposes a novel client-assisted failover mechanism that trades latency by a small increase in staleness. Our evaluation shows that our approach helps reducing latency while increasing stale reads by less than 1%.

Several aspects remain open for improvement. Better caching heuristics, and support for transaction migration, would help to avoid the high latency caused by successive cache misses. Placing scouts at different levels of a hierarchy, in particular in Content Delivery Network points of presence, might improve perceived latency even more. Finally, a better integration at the programming language level could help address engineering concerns, such as data encapsulation across software stack.

Figure 1 :

 1 Figure 1: SwiftCloud system structure.

Figure 2 :Figure 3 :

 23 Figure 2: SwiftCloud Client API.

3 .

 3 Transaction closure. Given a and b, two operations of some transaction T , and x and y, operations that are not part of T : if x a then x b, and if a y then b y. 4. Transitivity. For operations a, b, and c, if a b and b c, then a c. Execution Thread ensures that successive operations executed by a client are dependent. Gets From ensures that a read depends on the updates it reads. For instance, in Figure 3, the read of B.frd (the friend set of B) in T 6 depends on the update to B.frd in T 3 : B.frd.add(A) R[B.frd] = A. Transaction Closure ensures transaction isolation by extending dependence across all operations in the same transaction. For instance, in Figure 3, B.frd.add(A) R[B.frd] = A is extended to A.frd.add(B) R[B.frd] = A, guaranteeing that R[A.frd] = B. The relation is transitive and acyclic, hence it is a partial order.

Figure 4 :

 4 Figure 4: Execution of T 3 from Figure 3.

Figure 5 :

 5 Figure 5: Experimental topology and round-trip times.

Figure 6 :

 6 Figure 6: Perceived latency for SwiftSocial.

Inria

Figure 7 :

 7 Figure 7: Latency for TPC-W browsing workload.

Figure 8 :

 8 Figure 8: Performance of SwiftCloud (SwiftSocial).

Figure 9 :

 9 Figure 9: Staleness of reads due to fault tolerance algorithm in SwiftCloud as a function of contention (SwiftSocial).

Figure 10 :

 10 Figure 10: Latency for a single client switching data centres

RR n°8347

Requiring programmer to provide explicit causal dependencies at the programming level may reduce the amount of direct dependencies[START_REF] Bailis | The potential dangers of causal consistency and an explicit solution[END_REF], nevertheless indirect dependencies are still of a problem.RR n°8347

Specifically, a stronger variant involving real-time dependencies.

The number of entries in maxOTID is the number of scouts, which can be large. However, a map is local to a DC, and never transmitted and the number of active clients is more limited. Supporting even millions of clients is well within the DC storage capabilities.Inria

InriaRESEARCH CENTRE PARIS -ROCQUENCOURTDomaine de Voluceau, -Rocquencourt B.P. 105 -78153 Le Chesnay Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

This research is supported in part by ANR project ConcoRDanT (ANR-10-BLAN 0208), by the Google Europe Fellowship in Distributed Computing awarded to Marek Zawirski, and by Portuguese FCT/MCT projects PEst-OE/EEI/UI0527/2011 and PTDC/EIA-EIA/108963/2008 and Phd scholarship awarded to Valter Balegas (SFRH/BD/87540/2012). machine cliente