Marc Shapiro

Nuno Preguiça

Carlos Baquero

Marek Zawirski

Conflict-free Replicated Data Types

Keywords: Eventual Consistency, Replicated Shared Objects, Large-Scale Distributed Systems

published or not. The documents may come

Introduction

Replication and consistency are essential features of any large distributed system, such as the WWW, peer-to-peer, or cloud computing platforms. The standard "strong consistency" approach serialises updates in a global total order [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]. This constitutes a performance and scalability bottleneck. Furthermore, strong consistency conflicts with availability and partition-tolerance [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF].

When network delays are large or partitioning is an issue, as in delay-tolerant networks, disconnected operation, cloud computing, or P2P systems, eventual consistency promises better availability and performance [START_REF] Saito | Optimistic replication[END_REF][START_REF] Vogels | Eventually consistent[END_REF]. An update executes at some replica, without synchronisation; later, it is sent to the other replicas. All updates eventually take effect at all replicas, asynchronously and possibly in different orders. Concurrent updates may conflict; conflict arbitration may require a consensus and a roll-back. 6This weaker consistency is considered acceptable for some classes of applications. However, conflict resolution is hard. The literature offers little guidance on designing a correct optimistic system. Ad-hoc approaches are brittle and errorprone; witness for instance the concurrency anomalies of the Amazon Shopping Cart [START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF].

We propose a simple, theoretically-sound approach to eventual consistency. Our system model, Strong Eventual Consistency or SEC, avoids the complexity of conflict resolution and of roll-back. Conflict-freedom ensures safety and liveness despite any number of failures. It leverages simple mathematical properties that ensure absence of conflict, i.e., monotonicity in a semi-lattice and/or commutativity. A trivial example is a replicated counter, which (assuming no overflow) converges because its increment and decrement operations commute. In our conflict-free replicated data types (CRDTs), an update does not require synchronisation, and CRDT replicas provably converge to a correct common state. CRDTs remain responsive, available and scalable despite high network latency, faults, or disconnection.

Non-trivial CRDTs are known to exist: for instance, we previously published Treedoc, a sequence CRDT for co-operative text editing [START_REF] Preguiça | A commutative replicated data type for cooperative editing[END_REF]. Our aim here is to expand our knowledge of the principles and practice of CRDTs. We claim the following contributions for this paper:

-A solution to the CAP problem, Strong Eventual Consistency (SEC).

-Formal definitions of Strong Eventual Consistency (SEC) and of CRDTs.

-Two sufficient conditions for SEC.

-A strong equivalence between the two conditions. -We show that SEC is incomparable to sequential consistency.

-Description of basic CRDTs, including integer vectors and counters.

-More advanced CRDTs, including sets and graphs.

We refer the interested reader to a separate technical report [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF] for further detail and for a comprehensive portfolio of CRDT designs.

System model

We consider a system of processes interconnected by an asynchronous network. The network can partition and recover. We assume a finite set Π = {p 0 , . . . , p n-1 } of non-byzantine processes. Processes in Π may crash silently; a crashed process may remain crashed forever, or may recover with its memory intact. A non-crashed process is said correct.

State-based object

In this section we specify replicated objects in the so-called state-based style.

The intuition is illustrated in Figure 1. Executing an update modifies the state of a single replica. Every replica occasionally sends its local state to some other replica, which merges the state thus received into its own state. In this way, every update eventually reaches every replica, either directly or indirectly.

With no loss of generality, we consider a single object with one replica at each process. An object is a tuple (S, s 0 , q, u, m). The replica at process p i has state s i ∈ S, called its payload; the initial state is s 0 . A client of the object may read the state of the object via query method q and modify it via update method u. Method m serves to merge the state from a remote replica. A method (whether q, u or m) executes at a single replica.

Systems that deliver every update to every replica eventually in a faulttolerant manner are well-known in the literature, for instance gossip or antientropy approaches [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF]. For simplicity, we will assume hereafter a fully connected communication graph, where every arc is a fair-lossy channel. Infinitely often, the replica at p i sends (if it is correct) its current state to p j ; replica p j (if it is correct) merges the received state into its local state by executing method m.

A method whose precondition is satisfied is said enabled. We assume that an enabled method executes as soon as it is invoked. Method executions at some replica are numbered sequentially from 1. The k th method execution at replica i will be noted f k i (a), where f is either q, u or m, and a denotes the arguments. We note K i (f ) the ordinal of execution f at replica i, i.e., K i (f k j (a)) = k for i = j, and is undefined otherwise. (Abusing notation somewhat, we may drop subscripts, superscripts and/or arguments when there is no ambiguity.)

The states of a replica are numbered sequentially incrementing with each method execution. Thus, replica i has initial state s 0 i = s 0 . Before its k th execution of a method it has state s k-1 i , and s k i afterwards. We note the transition

s k-1 i • f k i (a) = s k i .
We define state equivalence s ≡ s ′ if all queries return the same result for s and s ′ . A query has no side-effects, i.e., (s • q) ≡ s.

Definition 1 (Causal History (state-based)).

We define the object's causal history C = [c 1 , . . . , c n ] (where c i goes through a sequence of states c 0 i , . . . , c k i , . . . ) as follows. Initially, c 0 i = ∅, for all i. If the k th method execution at i is: (i) a query q: the causal history does not change, i.e.,

c k i = c k-1 i ; (ii) an update (noted u k i (a)): it is added to the causal history, i.e., c k i = c k-1 i ∪ {u k i (a)}; (iii) a merge m k i (s k ′ i ′ )
, then the local and remote histories are unioned together:

c k i = c k-1 i ∪ c k ′ i ′ .
We say that an update is delivered at some replica when it is included in the causal history at that replica. An update u happened-before u ′ iff u is delivered when u ′ executes:

u → u ′ def = u ∈ c k-1 j
, where u ′ executes at replica p j and K j (u ′ ) = k. Updates are concurrent if neither happened-before the other:

u u ′ def = u → u ′ ∧ u ′ → u.
Note that the causal history is a formal reasoning device, which is normally not needed in a concrete implementation.

Given our communication assumptions, we can conclude that, in a statebased object, every update is eventually delivered to all replicas. However, this is not sufficient to ensure that replicas converge. For instance, if the merge method m is a no-op, an update executed at some replica has no effect on other replicas, and they will never converge.

Strong Eventual Consistency

Informally, eventual consistency means that replicas eventually reach the same final value if clients stop submitting updates. We capture this intuition as follows:

Definition 2 (Eventual Consistency (EC)). Eventual delivery:

An update delivered at some correct replica is eventually delivered to all correct replicas: ∀i, j : f ∈ c i ⇒ ♦f ∈ c j . Convergence: Correct replicas that have delivered the same updates eventually reach equivalent state: ∀i, j : c i = c j ⇒ ♦ s i ≡ s j . Termination: All method executions terminate.

Several EC systems will execute an update immediately, only to discover later that it conflicts with another, and to roll back to resolve this conflict [START_REF] Terry | Managing update conflicts in Bayou, a weakly connected replicated storage system[END_REF]. This constitutes a waste of resources, and in general requires a consensus to ensure that all replicas arbitrate conflicts in the same way. To avoid this, we require a stronger condition:

Definition 3 (Strong eventual consistency (SEC)). An object is Strongly Eventually Consistent if it is Eventually Consistent and:

Strong Convergence: Correct replicas that have delivered the same updates have equivalent state: ∀i, j : c i = c j ⇒ s i ≡ s j .

State-based Convergent Replicated Data Type (CvRDT)

We now propose a sufficient condition for strong convergence in state-based objects. A join semilattice (or just semilattice hereafter) is a partial order ≤ equipped with a least upper bound (LUB) ⊔ for all pairs:

m = x ⊔ y is a Least Upper Bound of {x, y} under ≤ iff ∀m ′ , x ≤ m ′ ∧y ≤ m ′ ⇒ x ≤ m∧y ≤ m∧m ≤ m ′ . It follows that ⊔ is: commutative: x ⊔ y = y ⊔ x; idempotent: x ⊔ x = x; and associative: (x ⊔ y) ⊔ z = x ⊔ (y ⊔ z).

Definition 4 (Monotonic semilattice object).

A state-based object, equipped with partial order ≤, noted (S, ≤, s 0 , q, u, m), that has the following properties, is called a monotonic semi-lattice: For lack of space, we omit the proof that is presented in a companion technical report [START_REF] Shapiro | Conflict-free Replicated Data Types[END_REF]. A CvRDT converges towards the LUB of the most recent updates. We require that x ≤ y ∧ y ≤ x ⇒ x ≡ y.

(i) Set S of

Op-based Commutative Replicated Data Type (CmRDT)

Alternatively to the state-based style, a replicated object may be specified in the operation-based (or op-based) style. An op-based object is a tuple (S, s 0 , q, t, u, P ), where S, s 0 and q have the same meaning as above (respectively state domain, initial state and query method). An op-based object has no merge method; instead an update is split into a pair (t, u), where t is a side-effect-free prepare-update method and u is an effect-update method. The prepare-update executes at the single replica where the operation is invoked (its source). At the source, prepare-update method t is followed immediately by effect-update method u, i.e., f k-

1 i = t ⇒ f k i = u.
(If this were not true, there would be no causality between successive updates.)

The effect-update method executes at all replicas (said downstream). The source replica delivers the effect-update to downstream replicas using a communication protocol specified by the delivery relation P , explained below.

We use the same notations for states and causal history as above, except that now f can refer to any of q, t or u. Both queries and prepare-update methods are side-effect-free, i.e., s • q ≡ s • t ≡ s.

Definition 5 (Causal History (op-based)

). An object's causal history C = {c 1 , . . . , c n } is defined as follows. Initially, c 0 i = ∅, for all i. If the k th method execution at i is: (i) a query q or a prepare-update t, the causal history does not change, i.e.,

c k i = c k-1 i ; (ii) an effect-update u k i (a), then c k i = c k-1 i ∪ {u k i (a)}.
An update is said delivered at a replica when the update is included in the replica's causal history. Update (t, u) happened-before (t ′ , u ′ ) iff the former is delivered when the latter executes: (t, u)

→ (t ′ , u ′ ) ⇔ u ∈ c k-1 j
, where t ′ executes at p j and k = K j (t ′ ). The definition of concurrent updates remains as above.

We assume an underlying reliable causally-ordered broadcast communication protocol, i.e., one that delivers every message to every recipient exactly once and in an order consistent with happened-before. Such protocols are a standard feature of distributed systems; they do not require consensus and they deliver to all correct processes as long as any network partition eventually recovers (as we assumed earlier). It follows that two updates that are related by happenedbefore execute at all replicas in the same sequential order: (t, u) → (t ′ , u ′ ) ⇒ ∀i, K i (u) < K i (u ′ ). However, concurrent updates may be delivered in any order. Definition 6 (Commutativity). Updates (t, u) and (t ′ , u ′ ) commute, iff for any reachable replica state s where both u and u ′ are enabled, u (resp.

u ′ ) remains enabled in state s • u ′ (resp. s • u), and s • u • u ′ ≡ s • u ′ • u.
Clearly, a sufficient condition for convergence of an op-based object is that all its concurrent operations commute. An object satisfying this condition is called a Commutative Replicated Data Type (CmRDT).

P is a delivery precondition, i.e., effect-update method u is enabled only if the precondition is satisfied. We interpret this temporally, i.e., delivery of u at replica i may delayed, until P (s i , u) is true. Therefore, for liveness, we now have the added obligation to prove that delivery is eventually enabled. Therefore we restrict our scope to preconditions for which causally-ordered broadcast is sufficient to ensure P .

Theorem 2 (Commutative Replicated Data Type (CmRDT)). Assuming causal delivery of updates and method termination, any op-based object that satisfies the commutativity property for all concurrent updates, and whose delivery precondition is satisfied by causal delivery, is SEC.

The proof is presented in [START_REF] Shapiro | Conflict-free Replicated Data Types[END_REF].

3 Some results

Fault-tolerance and the CAP theorem

The CAP theorem states that it is impossible to simultaneously ensure strong consistency (C), availability (A) and tolerate network partition (P) [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF]. As, network faults unavoidably occur in a large-scale environment, a real system must sacrifice either consistency or availability. Availability is often the top priority in practice [START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF]: does this mean giving up all consistency guarantees?

No: SEC provides a solution. A SEC replica is always available for both reads and writes, independently of network conditions. Any communicating subset of replicas of a SEC object eventually converges, even if partitioned from the rest of the network. SEC is weaker than strong consistency but nonetheless provides the well-defined guarantee of strong eventual convergence.

SEC provides an extreme form of fault tolerance, as a SEC object tolerates up to n -1 simultaneous crashes. Remarkably, SEC does not require to solve consensus.

CvRDTs and CmRDTs are equivalent

Operation-based emulation of a state-based object Theorem 3 (CmRDT emulation). Any SEC state-based object can be emulated by a SEC op-based object of a corresponding interface.

Proof. Given a CvRDT represented by tuple (S, ≤, s 0 , q, u, m), we emulate it by a CmRDT object (S, s 0 , q, t, u ′ , P ), which we specify hereby.

State and query of CvRDT can be directly stored and processed by emulating CmRDT using the same definitions. A prepare-update t(a) has the same interface (accepts the same domain of arguments and returns the same domain of value) as an update u(a). It records the result of applying update u(a) on a copy of current replica state s: s ′ = s • u(a); return value of u(a) is passed to the client. Recorded state s ′ is used as an argument of an actual effect-update u ′ (s ′ ), which is delivered to all replicas by the underlying protocol of CmRDT. Precondition P is unrestricted and enables delivery at any time. Effect-update u ′ (s ′ ) merges received state using original CvRDT method:

s • u ′ (s ′ ) def = s • m(s ′ ).
Since merge always commutes, then updates u ′ (s ′ ) commute and since the communication is reliable, we have a CmRDT with strong eventual consistency, which propagates all updates of emulated CvRDT.

State-based emulation of an operation-based object

State-based emulation of an operation-based object essentially formalises the mechanics of an epidemic reliable causal broadcast.

Theorem 4 (CvRDT emulation). Any SEC op-based object can be emulated by a SEC state-based object of a corresponding interface.

Proof. Given a CmRDT represented by tuple (S, s 0 , q, t, u, P ), we emulate it by a CvRDT object ((S × U × U ), ≤, (s 0 , ∅, ∅), q ′ , u ′ , m), which we specify hereby.

Without loss of generality, we assume that each invocation u k i is unique across replicas and set U denotes all possible updates. CvRDT's state is then defined as a triple (s m , M, D), where s m is a state of emulated CmRDT, M and D are two add-only sets of, respectively, known and delivered updates. A relation ≤ is defined as following:

(s m , M, D) ≤ (s ′ m , M ′ , D ′ ) def = M ⊆ M ′ ∧ D ⊆ D ′ . A query q ′ (
a) has the same interface as q(a); we define it as a trivial delegation to q(a) on the CmRDT, s m • q(a). An update u ′ (a) has the same interface as prepare-update t(a). It first delegates the invocation to prepare-update t(a) of the CmRDT that in turn triggers effect-update u(a), which becomes a locally known update. Finally, u ′ (a) uses a recursive function d to process updates:

d(s m , M, D) def = d(s m • u(a), M, D ∪ {u(a)}) if ∃u(a) ∈ M \ D : P (s m , u(a)) (s m , M, D) otherwise Hence, u ′ (a) is defined as: (s m , M, D) • u ′ (a) def = d(s m • t(a), M ∪ {u(a)}, D).
Finally, merge m takes a union of known messages and processes available updates:

(s m , M, D) • m(s ′ m , M ′ , D ′ ) def = d(s m , M ∪ M ′ , D
). Since the emulation ensures that messages are delivered exactly once to each replica's embedded object, in the appropriate order, and since the CvRDT conforms to SEC criteria, the embedded CmRDT instance is also SEC.

Note that the emulating object forms a monotonic semilattice over domain S × U × U . Calling or delivering an operation adds it to the relevant message set, and therefore advances the state in the partial order. The merge method m is defined to take the union of the M sets and (possibly) updating D, and is thus a LUB operation. This construction is similar to Wuu and Bernstein's log covered in Section 4.2.

SEC is incomparable to sequential consistency

A state-based replica executes a sequence of query, update, and merge methods. In addition to its sequential behaviour, a CRDT specifies concurrent behaviours that must satisfy the strong convergence property. As we show now, this permits executions that would be impossible in a sequentially-consistent system.

Consider a Set CRDT S with operations add(e) and remove(e). Immediately after add(e), the state will satisfy e ∈ S; after remove(e) the state satisfies e / ∈ S. In a sequential execution, the last update wins, e.g., after remove(e) → add(e) the state satisfies e ∈ S. Concurrent adds or removes of different elements are independent, e.g., after add(e) remove(e ′ ) the state satisfies e ∈ S ∧ e ′ / ∈ S. There is a choice of alternative semantics for concurrent updates of the same element. When concurrently adding and removing the same element, the add could win, or the remove could win, or the update of the replica with the highest IP address could win, or the state might be reset to a distinguished state ⊥, and so on. All these alternatives satisfy the strong convergence condition, and any of them may be reasonable for some application.

Let us consider the add-wins alternative: after add(e) remove(e) the state satisfies e ∈ S. Now consider the following scenario. Replica p 0 executes the sequence add(e); remove(e ′ ). Concurrently, replica p 1 executes add(e ′ ); remove(e). Then, replica p 3 merges the state from p 0 and p 1 . According to the concurrent specification, the final state at p 3 satisfies e ∈ S ∧ e ′ ∈ S. Such a state would never occur in a sequentially-consistent execution, in which either remove(e) or remove(e ′ ) must be last. Thus, there is a SEC object that is not sequentially consistent. Now consider the converse. In the absence of crashes, a sequentially-consistent object is SEC. Indeed, sequential consistency is defined by a single order of operations, after which all replicas must terminate with the same state. However, in the general case, sequential consistency requires consensus, which cannot be solved in the presence of n -1 crashes. Therefore, SEC is incomparable with sequential consistency.

Example CRDTs

We now recall some basic CRDTs that are known in the existing literature, which we will later compose to build higher-level objects. We will use state-or op-based specifications as most convenient. Generally, we find the state-based style more compact and easier to reason about formally, whereas the op-based style is often convenient for implementation.

Integer vectors and counters

Consider the state-oriented specification of a vector-of-integers object:

(N n , [0, . . . , 0], ≤ n , [0, . . . , 0], value, inc, max n ). Vectors v, v ′ ∈ N n are (partially) ordered by v ≤ n v ′ ⇔ ∀j ∈ [0..n -1], v[i] ≤ v ′ [i].
A query invocation value() returns a copy of the local payload. An update inc(i) increments the payload entry at index i, that is, s

• inc(i) = [s ′ [0], . . . , s ′ [n -1]] where s ′ [j] = s[j] + 1 if i = j and s ′ [j] = s[j] otherwise. Merging two vectors takes the per-index maxi- mum, i.e., s • max n (s ′ ) = [max(s[0], s ′ [0]), . . . , max(s[n -1], s ′ [n -1])].
We omit the proof that it is a CRDT.

If each process p i is restricted to incrementing its own index inc(i), this is the well-known vector clock [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF].

An increment-only integer counter is very similar; the only difference being that query invocation value() of a vector in state v returns

|v| def = j v[j].
We construct an integer counter that can be both incremented and decremented, by basically associating two increment-only counters I and D, where incrementing increments I and decrementing increments D, whereas value() returns |I| -|D|.

The ordering method ≤ is defined as (I, D)

≤ (I ′ , D ′ ) def = I ≤ n I ′ ∧ D ≤ n D ′ .

U-Set, map and log

Another simple CRDT construct is an add-only set object (S, ⊆ , ∅, value, add(e), ∪). The payload is any set; sets are ordered by inclusion. A query value() returns a copy of the local payload. Update add(e) adds element e to the set, i.e., s • add(e) = s ∪ {e}. It is well-known that sets ordered by ⊆ form a semi-lattice with ∪ as the LUB operator. It is clearly monotonic by the definition of add. Therefore, the add-only set is a CRDT.

Wuu and Bernstein build further CRDTs by combination of these basic components [START_REF] Wuu | Efficient solutions to the replicated log and dictionary problems[END_REF]. They propose a set with both add and remove operations by associating two add-only sets A and R; adding an element adds it to A, removing it adds it to R; query value() returns the set difference A \ R. (R is often called the tombstone set. A client is allowed to remove only an element that is currently in A). Note that they assume that every element is unique and added only once; we call their construct U-Set [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF]. Wuu and Bernstein derive their Dictionary data type from U-Set in the obvious way.

A Log is a replicated object, whose payload contains a set (initially empty) of (event, timestamp) pairs. It assumes that each process maintains a vector clock in the usual manner [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF]. When an event e occurs at process i, the process invokes update add(e); the update method updates the vector clock (say, to state v) and adds the pair (e, v) to the set. The timestamp ensures that each entry is unique. The merge method takes the union of the local and a remote set.

To avoid unbounded growth, Wuu and Bernstein propose a distributed garbage collection algorithm that discards unneeded entries. In order to tolerate n -1 crashes, only an entry that has been delivered to all processes may be discarded. If vector clock entry v i [j] = k, this implies that process i has delivered all k first events of process p j . Each replica maintains in its payload a copy of all remote vector clocks; for each remote site, the merge procedure keeps the largest version. Then, a replica may discard a log entry as soon as its timestamp is less than all the remote vector clocks. This algorithm does not require a consensus, but it is live only if no process is crashed. However, this may be acceptable, since the liveness of garbage collection does not impact the correctness of the main algorithm.

This algorithm may be adapted to other data types, for instance to discarding the A and R entries of a removed element in the U-Set.

Directed Graph CRDT

Now let us examine how one would design a more complex data type: a Directed Graph CRDT. Graphs are an important general-purpose data structure. Some important applications and algorithms work on graphs, e.g., shortest-path or web page-rank.

Thought experiment

To motivate our graph design, consider the "thought experiment" of designing a web search engine. The search engine uses a directed graph representing the web structure. This graph may be used, among other things, to compute page rank. Such an application processes large amounts of data and performs many updates. For efficiency and scalability, processing should be asynchronous; for responsiveness, processing should be incremental, as fast as each page is crawled. Processing should not require any synchronisation, e.g., transactions. A CRDT could be ideal.

We start with a Set CRDT containing some initial URLs to be crawled. A number of crawler processes run in parallel; each one removes some URL from the set and downloads it. (It might happen that the same page is downloaded twice but this does not impact correctness.)

When a crawler finds a new page, it executes the corresponding addVertex. For every page, it parses the links that it contains, comparing it with the page's previous version, if any, and executes the corresponding addArc and removeArc invocations. Finally, the URLs of the linked pages are added to the set to be crawled. Note that addArc must work even if the page at the tail of the arc has not yet been found (it might not even exist), but such an arc is not functional; a lookup of the corresponding arc should fail. Similarly if a node has been removed, all arcs incident to the node disappear. In this way, the behaviour of our CRDT will be consistent with that of web pages, which are allowed to contain nonfunctional URLs. Once the linked page is created, the link become relevant, e.g., for navigation and for page-rank computation.

payload set V , A --sets of pairs { (element e, unique-tag w), . . . } initial ∅, ∅ --V : vertices; A: arcs query lookup (vertex v) : boolean b let b = (∃w : (v, w) ∈ V ) query lookup (arc (v ′ , v ′′ )) : boolean b let b = (lookup(v ′ ) ∧ lookup(v ′′ ) ∧ (∃w : ((v ′ , v ′′ ), w) ∈ A) update addVertex (vertex v) prepare (v) : w let w = unique() --unique() returns a unique value effect (v, w) V := V ∪ {(v, w)} --v + unique tag update removeVertex (vertex v) prepare (v) : R pre lookup(v) --precondition pre ∃v ′ : lookup((v, v ′ )) --v is not the head of an existing arc let R = {(v, w)|∃w : (v, w) ∈ V } --Collect all unique pairs in V containing v effect (R) V := V \ R update addArc (vertex v ′ , vertex v ′′ ) prepare (v ′ , v ′′ ) : w pre lookup(v ′ ) --head node must exist let w = unique() --unique() returns a unique value effect (v ′ , v ′′ , w) A := A ∪ {((v ′ , v ′′ ), w)} --(v ′ , v ′′ ) + unique tag update removeArc (vertex v ′ , vertex v ′′ ) prepare (v ′ , v ′′ ) : R pre lookup((v ′ , v ′′ )) --arc(v ′ , v ′′ ) exists let R = {((v ′ , v ′′ ), w)|∃w : ((v ′ , v ′′ ), w) ∈ A} effect (R) --Collect all unique pairs in A containing arc (v ′ , v ′′ ) A := A \ R
In the web application, the graph is very large; sending the state between replicas and merging would be very costly. Therefore, we choose an op-based approach.

Design alternatives for arc removal

A directed graph is a pair of sets (V, A), called vertices and arcs respectively, such that A ⊆ V × V . Updates must maintain the invariant that the head and tail vertices of an arc both exist. Therefore, adding an arc to A has the precondition that its two vertices are in V ; conversely, a vertex may be removed only if it supports no arc; these are preconditions to prepare-update. Furthermore, the system must ensure that concurrent addArc(v ′ , v ′′ ) removeVertex(v ′ ) do not violate the invariant. Several alternatives may be considered: (i) Give precedence to removeVertex(v ′ ): all edges to or from v ′ are removed as a side effect. This is easy to implement, by hiding any arc that includes a removed vertex.

(ii) Give precedence to addArc(v ′ , v ′′ ): if either v ′ or v ′′ has been removed, it is restored. This requires recreating nodes that have being explicitly deleted. (iii) removeVertex(v ′ ) is delayed until all concurrent addArc operations have executed. This requires synchronisation which violates the goals of asynchrony and fault tolerance. There is no perfect choice. Hereafter, we choose Option (i) because it is adequate in our application scenario.

Graph specification

Figure 3 shows our specification for a Directed-Graph CRDT. We prove that this object is indeed a CmRDT in [START_REF] Shapiro | Conflict-free Replicated Data Types[END_REF].

This CRDT maintains two sets internally, one for the vertices and one for the arcs. To add a vertex v, the prepare-update method creates a unique identifier, w, and the effect-update method adds the pair (v, w) to the set of vertices. With this approach, each vertex has an unique internal identifier. If the same vertex is added twice, the two additions will be distinguished by their two unique identifiers. A lookup will mask the duplicates.

To remove vertex v, the prepare-update computes the set R of pairs that contain v, i.e., all copies known in the source replica; the effect-update method removes this same set R from the set of vertices in all replicas. As operations are delivered in causal order, when the effect-update method executes in some replica, for each pair in R, the correspondent addVertex operations has already executed. Thus, unlike the state-based solution of Section 4.2, a set need not keep tombstones.

If the same vertex is removed and added concurrently, the addVertex wins, as the new unique identifier is not included in the set computed by the remove's prepare-update. This approach is consistent with a sequential execution, as the a vertex can removed only if it is observed. The same approach is used for arcs.

To remove a vertex, the source replica checks that the vertex is observed, and also that it is not the head of any existing arc. Conversely, to add an arc, its head node must exist, but there is no check for existence of the tail. The lookup method will mask the existence of such an arc. However, if the tail is added later, then the arc becomes visible. Similarly, concurrent updates may remove a vertex that is the head of an arc. However, the lookup method will mask such an arc.

Comparison with previous work

Eventual consistency has been an active topic of research in highly-available, large-scale asynchronous systems [START_REF] Saito | Optimistic replication[END_REF][START_REF] Vogels | Eventually consistent[END_REF]. Contrary to much previous work [3, for instance], we take a formal approach grounded in the theory of commutativity and semilattices.

The state-based approach was invented for register-like objects, where the only update operation is assignment. It is in wide use in file systems such as NFS, AFS or Coda, and in key-value stores such as Dynamo [START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF] and Riak. Opbased approaches are used when the cost of transferring state is too high, e.g., databases, and when operation semantics are important, e.g., cooperative systems such as Bayou [START_REF] Petersen | Flexible update propagation for weakly consistent replication[END_REF] or IceCube [START_REF] Preguiça | Semantics-based reconciliation for collaborative and mobile environments[END_REF].

Although the CRDT concept was identified only recently, related designs have been published before. Johnson et. al. invented the LWW-Register [START_REF] Johnson | The maintenance of duplicate databases. Internet Request for Comments RFC 677[END_REF]. They propose a database of registers that can be created, updated and deleted, using the last-writer-wins (LWW) rule to arbitrate between concurrent changes. LWW ensures a total order of operations, at the cost of losing concurrent updates.

Concurrent editing uses the related concept of Operational Transformation (OT), due to Ellis and Gibbs [START_REF] Ellis | Concurrency control in groupware systems[END_REF]. To ensure responsiveness, a local operation executes immediately. Operations are not designed to commute; however, a replica receiving an update transforms it against previously-executed concurrent updates to achieve a similar result. OT algorithms for a decentralised architecture have been proposed; Oster et al. show that most of them are incorrect [START_REF] Oster | Proving correctness of transformation functions in collaborative editing systems[END_REF]. We believe that designing for commutativity from the start is cleaner and simpler.

The foundations of CvRDTs were introduced by Baquero and Moura [START_REF] Baquero | Specification of convergent abstract data types for autonomous mobile computing[END_REF]. We extend their work with CmRDTs and with a number of new results. The CRDT concept was invented by Shapiro and Preguiça on their work on Treedoc, a Sequence CRDT for concurrent editing [START_REF] Preguiça | A commutative replicated data type for cooperative editing[END_REF]. Logoot is another Sequence CRDT that supports an undo mechanism based on a CRDT Counter [START_REF] Weiss | Logoot-undo: Distributed collaborative editing system on P2P networks[END_REF].

Roh et al. [START_REF] Roh | Replicated abstract data types: Building blocks for collaborative applications[END_REF] independently developed the related concept of Replicated Abstract Data Type. They generalise LWW to a partial order of updates, which they leverage to build several LWW-style classes.

Burckhardt and Leijen propose the Concurrent Revisions programming model for shared abstract data types, in which a forked revision runs in isolation until it joins again. Join is based on a three-way merge function [START_REF] Burckhardt | Semantics of concurrent revisions[END_REF]. They show that simple sequential merge functions exist for ADTs built upon Abelian groups. We have also demonstrated the relation between CRDTs and sequential consistency in a similar, but more loosely-coupled, replication model.

Ducourthial et al. study algebraic structures with specific properties in order to solve self-stabilisation problems [START_REF] Ducourthial | R-semi-groups: a generic approach for designing stabilizing silent tasks[END_REF]. They propose the so-called r-operator for "silent" tasks [START_REF] Delaët | Self-stabilization with R-operators revisited[END_REF]. Strong convergence can be seen as as a silent task, given a limited number of disturbing updates. However, there are differences between the two approaches. Whereas a self-stabilising system must tolerate arbitrary memory corruption, a shared mutable object should change state durably only by executing update operations. Furthermore, whereas CvRDT states constitute a monotonic semi-lattice, the r-operator requries a total order.

Conclusion

We presented the concept of a CRDT, a replicated data type for which some simple mathematical properties guarantee eventual consistency. In the state-based style, the successive states of an object should form a monotonic semilattice, with merge computing a least upper bound. In the op-based style, concurrent operations should commute. Assuming only that the communication subsystem ensures eventual delivery (in causal order for op-based objects), CRDTs are guaranteed to converge towards a common, correct state, without requiring any synchronisation.

We presented some simple CRDT examples, such as sets, and detailed how to create a directed Graph CRDT, which might be used in a large-scale web search engine. Our data types have a clean and deterministic semantics in the presence of concurrent updates.

Eventual consistency is a critical technique in many large-scale distributed systems, including delay-tolerant networks, sensor networks, peer-to-peer networks, collaborative computing, cloud computing, and so on. However, work on eventual consistency was mostly ad-hoc so far. Although some of our CRDTs were known before in the literature or in the folklore, this is the first work to engage in a systematic study. We believe this is required if eventual consistency is to gain a solid theoretical and practical foundation.

Future work is both theoretical and practical. On the theory side, this will include understanding the class of computations that can be accomplished by CRDTs, the complexity classes of CRDTs, the classes of invariants that can be supported by a CRDT, the relations between CRDTs and concepts such as self-stabilisation and aggregation, and so on. On the practical side, we plan to implement the data types specified herein as a library, to use them in practical applications, and to evaluate their performance analytically and experimentally. Another direction is to support infrequent, non-critical synchronous operations, such as committing a state or performing a global reset. We will also look into stronger global invariants, possibly using probabilistic or heuristic techniques.

Fig. 1 .Fig. 2 .

 12 Fig. 1. State-based replication

Fig. 3 .

 3 Fig. 3. Directed Graph Specification (op-based)

A conflict is a combination of concurrent updates, which may be individually correct, but that, taken together, would violate some invariant.

⋆ This research is supported in part by ANR project ConcoRDanT (ANR-10-BLAN 0208). Marek Zawirski is supported in part by his Google Europe Fellowship in Distributed Computing 2010. Nuno Preguiça is partially supported by CITI (PEst-OE/EEI/UI0527/2011). Carlos Baquero is partially supported by FCT project Castor (PTDC/EIA-EIA/104022/2008).


Mingxin Zhou
email: mingxin.zhou@pku.edu.cn

Member, IEEE Leiming Zhang
email: leiming.zhang@pku.edu.cn

Senior Member, IEEE Lingyang Song
email: lingyang.song@pku.edu.cn

Senior Member, IEEE Merouane Debbah
email: mer-ouane.debbah@supelec.fr

A Differential Feedback Scheme Exploiting the Temporal and Spectral Correlation

Keywords: Differential feedback, correlation, MIMO I. INTRODUCTION

Channel state information (CSI) provided by limited feedback channel can be utilized to increase the system throughput. However, in multiple input multiple output (MIMO) systems, the signaling overhead realizing this CSI feedback can be quite large, while the capacity of the uplink feedback channel is typically limited. Hence, it is crucial to reduce the amount of feedback bits. Prior work on limited feedback compression commonly adopted the block fading channel model where only temporal or spectral correlation in wireless channel is considered. In this paper, we propose a differential feedback scheme with full use of the temporal and spectral correlations to reduce the feedback load. Then, the minimal differential feedback rate over MIMO time-frequency (or doubly) selective fading channel is investigated. Finally, the analysis is verified by simulation results.

the fading process was considered best. When the wireless channel experiences temporal-correlated fading, modeled as a finite-state Markov chain, the amount of CSI feedback bits can be reduced by ignoring the states occurring with small probabilities [START_REF] Baddour | Autoregressive modeling for fading channel simulation[END_REF]- [START_REF] Zhou | Interference alignment with delayed differential feedback for time-correlated MIMO channels[END_REF]. The feedback rate in frequency-selective fading channels was studied in [START_REF] Sun | Asymptotic capacity of multicarrier transmission with frequency-selecive fading and limited feedback[END_REF], [START_REF] Chin | Design of Differential Quantization for Low Bitrate Channel State Information Feedback in MIMO-OFDM Systems[END_REF], by exploiting the frequency correlation.

In summary, all the above works mainly focus on feedback rate compression considering either temporal correlation or spectral correlation. However, doubly selective fading channels are more frequently encountered in wireless communications as the desired data rate and mobility grow simultaneously. To the best knowledge of the authors, the scheme of making full use of the two-dimensional correlations is not yet well studied. Using both of the orthogonal dimensional correlations in a cooperated way, the feedback overhead can be further reduced in the doubly selective fading channels. Thus, in this paper, we derive the minimal feedback rate using both the temporal and spectral correlations.

The main contributions of the present paper can be briefly summarized as:1) We discuss the minimal feedback rate without differential feedback. 2) We propose a differential feedback scheme by exploiting the temporal and spectral correlations, and 3) We derive the minimal differential feedback rate expression over MIMO doubly selective fading channel.

The rest of the paper is organized as follows: In Section II, we describe the differential feedback model as well as the statistics of the doubly selective fading channel. In Section III, we propose a differential feedback scheme by exploiting the two-dimensional correlations and derive the minimal feedback rate. In Section IV, we provide some simulation results showing the performance of the proposed scheme.

II. SYSTEM MODEL

In this paper, we assume that the down-link channel is a mobile wireless channel which is always correlated in time and frequency domains, while the up-link channel is a limited feedback channel.

A. Statistics of the down-link channel

Since the channel corresponding to each antenna is independent and with the same statistics, we can describe the separation property of the channel frequency response H(t, f ) at time t for an arbitrary transmit and receive antenna pair [START_REF] Li | Robust channel estimation for OFDM systems with rapid dispersive fading channels[END_REF]

r H (∆t, ∆f ) = E {H (t + ∆t, f + ∆f ) H * (t, f )} = σ 2 H r t (∆t) r f (∆f ) , (1)
where E {•} denotes expectation function, the superscript (•) * denotes complex conjugate. σ 2 H is the power of the channel frequency response. r t (∆t) and r f (∆f ) denotes the temporal and spectral correlation functions, respectively.

Assuming that the channel frequency response stays constant within the symbol period t s and the subchannel spacing f s , the correlation function for different periods and subchannels is written as

r H [∆m, ∆n] = σ 2 H r t [∆m] r f [∆n] , (2)
where r t [∆m] = r t (∆mt s ) and r f [∆n] = r (∆nf s ). Furthermore, if we just consider the time domain, the correlated channel can be modeled as a time-domain first-order autoregressive process (AR1) [START_REF] Baddour | Autoregressive modeling for fading channel simulation[END_REF]

H m,n = α t H m-1,n + 1 -α 2 t W t , (3)
where H m,n denotes the channel coefficient of the mth symbol interval and the nth subchannel, W t is a complex white noise variable, which is independent of H m-1,n , with variance σ 2 H . The parameter α t is the time autocorrelation coefficient, which is given by the zero-order Bessel function of first kind α t = r t [1] = J 0 (2πf d t s ), where f d is the Doppler frequency [START_REF] Gans | A power-spectral theory of propagation in the mobile-radio environment[END_REF].

Similarly, if we just consider the frequency domain, the correlated channel can also be represented as a frequencydomain AR1 [START_REF] Sun | Asymptotic capacity of multicarrier transmission with frequency-selecive fading and limited feedback[END_REF]

H m,n = α f H m,n-1 + 1 -α 2 f W f , (4)
where W f is a complex white noise variable, which is independent of H m,n-1 , with variance σ 2 H . The parameter α f determines the correlation between the subchannels, which is given by α

f = r f [1] = 1 √ 1+(2πfs∆) 2
, where ∆ is the root mean square delay spread [START_REF] Gans | A power-spectral theory of propagation in the mobile-radio environment[END_REF].

B. Differential Feedback Model

The system model with differential feedback is illustrated in Fig. 1. By using differential feedback scheme, the receiver just feeds back the differential CSI. We suppose that there are N t and N r antennas at the transmitter and receiver, respectively. The received signal vector at the mth symbol interval and the nth subchannel is given by y

m,n = H m,n x m,n + n m,n . (5)
In the above expression, y m,n denotes the N r × 1 received vector at the mth symbol interval and the nth subchannel. H m,n , a N r × N t channel fading matrix, is the frequency response of the channel. The entries are assumed independent and identically distributed (i.i.d.), obeying a complex Gaussian distribution with zero-mean and variance σ 2 H . Different antennas have the same characteristic in temporal and spectral correlations, α t and α f , respectively. Besides, there is no spatial correlation between different antennas. x m,n denotes the N t × 1 transmitter signal vector and is assumed to have unit variance. n m,n is a N r × 1 additive white Gaussian noise (AWGN) vector with zero-mean and variance σ 2 0 . Both x m,n and n m,n are independent for different m's and n's.

Through CSI quantization, the feedback channel output is written as [START_REF] Zhang | On the minimum feedback rate of MIMO block-fading channels with time-correlation[END_REF]- [START_REF] Zhang | On the minimum differential feedback rate for time-correlated MIMO Rayleigh block-fading channels[END_REF]

H m,n = Hm,n + E m,n , (6)
where Hm,n denotes the channel quantization matrix, and E m,n is the independent additive quantization distortion matrix whose entries are zero-mean and with variance D NrNt , where D represents the channel quantization distortion constraint.

The differential feedback is under consideration as shown in Fig. 1. We can use the previous CSI to forecast the present CSI H m,n at the transmitter

Ĥm,n = a 1 H m-1,n + a 2 H m,n-1 , (7)
where a 1 and a 2 are the coefficients of the channel predictor which will be calculated by using the minimum mean square error (MMSE) principle in the next section. Meanwhile, the receiver calculates the differential CSI, given the previous ones. The differential CSI can be formulated as

H d = Diff (H m,n |H m-1,n , H m,n-1 ) , (8)
where H d represents the differential CSI which obviously is the prediction error, and Dif f (•) is the differential function.

Then through limited feedback channel, H d should be quantized and fed back. Finally, The CSI reconstructed by combining the differential one and the channel prediction is utilized by the channel adaptive techniques. In this paper, we adopt the water-filling precoder, however, the analysis and conclusions given in this paper are also valid for other adaptive techniques.

The channel quantization matrix is decomposed as Hm,n = Ū Σ V+ using singular value decomposition (SVD) at the transmitter. Ū and V are unitary matrixes, and Σ is a nonnegative diagonal matrix composed of eigenvalues of Hm,n .

With the water-filling precoder, the closed-loop capacity can be obtained as [START_REF] Zhang | On the minimum feedback rate of MIMO block-fading channels with time-correlation[END_REF]- [START_REF] Zhang | On the minimum differential feedback rate for time-correlated MIMO Rayleigh block-fading channels[END_REF]

C erg = E log det I Nr + J • J + F -1 , (9)
where J = Hm,n VZ , J e = E m,n VZ , and

F = 1 A 2 I Nr + E [J e J + e |J],
where A represents the amplitude of signal symbol, and Z denotes a diagonal matrix determined by waterfilling [START_REF] Zhang | On the minimum feedback rate of MIMO block-fading channels with time-correlation[END_REF]

-[15]        z2 i = μ -(γ 2 i,i A 2 ) -1 , 0, γ2 i,i A 2 ≥ μ-1 otherwise Nt i=1 z2 i A 2 = N t A 2 , power constraint , (10)
where γi,i , i = 1, 2, ..., N t are the entries of Σ, μ denotes a cut-off value chosen to meet the power constraint.

It is obvious from ( 9) that the closed-loop ergodic capacity is determined by H m,n and Hm,n , and the loss of capacity is mainly caused by the quantization error. Therefore, given the limited feedback channel, the capacity can be enhanced by exploiting the channel correlations to reduce the quantization error.

III. MINIMAL DIFFERENTIAL FEEDBACK RATE

In this section, exploiting the temporal and spectral correlations, we study the minimal feedback rate that denotes the minimal feedback bits required per block to preserve the given channel quantization distortion.

We first describe the feedback rate using normal quantization. Without differential feedback scheme, the receiver feeds back H m,n to the transmitter. The information entropy of a Gaussian variable X with variance σ 2 is represented as [START_REF] Mceliece | The Theory of Information and Coding[END_REF]

h (X) = 1 2 log 2πeσ 2 . ( 11
)
Thus, the feedback load has positive relation with σ 2 H . Furthermore, taking quantization of the channel matrix into consideration, the feedback rate is determined by the rate distortion theory of continuous-amplitude sources [START_REF] Mceliece | The Theory of Information and Coding[END_REF]

R = inf I H m,n ; Hm,n : E d H m,n ; Hm,n ≤ D , (12)
where inf{•} denotes infimum function, I H m,n ; Hm,n denotes the mutual information between Hm,n and H m,n , and d H m,n ; Hm,n = H m,n -Hm,n 2 denotes the channel quantization distortion which is constrained by D.

Since the entries of H and H are i.i.d. complex Gaussian variables, the feedback rate can be written as

R = inf N t N r I H m,n ; Hm,n : E[d(H m,n , Hm,n )] ≤ d , ( 13
) where d = D
NtNr is the one-dimensional average channel quantization distortion. H m,n and Hm,n represent the entries of H m,n , Hm,n , respectively. Also, from (6) the one-dimensional channel quantization is written as

H m,n = Hm,n + E m,n . (14)
The mutual information can be written as

I H m,n ; Hm,n = h (H m,n ) -h H m,n Hm,n , . (15)
Combining ( 14), ( 15) can be rewritten as

I H m,n ; Hm,n ≥ h (H m,n ) -h (E m,n ) . ( 16
)
Substituting [START_REF] Li | Robust channel estimation for OFDM systems with rapid dispersive fading channels[END_REF] and ( 16) into [START_REF] Zhang | On the minimum feedback rate of MIMO block-fading channels with time-correlation[END_REF], we obtain

R = N r N t log σ 2 H d . (17)
From ( 17), the feedback rate required for the nondifferential feedback is very large. Nevertheless, by employing the temporal and spectral correlations, we can use the differential feedback scheme to reduce the feedback bits significantly. The transmitter can predict the present CSI H m,n depending on the previous ones in time domain H m-1,n and frequency domain H m-1,n . Then, the receiver quantizes H d ,or equivalently, the error of the channel prediction, and feeds back to the transmitter. Finally, the transmitter reconstructs the CSI by both the channel prediction and the differential CSI. It is obvious that the more accurate the channel is predicted, the less bits is fed back from the receiver. As H m-1,n , H m,n-1 and H m,n are correlated, an MMSE channel predictor can be constructed as [START_REF] Zhang | Cognitive Machine-to-Machine Communications: Visions and Potentials for the Smart Grid[END_REF], where the coefficients a 1 and a 2 are selected to minimize

MSE (a 1 , a 2 ) = E Ĥm,n -H m,n 2 . ( 18
)
The MSE represents the statistical difference between the predicted value and the true one. We can obtain the minimized quantization bits by minimizing the MSE.

We can rewrite H m,n as

H m,n = Ĥm,n + H d = a 1 H m-1,n + a 2 H m,n-1 + H d , (19)
where H d is the differential feedback load to minimize. By the orthogonality principle [START_REF] Papoulis | Probability, Random Variables, and Stochastic Processes[END_REF], a 1 , a 2 are determined by

E [(H m,n -a 1 H m-1,n -a 2 H m,n-1 ) H m-1,n ] = 0 E [(H m,n -a 1 H m-1,n -a 2 H m,n-1 ) H m,n-1 ] = 0 .
(20) Since the entries of H m,n ,H m-1,n ,H m,n-1 are i.i.d. complex Gaussian variables, the orthogonality principle can be rewritten as

E [(H m,n -a 1 H m-1,n -a 2 H m,n-1 ) H m-1,n ] = 0 E [(H m,n -a 1 H m-1,n -a 2 H m,n-1 ) H m,n-1 ] = 0 .
(21) Moreover, the one-dimensional frequency response of the channel can be represented as

H m,n = Ĥm,n + H d = a 1 H m-1,n + a 2 H m,n-1 + H d , ( 22
)
where H m,n , Ĥm,n , H m-1,n , H m,n-1 and H d represent the corresponding entries.

Direct calculation shows that (21) is equivalent to

r H [1, 0] -a 1 r H [0, 0] -a 2 r H [1, 1] = 0 r H [0, 1] -a 1 r H [1, 1] -a 2 r H [0, 0] = 0 . ( 23
)
With the separation property of the correlations of the channel frequency response (2), and combining 23) can be simplified by

r t [0] = r f [0] = 1 and r t [1] = α t , r f [1] = α f , (
a 1 σ 2 H + a 2 α t α f σ 2 H -α t σ 2 H = 0 a 1 α t α f σ 2 H + a 2 σ 2 H -α f σ 2 H = 0 . ( 24
)
From (24), a 1 , a 2 are given by

     a 1 = αt(1-α 2 f ) 1-α 2 t α 2 f a 2 = α f (1-α 2 t ) 1-α 2 t α 2 f . (25)
Combing ( 25) and ( 22), the one-dimensional MSE of the channel estimator is

MSE = Var (H d ) = σ 2 H 1 -a 2 1 -a 2 2 -2a 1 a 2 α t α f . (26)
Finally, the channel estimator Ĥm,n is given by

Ĥm,n = α t 1 -α 2 f 1 -α 2 t α 2 f H m-1,n + α f 1 -α 2 t 1 -α 2 t α 2 f H m,n-1 . ( 27
)
And combining ( 19) and ( 27), H m,n is given by

H m,n = α t 1 -α 2 f 1 -α 2 t α 2 f H m-1,n + α f 1 -α 2 t 1 -α 2 t α 2 f H m,n-1 + H d .
(28) Then, through the feedback channel, the error of the channel predictor H d can be fed back from the transmitter to the receiver. Similarly, from [START_REF] Li | Robust channel estimation for OFDM systems with rapid dispersive fading channels[END_REF], the feedback load is positive related with

Var(H d ) = σ 2 H 1 -a 2 1 -a 2 2 -2a 1 a 2 α t α f . Because ∂MSE ∂αt < 0, ∂MSE ∂α f
< 0, the feedback load can be much smaller than σ 2 H , the non-differential one, especially when the channel is highly correlated. For example, given α t > 0.75, α f > 0.75, then MSE| αt>0.75, α f >0.75 < MSE| αt=0.75, α f =0.75 = 0.28σ 2 H . From (28), taking quantization impact into consideration, the minimal differential feedback rate over doubly selective fading channels can be calculated by the rate distortion theory of continuous-amplitude sources in a similar way.

R = N r N t log a 2 1 + a 2 2 + 2a 1 a 2 α t α f d σ 2 H + V ar (H d ) d , (29)
where the channel predictor coefficients a 1 , a 2 are determined by

a 1 = αt(1-α 2 f ) 1-α 2 t α 2 f and a 2 = α f (1-α 2 t ) 1-α 2 t α 2 f . The average power of H d is V ar (H d ) = σ 2 H 1 -a 2 1 -a 2 2 -2a 1 a 2 α t α f . The detailed derivation is given in Appendix A.
The above expression gives the minimal differential feedback rate simultaneously utilizing the temporal and spectral correlations. From (29), the minimal differential feedback rate is a function of α t , α f and the channel quantization distortion d, and much smaller than that of the non-differential one [START_REF] Papoulis | Probability, Random Variables, and Stochastic Processes[END_REF].

IV. SIMULATION RESULTS AND DISCUSSION

In this section, we first provide the relationship between the MSE of the predictor and the two-dimensional correlations in Fig. 2. The minimal differential feedback rate over MIMO doubly selective fading channels is given in Fig. 3. Then, a longitudinal section of Fig. 3 is presented, where we assume the temporal correlation and spectral correlation is equal. Finally, we verify our theoretical results by a practical differential feedback system with water-filling precoder and Lloyd's quantization algorithm [START_REF] Lloyd | Least-square quantization in PCM[END_REF].

A. MSE of the predictor and Minimal Differential Feedback Rate

For simplicity and without loss of generality, we consider N r = N t = 2, and σ 2 H = 1. Fig. 2 presents the MSE between the predicted value and the true value. As the temporal or spectral correlation increases, the MSE decreases. Furthermore, when either α t or α f comes to one, the MSE tends to zero. Additionally, because α t and α f could be any value, we provide one of the longitudinal section of Fig. 3 where the temporal correlation is equal to the spectral correlation in Fig. 4. For comparison, the differential feedback compression only using one-dimensional correlation and the non-differential feedback scheme are also included in Fig. 4. It is observed from Fig. 4 that the scheme using both temporal and spectral correlations is always better than the scheme using only one-dimensional correlation. As the correlations increase, the two-dimensional differential feedback compression exhibits a significant improvement compared to one-dimensional one. This performance advantage even reaches up to 67% with α t = α f = 0.95.

B. Differential Feedback System with Lloyd's Algorithm

In this subsection, we consider the temporal correlation α t = 0.9, with carrier frequency 2 GHz, the normalized Doppler shift f d = 100 Hz and spectral correlation α f = 0.9, with ∆ = 8µs, which is a reasonable assumption [START_REF] Gans | A power-spectral theory of propagation in the mobile-radio environment[END_REF]. we design a differential feedback system using Lloyd's quantization algorithm to verify our theoretical results [START_REF] Lloyd | Least-square quantization in PCM[END_REF]. We use

Diff (H m,n |H m-1,n H m,n-1 ) = H m,n -a 1 H m-1,n - a 2 H m,n-1 as a differential function, where a 1 = αt(1-α 2 f ) 1-α 2 t α 2 f , a 2 = α f (1-α 2 t ) 1-α 2 t α 2 f
in the two-dimensional differential feedback compression and a 1 = α t , a 2 = 0 in the one-dimensional one.

The feedback steps can be summarized as follows. Firstly, based on Lloyd's quantization algorithm, the channel codebook can be generated according to the statistics of the corresponding differential feedback load at both transmitter and receiver. Secondly, the receiver calculates the current differential CSI H d . Thirdly, the differential CSI is quantized to the optimal coodbook value Hd according to the Euclidean distance. Finally, the transmitter reconstructs the channel quantization matrix by H m,n = a 1 H m-1,n + a 2 H m,n-1 + Hd .

In Fig. 5, we give the simulation results of the ergodic capacity employing Lloyd's algorithm. The theoretical capacity results are also provided in Fig. 5. We can see from Fig. 5 that the performance of the two-dimensional one are always better than the one-dimensional one, which verifies our theoretical analysis. As shown in Fig. 5, with the increase of feedback rate b, the ergodic capacities increase rapidly when b is small, and then slow down in the large b region, because when b is large enough, the quantization errors tend to zero. Also, the capacities of Lloyd's quantization are lower than the theoretical ones. The reasons are as follows. The Lloyd's algorithm is optimal only in the sense of minimizing a variable's quantization error, but not in data sequence compression while the channel coefficient H is correlated in both temporal and spectral domain. However, the imperfection reduces as b increases, because the quantization errors of both Lloyd's algorithm and theoretical results tend to zero with sufficient feedback bits b.

V. CONCLUSIONS

In this paper, we have designed a differential feedback scheme making full use of both the temporal and spectral correlation and compared the performance with the scheme without differential feedback. We have derived the minimal differential feedback rate for our proposed scheme. The feedback rate to preserve the given channel quantization distortion is significantly small compared to non-differential one, as the channel is highly correlated in both temporal and spectral domain. Finally, we provide simulations to verify our analysis.

APPENDIX A DERIVATION OF THE MINIMAL DIFFERENTIAL FEEDBACK RATE USING TEMPORAL AND SPECTRAL CORRELATIONS

The minimal differential feedback rate over MIMO doubly selective fading channel can also be derived by the rate distortion theory. Given Hm-1,n and Hm,n-1 at the transmitter, the differential feedback rate can be represented as (31)

The one-dimensional channel quantization equality can be written as

H m-1,n = Hm-1,n + E m-1,n H m,n-1 = Hm,n-1 + E m,n-1 . (32)
Similarly, (28) yields

H m,n = a 1 H m-1,n + a 2 H m,n-1 + H d , (33)
where Now we give the derivation of the correlation function of two noise terms r (E m-1,n , E m,n-1 ). From (32), the quantization error can be decomposed into two parts

a 1 = αt(1-α 2 f ) 1-α 2 t α 2 f , a 2 = α f (1-α 2 t ) 1-α 2 t α 2
E m-1,n = σ 2 H -σ 2 H σ 2 H H m-1,n + ψ m-1,n E m,n-1 = σ 2 H -σ 2 H σ 2 H H m,n-1 + ψ m,n-1 , (39)
where ψ m,n-1 = Hm,n-1 -

σ 2 H σ 2 H H m,n-1 ψ m-1,n = Hm-1,n - σ 2 H σ 2 H H m-1,n , (40)
ψ is a Gaussian variable with zero-mean and variance

Fig. 1 .

 1 Fig. 1. System model of the differential feedback over MIMO doubly selective fading channel

Fig. 2 .

 2 Fig. 2. The MSE of the predictor at the transmiter, for Nr = 2, Nt = 2, σ 2 H = 1 and D = 0.1.

Fig. 3

 3 Fig.3plots the relationship between the minimal differential feedback rate and the two-dimensional correlations with the channel quantization distortion D = 0.1. It is very similar to the MSE shown in Fig.2, because it presents the minimal bits required to quantize the differential CSI.

Fig. 3 .

 3 Fig. 3. The minimal differential feedback rate, for Nr = 2, Nt = 2, σ 2 H = 1 and D = 0.1.

Fig. 4 .

 4 Fig. 4. The relationship between the minimal feedback rate and temporal and spectral correlations, when they are equal, for Nr = 2, Nt = 2, σ 2 H = 1 and D = 0.1.

Fig. 5 .

 5 Fig. 5. The relationship between the ergodic capacity and feedback rate with Lloyd's algorithm in AR1 model for Nr = 2, Nt = 2, σ 2 H = 1 and SNR = 5dB.

  R=inf I H m,n ; Hm,n | Hm-1,n , Hm,n-1 :E d H m,n ; Hm,n ≤D .(30) Since the entries are i.i.d. complex Gaussian variables, (30) can be written as R=inf I H m,n ; Hm,n | Hm-1,n , Hm,n-1 :E d H m,n ; Hm,n ≤D .

f.

  The conditional mutual information I H m,n ; Hm,n | Hm-1,n , Hm,n-1 can be written asI H m,n ; Hm,n | Hm-1,n , Hm,n-1 =h H m,n | Hm-1,n , Hm,n-1 (34) -h H m,n | Hm,n , Hm-1,n , Hm,n-1 .First, we calculate h H m,n Hm-1,n , Hm,n-1 . Substituting (32) into (33), it yields thatH m,n =a 1 Hm-1,n +E m-1,n +a 2 Hm,n-1 +E m,n-1 +H d .(35) Substituting (35) into (34), we obtainI=h(a 1 E m-1,n +a 2 E m,n-1 +H d )-h E m,n | Hm-1,n , Hm,n-1 . (36) Considering inequality h E m,n | Hm-1,n , Hm,n-1 ≤ h(E m,n )(36) can be written asI ≥ h (a 1 E m-1,n + a 2 E m,n-1 + H d )h (E m,n ) . (37)Since E m-1,n , E m,n-1 and H d are complex Gaussian variables, and the information entropy of a Gaussian variables with variance σ 2 is h (X) =1 2 log 2πeσ 2 , we calculate the variance of a1 E m-1,n + a 2 E m,n-1 + H d V ar (a 1 E m-1,n + a 2 E m,n-1 + H d ) =a 2 1 d + a 2 2 d (38) +V ar H d 2 + 2a 1 a 2 r (E m-1,n , E m,n-1 ).

  Then the correlation function of E m-1,n and E m,n-1 can be calculated asr (E m-1,n , E m,n-1 ) = V ar (a 1 E m-1,n + a 2 E m,n-1 + H d ) = a 2 1 d + a 2 -2a 1 a 2 α t α f .

					Substituting (41) into (38), we obtain
						2 d	(42)
					+σ 2 H d + 2a 1 a 2	d 2 H σ 2	α t α f .
					From (31), (37) and (42), it yields that
					R = N r N t log a 2 1 + a 2 2 + where a 1 = αt(1-α 2 f ) 1-α 2 t α 2 f , a 2 = 2a 1 a 2 α t α f d σ 2 H α f (1-α 2 t ) 1-α 2 t α 2 f σ 2 H 1 -a 2 1 -a 2 2	+ and V ar (H d ) = V ar (H d ) , d (43)
	σ 2 H (σ 2 H -σ 2 H )
	σ 2
	σ 2 H -σ 2 H σ 2 H	2	α t α f =	d 2 σ 2	(41)

H

, independent with H.

H α t α f .

The associate editor coordinating the review of this paper and approving it for publication was Prof. Xianbing Wang. This work was partially supported by the National 973 project under grant 2013CB336700, National Nature Science Foundation of China under grant number 61222104 and 61061130561, the Ph.D. Programs Foundation of Ministry of Education of China under grant number 20110001110102, and the Opening Project of Key Laboratory of Cognitive Radio and Information Processing (Guilin University of Electronic Technology).