Marc Shapiro

Nuno Preguiça

Carlos Baquero

Marek Zawirski

Conflict-free Replicated Data Types

Keywords: Eventual consistency, replicated shared objects, large-scale distributed systems Cohérence à terme, objets partagés répliqués, système réparti de grande échelle

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, partitiontolerant 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. 1This 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 error-prone; 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 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 nonbyzantine 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 fault-tolerant manner are well-known in the literature, for instance gossip or anti-entropy 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.)

INRIA

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 2.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 state-based 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.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 2.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 ≤ Proof. As we assumed earlier a fully connected communication graph and that replicas transmit and merge state infinitely often, the conditions for eventual delivery are fulfilled. With no loss of generality, we assume that every operation is enabled (otherwise its invocation reduces to a no-op); furthermore we already assumed that an operation executes at a single replica. Under these conditions, an operation terminates if it has no infinite loops or recursion, which we assume to be true.

iff ∀m , x ≤ m ∧ y ≤ m ⇒ x ≤ m ∧ y ≤ m ∧ m ≤ m . It
We now focus on proving strong convergence. We first note that Definition 2.4 precludes spontaneous state changes or roll-backs: when a replica is in some state s, it can change state only by executing an update u or a merge m.

Consider replicas i and j. The proof assumption is c i = c j . Since updates are unique, these replicas can only have delivered the same updates in the following conditions:

-They are in the initial state, and therefore s i ≡ s j .

-During the execution, there was a point p, q when c p i ⊂ c q j . In p i , for k > p there is a merge that included a state s : s = s q j and all f k i operations are non mutating or merges with s ⊆ s q j . In p j , for k > q, all operations f k j are non mutating or merges with s ⊆ s q j . Therefore, since is a LUB, one has s i ≡ s j (≡ s q j ). -During the execution, there was a point p, q when c q j ⊂ c p i . Proved by simmetry with the previous case.

-During the execution, there was a point p, q when c p i ⊂ c q j and c q j ⊂ c p i . In p i , for k > p there is a merge that included a state s : s q j ⊆ s ⊆ s q j ∪ s p i and all f k i operations are non mutating or merges with s ⊆ s q j ∪ s p i . Converselly in p j , for k > q there is a merge that included a state s : s p i ⊆ s ⊆ s q j ∪ s p i and all f k j operations are non mutating or merges with s ⊆ s q j ∪ s p i . In these conditions, c i = c j = c p i ∪ c q j and due to the LUB properties of we have s i ≡ s j (≡ s p i s q j ≡ s q j s p i ).

INRIA

Since replicas transmit and merge state infinitly often, these conditions will occur infinitly often. Finally, by transitivity all replicas that deliver the same updates will depict equivalent states.

A CvRDT converges towards the LUB of the most recent updates. We require that x ≤ y ∧ y ≤ x ⇒ x ≡ y.

Op-based Commutative Replicated Data Type (CmRDT)

Alternatively to the state-based style, a replicated object may be specified in the operationbased (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. (their arguments may differ, e.g., t(a) and u(a ) in Figure 2). 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 2.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 happened-before 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 2.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.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.

Proof. We assume delivery of updates to all correct replicas by reliable causal broadcast, which fullfils their delivery specification P . Once delivered operations cannot be undelivered. We also assume that the all CmRDT methods are well formed and terminate. Thus, we now focus on proving strong convergence.

Consider any two correct replicas p i and p j . Under the assumptions, eventually the the two replicas will deliver the same operations (if no new operations are generated), and we have c i = c j . For any two updates f (a), f (a ) in c i : (i) If f (a) → f (a ), then by causal delivery assumption, ∀p i the apply order is consistent with causality K i (f (a)) < K i (f (a )); (ii) If they are not causally related, f (a) f (a ), then they must commute and can be delivered in any relative order. In any replica p i , both apply orders, K i (f (a)) < K i (f (a )) and K i (f (a)) > K i (f (a )), lead to the same effect. In all cases an equivalent abstract state s i ≡ s j is reached in the two replicas.

By transitivity, ∀i, j :

c i = c j ⇒ s i ≡ s j .
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, partitiontolerant 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 INRIA 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. 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.

CvRDTs and CmRDTs are equivalent

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 3.2 (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). 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 INRIA 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 maximum, 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] Gene | 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.)

INRIA 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 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 non-functional URLs. Once the linked page is created, the link become relevant, e.g., for navigation and for page-rank computation.

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. In the next section, we prove that this object is indeed a CmRDT.

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 effectupdate 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 effectupdate 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.

INRIA 6 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. Op-based 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 and Thomas invented the LWW-Register [START_REF] Johnson | The maintenance of duplicate databases[END_REF]. They propose a database of registers that can be created, updated and deleted, using the last-writerwins (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.

INRIA 7 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 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.

Figure 1 :Figure 2 :

 12 Figure 1: State-based replication

3. 2 . 1

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

  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).

Figure 3 :

 3 Figure 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.RR n°7687

RR n°7687

* 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. Carlos Baquero is partially supported by FCT project Castor (PTDC/EIA-EIA/104022/2008).

† French-language title, abstract and keywords

Proof that Directed Graph is a CRDT

In this section, we prove that the specification of Figure 3 represents a CRDT. As effect-updates are always enabled, and as inspection of the code shows that every method execution terminates, termination follows.

Lemma 5.1. addVertex(v ) and addVertex(v ) commute.

Proof. addVertex(v ) generates a unique identifier u ; addVertex(v ) generates unique identifier u . For any initial state S = (V, A), whatever order both operations are executed, the final state is the same

Proof. removeVertex(v ) computes a set, R , of pairs to be removed; removeVertex(v ) computes set R . For any initial state S = (V, A), whatever order both operations are executed, the final state is the same

Proof. addVertex(v ) generates unique identifier u ; removeVertex(v ) generates set R . (v , u ) ∈ R as u is a fresh unique identifier. Thus, for any initial state S = (V, A), whatever order both operations are executed, the final state is the same

Proofs for arcs are similar, so we omit them. We finally need to prove that any operation on vertices and arcs commute. However, as operation on vertices and operation on arcs modify disjoint internal sets, it is immediate that executing both operations in any order will lead to the same state. Proof. Effect-update methods are always enabled, and any pair of concurrent operations commute, per the lemmas above.


S Civiš
email: civis@jh-inst.cas.cz

I Matulková

J Cihelka

P Kubelík

K Kawaguchi

V E Chernov

Low-excited f, g and h-states in Au, Ag and Cu observed by FTIR spectroscopy in 1000-7500 cm -1 region

Keywords: numbers: 52.38.Mf, 07.57.Ty, 32.30.Bv, 31.15.B- Time-resolved Fourier transform infrared spectroscopy, atomic ablation, Rydberg states, dipole transition matrix elements

Low-excited f-, g-and h-states in Au, Ag and Cu observed by Fourier-transform infrared spectroscopy in the 10007500 cm1 region S Civiš, I Matulková, J Cihelka, P Kubelík, K Kawaguchi,

Introduction

The atomic states with high angular momentum are of interest for various problems of atomic physics. Since Fano's formulation of the fundamental principles of large angular momentum transfer in electron-atom scattering (Fano, 1974), the high-l states have been shown to play an important role in understanding the correlation effects in processes such as the excitation and decay of autoionizing states (Napier et al., 2008;Themelis, 2010). Atomic Rydberg states with a high orbital momentum are nonpenetrating states, i.e. the Rydberg electron in such states moves far away from the atomic core. Therefore these high-l states have very small quantum defects determined by long-range interaction with the atomic core (Lundeen, 2005). These interactions are described by simple analytical expressions that allow to extract the characteristics of the atomic core ion as polarizabilities, multipole momenta from precise microwave (Hanni et al., 2008) or optical (Keele et al., 2010) measurements of high-l states (for the use of high-l spectroscopy for the measurement of some relativistic interaction constants see (Lundeen, 2005)). Note that the theoretical calculations of these values depends crucially on very precise atomic wavefunction behavior in the vicinity of the nucleus, and therefore the above measurements can also be considered as a test of the atomic ab initio calculations.

The above mentioned measurements (Hanni et al., 2008;Keele et al., 2010) were performed for Rydberg multiplets corresponding to the principal quantum numbers n = 9..10 by observing transitions from these levels to states with n = 20..21 or n = 30..31. At the same time, information about low-lying states with l ≥ 4 is rather scarce. For instance, no g-levels are reported for Au; only 5g-levels are listed for Ag and Cu (the high Rydberg ng levels of Cu with n = 23..28 were studied using microwave spectroscopy (MacAdam et al., 2009)). No h-states have been reported for the above atoms. The present paper attempts to fill this gap; this is continuation of our study of the IR spectra of metals started in previous works (Civiš et al., 2010;Civiš et al., 2010Civiš et al., , 2011)).

We show that g-and h-states with n = 5..7 play a key role in the interpretation of the infrared spectra of Au, Ag and Cu arising in pulsed laser ablation of the metal targets in a vacuum. Some emission lines in the 2000-4000 cm -1 range were previously reported by us (Civiš et al., 2010;Civiš et al., 2010) with incorrect identification; after having performed the present measurements to cover the 1200-1600, 4100-5000 and 5200-7500 cm -1 ranges, we are able to discover the 5g-state for the gold and the 6hstates for all three metals considered. The energies of n g-and n h-states can easily be predicted roughly using the Rydberg formula and then refined using the measured line wavenumbers. These states allow us to give consistent classification for all lines observed in the four IR ranges mentioned.

Methods

In the present paper we report the IR emission spectra of Au, Ag and Cu atoms recorded using time-resolved Fourier-transform spectroscopy of the metal vapors produced during the ablation of the metal targets by a high-repetition rate (1.0 kHz) pulsed nanosecond ArF laser (λ = 193 nm, output energy of 15 mJ) in a vacuum (10 -2 Torr). The experimental setup has already been described in detail in our previous papers (Civiš et al., 2010;Kawaguchi et al., 2008). As compared to our previous studies of the spectra of these atoms (Civiš et al., 2010;Civiš et al., 2010Civiš et al., , 2011) ) this present work records their FTIR spectra in four spectral ranges (1200-1600, 1900-3600, 4100-5000 and 5200-7500 cm -1 ). In 1200-1600 cm -1 range we used a high-sensitivity MCT detector that allowed us to record the spectra with a reasonable signal-to-noise ratio (SNR) as compared to the previous work (Civiš et al., 2010). For the measurements in the 1900-3600, 4100-5000 and 5200-7500 cm -1 ranges an InSb detector was used. Parts of the measured spectra are shown in Figure 1.

For data sampling we used the so-called 1/3 sampling, where the scanner rate was set to produce a 3 kHz HeNe laser interference signal, the ArF laser oscillation was triggered, and 30 sets of time-resolved data were recorded with a preset time interval of 1 µs. Three scans were needed for a complete interferogram, and only 5 scans were coadded to improve the SNR. The spectral resolution in such a procedure was about 0.1 cm -1 . We also performed measurements with only one scan but with a higher resolution of about 0.017 cm -1 and worse SNR. The acquired spectra were postzerofilled (zero filling 2, trapezoid apodization function) using Bruker OPUS software and subsequently corrected by subtracting the blackbody background spectrum. The wavenumbers, line widths and their intensities (as well as the uncertainties for these quantities) were then obtained using a fitting to, e.g., Gaussian line shape. For some lines we resolved their hyperfine structure. In such cases we reported each hyperfine multiplet as a single Gaussian line whose position p, full width at half maximum (FWHM) w and intensity Ā can be obtained using the averaging procedure:

Ā = A i ; ∆ Ā = (∆A i ) 2 1 2 p = 1 Ā p i A i ; ∆p = 1 Ā (A i ∆p i ) 2 + (p i -p) 2 (∆A i ) 2 1 2 w = 1 Ā A i [w 2 i + (p -p i ) 2 ] = -p 2 + 1 Ā A i (w 2 i + p 2 i ) ( 1 ) ∆ w = 1 2 w ∂ w2 ∂w i ∆w i 2 + ∂ w2 ∂p i ∆p i 2 + ∂ w2 ∂A i ∆A i 2 1 2 ∂ w2 ∂w i = 2A i w i Ā ; ∂ w2 ∂p i = 2A i (p i -p) Ā ; ∂ w2 ∂A i = (p i -p) 2 + w 2 i -w2 Ā .
Here the sum runs through all components of the multiplet; p i , w i and A i are the positions, FWHMs and intensities of the multiplet components; ∆ represents uncertainties. For each component these quantities were obtained by a Gaussian fitting; ) for all metals corresponds to the 5g-6h transition.

an example of such fitting of hyperfine components together with the resulting averaged lines is given in Figure 3 below. The Equations 1 have a clear physical meaning: A is determined as the area under the spectral line, p is the "center of gravity" of the multiplet, w can be considered to be proportional to the root mean square deviation.

The line identification in the present work essentially uses the dipole matrix elements (line strengths) for the transition between the (Nd 10 )nl j states of Cu (N = 3), Ag (N = 4) and Au (N = 5). We report here the results of the dipole transition moment calculation for gold only since the corresponding tables for silver and copper have been already published in our previous papers (Civiš et al., 2010) and (Civiš et al., 2011) correspondingly. The Fues model potential method (FMP) for these calculation was outlined in the previous paper (Civiš et al., 2010); the choice of the radial quantum number n r (which is equal to the number of nodes of the radial wavefunction) for all the atoms under study is given in Table 1.

Table 1. Radial quantum number n r for (Nd 10 )nl j states of Cu (N = 3), Ag (N = 4) and Au (N = 5) used in the Fues model potential calculation of dipole matrix elements in the present work

l = 0 l = 1 l = 2 l = 3 l ≥ 4 Cu n -4 n -4 n -4 n -l -1 n -l -1 Ag n -5 n -5 n -5 n -l -1 n -l -1 Au n -6 n -6 n -5 n -5 n -l -1
The procedure for extracting the energy values for the levels involved in the observed transitions is briefly described in our previous paper (Civiš et al., 2010). Since it implies a least-square fitting, it is obvious that adding new transitions to this procedure can slightly change (and, generally speaking, improve) the output results for the energy levels. Indeed, as a rule, they demonstrate slight differences (within the specified error range) from those reported in our previous studies (Civiš et al., 2010;Civiš et al., 2010Civiš et al., , 2011) ) based on fewer set of observed transitions. In some cases (e.g., for Au) the discrepancies are not small and they are caused by the new classification of some transitions given in the present paper, having taken into account the whole set of the observed lines. We consider these values (shown in Tables 4, 7 and 9) as recommended. All the uncertainties in the tables below are given in round brackets after the corresponding values and should be treated as their rightmost significant digits, e. g. 123.4(56) means 123.4 ± 5.6.

Results and discussion

Au

Our measurements of Au FTIR spectra were performed in three spectral regions (1200-1600, 1900-3600, 5200-7500 cm -1 ) and this has resulted in some corrections to our previous identification (Civiš et al., 2010) of Au I levels which were based on the 1900-3600 cm -1 range only. The measured emission lines are presented in Table 2.

The strongest lines measured in the 5200-7500 cm -1 region are the 5459.12 and 5537.4 cm -1 lines. Together with the weaker 5454.9 cm -1 line, they are easily classified as due to the 6d-5f transition triplet. This yields the fine-structure splitting about 4 cm -1 between the 5f5 2 and 5f 7 2 states. The latter value, in turn, suggests that the two strongest lines (2522.69 and 2518.49 cm -1 ) in the 1900-3600 cm -1 region are due to the 5f-5g transitions. Following the first (and the only) report on the IR spectrum of gold (George et al., 1988), in our previous paper (Civiš et al., 2010) we gave another classification for these lines based on measurements in the 1800-4000 cm -1 range only. The present classification is essentially based on the 5g states discovered from measurements in the 5200-7500 cm -1 range. The correctness of the present assignment is supported by the calculations of the dipole transition matrix elements presented in Table 3. Indeed, according to this table, the most intense lines in the 1900-3600 cm -1 region should correspond to the 5f 2 line, has significantly low intensity and is blended by the strong 2518.49 cm -1 line, due to small (about 0.01 cm -1 , see Table 4) fine-structure splitting between the 5g levels.

The presence of only one very prominent line, 1347.34 cm -1 , in the 1200-1600 cm -1 range can be easily explained by assigning it as due to the 5g-6h transition. The triplet of possible lines is not resolved because of the small fine-structure splitting of the 5g and 6h levels. This classification is also supported by Table 3 which lists the 5g-6h transition as the most probable in the 1200-1600 cm -1 range (if we take into account the sum of the intensities of the three 5g7 Given the energy levels of the 5f, 5g and 6h states, one can easily predict the energies of the nf, ng and nh levels by the extrapolation of the Rydberg formula assuming the quantum defects to be independent of n. Some levels (with n = 6, 7) of such a series are involved into the observed transitions, and their energies can then be determined from the measured wavenumbers. The discovery of the ng and nh levels allows us now to make some corrections to our previous classification (Civiš et al., 2010) based on emission measurements in the 1800-4000 cm -1 range only. The summary of corrections to the previous results are given in Table 5; and we consider the present classification as the recommended one. Some weak lines reported in the previous work were not observed in the present measurements; this could be due to different plasma conditions in two experiments. Note that there are also some differences between the line sets observed in our measurements and in the paper by George et al. (1988): we observed no lines with wavenumbers greater than 6000 cm -1 from those listed by George et al. (1988). In turn, in the 2100-3100 cm -1 range, their list lacks all lines observed in the present work except the 2518.49 cm -1 line. This is probably caused by the different excitation mechanisms in the hollow cathode discharge (George et al., 1988) and laser ablation experiments.

Table 4 contains the revised energy values of the Au levels obtained from the present measurement in three spectral ranges. The majority of the energies are close to the previously reported values. The most significant discrepancy (about 8 cm -1 ) is found for the 5f 5 2 term whose energy value was reported 70 years ago (Platt and Sawyer, 1941). Together with the incorrect classification of the 2518.49 cm -1 line, this old-reported energy value has caused some problems with discrepancies between the measured and calculated wavenumbers in the paper by George et al. (1988George et al. ( , bottom of p. 1501)). With our new classification involving g and h-states, the observed set of lines and levels seems to be self-consistent and we consider the energy values of the levels presented in Table 4 to be the recommended ones. p Table 2. Au I lines and their identification. Each of the four spectral ranges (1200-1600, 1900-3600, 4100-5000 and 5200-7500 cm -1 ) has its own scale of arbitrary units for the emission intensity. 4). The Ritz wavenumbers ν and air wavelengths λ are calculated using these energy values.

Transition i-k Lower level (cm -1 ) Upper level (cm -1 ) ν (cm -1 ) λ (nm)
S ik (a. u.)

f ik A ki (s -1 ) 6g 9 2 -8f

Ag

The emission spectra of Ag were recorded in the three ranges, 1200-1600 cm -1 , 4100-5000 cm -1 and 5200-7500 cm -1 . Only for the latter range have we found an earlier (but century-old) study [START_REF] Randall | [END_REF] of Ag lines which reported four lines: 5438.6, 5460.7, 5740.0 and 5943.9 cm -1 . Our results (six lines in Table 6 below) display some differences but obviously have a much higher accuracy, which made it for us possible to resolve the fine structure of the 4f states. Indeed, our previous measurement (Civiš et al., 2010) has shown that the fine splitting of the f-states in Ag is quite small (0.122 cm -1 and 0.245 cm -1 for the 5f and 7f states correspondingly) and that it is considerable low as compared to the fine-structure splitting of the f-states in Au and Cu. The fine structure of the 4f state in Ag remained unresolved. We noted (Civiš et al., 2010) that, to obtain reliable values of the finesplitting component of the 4f levels, one should consider the transitions from these states to nd states, since the latter have larger fine-structure splitting. Such transitions (with n = 5) have been observed in the present work in the 5200-7500 cm -1 range and this allowed us to resolve the fine structure for 4f state. We have also resolved this for the 6g state, using the 5f-6g doublet measured at 1363 cm -1 . Unfortunately, our data is still not sufficient to resolve the fine structure of the 5g state from the most prominent 2506 cm -1 line since, due to its high intensity and comparatively large width, it cannot be reliably fitted by a two-peak curve. We show this line together with the less intensive 1363 cm -1 doublet in Figure 2.

The present measurements in the 1200-1600 cm -1 range also help us to resolve some problems with line identification in the previous measurement (Civiš et al., 2010) using a low-sensitive MCT detector resulting in a high noise level. We are able to observe the 7d-6f doublet at 1336.6 and 1342.15 cm -1 while the most prominent 1345.6 cm -1 line (incorrectly classified as due to the 7d 3 2 -6f 5 2 transition (Civiš et al., 2010)) corresponds to the 5g-5h transition, similarly as in the case of Au.

Table 7 presents the energies of the Ag levels involved in the observed transitions. Their uncertainties are lower than those for Au and Cu (see Table 9 below), since for the Ag levels we used the high-accuracy reference values published by Pickering and Zilio (2001). Most of the values do not differ much from the previous measurement (Civiš et al., 2010) and from other sources. The exception is the 6f5 2 level whose value was extracted using an incorrect identification of the 1345.6 cm -1 line (Civiš et al., 2010). We did not include in this table some levels for which we have obtained here exactly the same values as reported in the previous work (Civiš et al., 2010). (Brown and Ginter, 1978) e (Jannitti et al., 1979) f (George et al., 1988) Table 5. A summary of corrections to the previous results (Civiš et al., 2010) 6. Ag I lines and their identification. Each of the three spectral ranges, 1200-1600 cm -1 , 4100-5000 cm -1 and 5200-7500 cm -1 , has its own scale of arbitrary units for the emission intensity. ) in Ag I. The arbitrary units for intensity have different scales on vertical axes in the inset and in the main graph.

Cu

To our knowledge, the only study of the Cu spectrum in the 5200-7500 cm -1 range was reported about 60 years ago (Shenstone, 1948) where four (5484.1, 5496.6, 6003.2 and 6245.0 cm -1 ) lines were mentioned. Our measurement yielded 8 lines (see Table 8 below) which can be easily classified as consisting of two triplets (4d-4f and 5p-5d) and the 5s-5p doublet. The latter consists of two very close lines which are due to the small (about 0.3 cm -1 ) fine-structure splitting of the 5p term of Cu I. This doublet is shown in Figure 3; the hyperfine structure is clearly seen. The reported (Table 8) parameters of such multiplets are averaged over the hyperfine structure according to Equations 1.

Similarly to Au and Ag, the most prominent line (1344 cm -1 ) of Cu in the 1200-1600 cm -1 range is due to the 5g-6h transition. The 1277 and 1302 cm -1 lines are easily identified using energy values taken from the literature. The remaining four lines are identified as being due to the two most prominent pairs of the 5f-6g and 6d-6f triplets; this identification is based on a comparison of the corresponding line strengths calculated using the FMP method. The information about the 6h term extracted from the measurements in the 1200-1600 cm -1 region makes it possible for us to identify the 2153 cm -1 line (not reported in the previous work (Civiš et al., 2011)) as due to the 5g-7h transition.

The revised Cu I level energies using the present measurements are given in Table 9. For the majority of levels, the difference between the results reported in this and in other works is of the same order of magnitude as the uncertainty specified. Nevertheless, the present values of the 6g7 2 , 9 2 levels differ by almost 0.6 cm -1 as compared to our previous work (Civiš et al., 2011). We consider the present values to be preferable since these are extracted here from stronger lines (1354 and 1361 cm -1 ) while the previous work used the less prominent 3837 and 3840 cm -1 lines which lie at the boundary of the 42556.152 (Pickering and Zilio, 2001) detector's sensitivity. The present values of 7g 7 2 , 9 2 also differ from the values reported previously (Civiš et al., 2011): by 0.475 and 1.237 cm -1 respectively. We consider the present values to be the recommended ones, since in their extraction far more intensive (4646.928 and 4649.903 cm -1 ) lines were involved as compared to the weak (2163.89 and 2171.118) lines used for extracting 7g 7 2 , 9 2 in the previous work (Civiš et al., 2011). The present values display fine-structure splitting of about 0.4 cm -1 which is more realistic than the 1.18 cm -1 -splitting resulting from the previous data (Civiš et al., 2011).

Conclusion

The present paper continues our studies of the IR emission spectra of metals in laserinduced plasma using Fourier-transform spectroscopy. Our measurements of Au, Ag and Cu spectra in four ranges (1200-1600, 1900-3600, 4100-5000 and 5200-7500 cm -1 ) result in the reporting of 64 lines (32 for Au, 12 for Ag and 20 for Cu) not reported previously and in the refinement of 19 lines already published (9 for Au, 6 for Ag and 4 for Cu). We also provide a new classification for 4 Au lines and 1 Ag line.

The majority of the lines are due to transitions between the N d 10 nl j states with closed core (N = 3, 4, 5 for Cu, Ag and Au correspondingly) and n = 4..10. The line classification is performed using relative line strengths expressed in terms of transition dipole matrix elements calculated with the help of the Fues model potential. We show the results for the transition probabilities and oscillator strengths for transitions between the reported 5d 10 nl j states of Au I (the previous papers contained such results for Ag (Civiš et al., 2010) and Cu (Civiš et al., 2011)).

For the classification of the observed IR lines, an important role is played by the f-, g-and h-states including those discovered in the present measurements. For all three elements considered, the most intensive emission line in 1200-1600 cm -1 corresponds to the 5g-6h transition (for an example, see the transition probability table 3 for Au). Indeed, due to small quantum defects (of the order of 10 -2 and 10 -3 for theg and h states respectively) this transition yields emission lines with close wavenumbers (1345-1347 cm -1 ) for Au, Ag and Cu (see Figure 1).

The most prominent lines in the 1900-3600 cm -1 range are the pairs nf 5 2 -5g 7 2 and nf 7 2 -5g 9 2 where n is the principal quantum number of the first valence f-state; n = 5 for Au and n = 4 for Ag and Cu. For Au and Cu this nf-5g doublet occurs at 2517-2522 cm -1 (see Table 2 and the previous paper (Civiš et al., 2011)). Due to very small fine splitting of 4f state (E 4f 7 2 -E 4f 7 2 = 0.016 cm -1 in Ag (see Table 7) we saw only one Ag 4f-5g line (Civiš et al., 2010) at 2506 cm -1 .

In the 4100-5000 cm -1 range the most prominent emission takes place from the Table 8. Cu I lines and their identification. Each of the four spectral ranges, 1200-1600, 1900-3600 cm -1 (only 2153 cm -1 line), 4100-5000 and 5200-7500 cm -1 , has its own scale of arbitrary units for the emission intensity. 7g-state to the first valence nf-state. The strongest lines in the 5200-7500 cm -1 are due to the n d-nf transitions from first valence nf-states (with n values given above) and the first valence n d-states (n = 6, 5, 4 for Au, Ag and Cu correspondingly).

From the recorded spectra we extract revised values for the energies of 70 known levels (23 for Au, 20 for Ag and 27 for Cu) and of 15 previously not reported f-, g-and h-levels (8 for Au, 3 for Ag and 4 for Cu). [START_REF] Ralchenko | NIST atomic spectra database (version 3.1.5)[END_REF]), 57948.71 (Shenstone, 1948) 3d 10 5g 7 2 57924.549(26) 57924.610 (Civiš et al., 2011) 3d 10 5g 9 2 57924.132(20) 57924.075 (Civiš et al., 2011) 3d 10 5f 7 2 57911.591(10) 57908.7 (Shenstone, 1948), 57911.090 (Civiš et al., 2011) 3d 10 5f 5 2 57905.120(10) 57905.2 (Shenstone, 1948), 57905.23 (Longmire et al., 1980), 57905.041 (Civiš et al., 2011) 3d 10 6d 5 2 57895.097(29) 57895.1 (Shenstone, 1948), 57895.084 (Civiš et al., 2011) 3d 10 6d 3 2 57893.042(27) 57893.05 (Shenstone, 1948), 57893.028 (Civiš et al., 2011 55391.292 (Shenstone, 1948), 55390.569 (Civiš et al., 2011) 3d 10 5d 3 2 55387.667(10) 55387.668 (Shenstone, 1948), 55387.621 (Civiš et al., 2011) 3d 10 6p 1 2 55027.748(26) 55027.74 (Shenstone, 1948), 55027.713 (Longmire et al., 1980), 55027.763 (Civiš et al., 2011) 3d 10 6p 3 2 54784.074(35) 54784.06 (Shenstone, 1948), 54784.073 (Longmire et al., 1980) 43137.209 (Shenstone, 1948)

Figure 1 .

 1 Figure1. Emission spectra of Cu, Ag and Au in the 1330-1380 cm -1 range. The most prominent line (near 1345-1348 cm -1 ) for all metals corresponds to the 5g-6h transition.

Figure 3 .

 3 Figure 3. The 5s 1 2 -5p 1 2 , 32 doublet lines of Cu I. The hyperfine components are fitted to Gaussian shape (thin curve), the parameters of the averaged lines (thick curves) are calculated using Equations 1.

Table 3 :

 3 FMP-calculated transition dipole moments (line strengths S ik , oscillator strengths f ik , transition probabilities A ki ) between the 5d 10 states of the Au atom observed in the present work. The energies of all levels are taken from the present measurement (see Table4) except that for the 7p3

	2	level (taken from George

Table 4 .

 4 Revised values of some levels of Au I

	Term					Energy (cm -1 )	Other sources
	5d 10 7h				72168.489(37)	This work
	5d 10 7g 9 2 5d 10 7g 7 2 5d 10 6h				72166.211(47) 72166.188(45) 71359.307(35)	This work This work This work
	5d 10 6g 7 2 5d 10 7f 5 2 5d 10 7f 7 2 5d 10 5g 9 2 5d 10 5g 7 2 5d 10 8d 5 2 5d 10 6f 7 2 5d 10 6f 5 2 5d 10 8d 3 2 5d 10 9p 3 2 5d 10 9p 1 2 5d 10 9s 1 2 5d 10 7d 5 2 5d 10 5f 5 2 5d 10 5f 7 2 5d 10 7d 3 2 5d 10 8p 3 2 5d 10 8p 1 2 5d 10 8s 1 2				71355.845(43) 71341.709(40) 71339.538(34) 70011.968(35) 70011.960(47) 70007.956(33) 69985.561(45) 69981.893(43) 69971.407(40) 69969.926(94) 69648.345(75) 68680.631(50) 67510.600(45) 67489.277(47) 67493.483(35) 67469.675(44) 67487.264(29) 66935.902(29) 64742.879(29)	This work This work 71339.569 a This work This work 70007.6 b , 70007.975 c 69985.559 a 69988.172 a 69971.3 b , 69971.418 c 69969.89 d , 69967.489 a 69648.28 d , 69950.681 a 68680.5 b , 68680.628 c 67510.7 b , 67510.605 c 67490.0 b , 67489.276 f , 67491.487 a 67485.3 b , 67485.292 a 67469.4 b , 67469.683 c 67487.11 d , 67487.291 a 66935.76 d , 66935.941 a 64742.4 b , 64742.896 c , 64742.911 a
	5d 9 3 2	6s	2	6p 3 2	2 3	63005.873(38)	63005.1 b (20 o state), 63005.7 e (J series, n = 6), 63005.883 f
	5d 9 3 2 5d 10 6d 5 6s 2 5d 10 6d 3 2	2	6p 3 2	1 2	62568.757(131) 62568.7 e (I series, n = 6) 62034.361(35) 62033.7 b , 62034.363 c 61951.885(48) 61951.6 b , 61951.886 c
	5d 9 3 2	6s	1	6p 3 2	3 2	61563.839(20)	61563.840 f , 61563.7 e (E series, n 61563.3 b (19 o state)	=	6),
	5d 10 7p 1 2				60033.076(20)	60033.0 b , 60032.85 d , 60033.076 f
	5d 9 3 2	6s	2	6p 1 2	3 2	58846.546(19)	58845.1 b (16 o state), 58845.414 c (16 o state), 58846.4 e (H series, n = 6), 58846.546 f
	5d 10 7s 1 2				54485.235(50)	54484.9 b , 54485.235 c
	a (Civiš et al., 2010)

b

(Platt and Sawyer, 1941)

c

(Ehrhardt and Davis, 1971) d

Table 7 .

 7 Revised values of some levels of Ag I

	Term	Energy (cm -1 ) Other sources
	4d 10 7g	58864.644(7)	This work
	4d 10 9d 5 2 4d 10 10s 1 2 4d 10 6h	58864.603(16) 58864.614 (Pickering and Zilio, 2001) 58478.051(30) 58478.047 (Pickering and Zilio, 2001) 58057.140(4) This work
	4d 10 6g 9 2 4d 10 6g 7 2 4d 10 8d 5 2 4d 10 6f 5 2 4d 10 6f 7 2 4d 10 5g	58054.713(3) 58054.711(4) 58053.388(8) 58041.987(5) 58042.063(4) 56711.565(3)	58054.723 (Civiš et al., 2010) 58054.723 (Civiš et al., 2010) 58053.404 (Pickering and Zilio, 2001) 58045.481 (Civiš et al., 2010) This work 56711.1 (Shenstone, 1940)
	4d 10 7d 5 2	56705.467(2)	56705.498 (Pickering and Zilio, 2001), 56705.435 (Civiš
			et al., 2010)
	4d 10 7d 3 2	56699.832(3)	56699.768 (Pickering and Zilio, 2001), 56699.911 (Civiš
			et al., 2010)
	4d 10 5f 7 2 4d 10 5f 5 2 4d 10 8p 3 2	56691.397(2) 56691.275(2) 56660.597(3)	56691.4 (Shenstone, 1940), 56691.397 (Civiš et al., 2010) 56691.4 (Shenstone, 1940), 56691.275 (Civiš et al., 2010) 56660.559 (Pickering and Zilio, 2001), 56660.556 (Civiš
			et al., 2010)
	4d 10 4f 7 2 4d 10 4f 5 2 4d 10 7p 3 2	54204.745(3) 54204.729(2) 54121.108(1)	54204.73 (Shenstone, 1940) 54204.73 (Shenstone, 1940) 54121.129 (Pickering and Zilio, 2001), 54121.059 (Civiš
			et al., 2010)
	4d 10 7p 1 2	54041.037(2)	54040.99 (Brown and Ginter, 1977), 54041.087 (Civiš
			et al., 2010)
	4d 10 7s 1 2	51886.965(1)	51886.971 (Pickering and Zilio, 2001), 51886.954 (Civiš
			et al., 2010)
	4d 10 6p 3 2	48500.810(1)	48500.805 (Pickering and Zilio, 2001), 48500.804 (Civiš
			et al., 2010)
	4d 10 6p 1 2 4d 10 6s 1 2	48297.406(1) 42556.147(1)	48297.402 (Pickering and Zilio, 2001; Civiš et al., 2010)

Table 9 .

 9 Revised values of some levels of Cu I

	Term	Energy (cm -1 ) Other sources
	3d 10 7g 7 2 3d 10 7g 9 2 3d 10 7f 5 2 3d 10 7f 7 2 3d 10 6h	60076.634(25) 60076.159 (Civiš et al., 2011) 60076.217(19) 60074.980 (Civiš et al., 2011) 60071.634(11) This work 60071.199(9) 60071.510 (Civiš et al., 2011) 59268.422(20) This work
	3d 10 6g 7 2 3d 10 6g 9 2 3d 10 6f 7 2 3d 10 6f 5 2 3d 10 7d 5 2 3d 10 7d 3 2 3d 10 7p 3 2	59266.776(10) 59267.202 (Civiš et al., 2011) 59266.026(10) 59266.676 (Civiš et al., 2011) 59259.436(30) This work 59259.916(28) This work 59250.565(27) 59250.72 (Shenstone, 1948) 59249.303(26) 59249.46 (Shenstone, 1948) 57948.572(11) 57948.57

Acknowledgments

This work was financially supported by the Grant Agency of the Academy of Sciences of the Czech Republic (Grant No. IAA400400705).