Stéphane Weiss
email: weiss@loria.fr

Pascal Urso
email: urso@loria.fr

Pascal Molli
email: molli@loria.fr

Logoot : a Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks

Massive collaborative editing becomes a reality through leading projects such as Wikipedia. This massive collaboration is currently supported with a costly central service. In order to avoid such costs, we aim to provide a peerto-peer collaborative editing system. Existing approaches to build distributed collaborative editing systems either do not scale in terms of number of users or in terms of number of edits. We present the Logoot approach that scales in these both dimensions while ensuring causality, consistency and intention preservation criteria. We evaluate the Logoot approach and compare it to others using a corpus of all the edits applied on a set of the most edited and the biggest pages of Wikipedia.

Introduction

Collaborative editing (CE) systems allow distant users to modify the same data concurrently. The major benefits are: reducing task completion time, getting different viewpoints, etc... Wikis, online office suites and version control systems are the most popular collaborative editing tools.

Several collaborative editing systems are becoming massive: they support a huge number of users to obtain quickly a huge amount of data. For instance, Wikipedia is edited by 7.5 million of users and got 10 million of articles in only 6 years. However, most of CE systems are centralized with costly scalability and poor fault tolerance. For instance, the Wikimedia Foundation spent 2.7 million dollars between 2007 and 2008 for maintaining wiki servers 1 . To overcome these limitations, we aim to provide a peer-to-peer (P2P) CE system.

P2P systems rely on replication to ensure scalability. A single object is replicated a limited number of times in structured networks (such as Distributed Hash Tables) or a unbounded number of times in unstructured P2P networks. In all cases, replication requires to define and maintain consistency of copies. With a limited number of replicas, 1. http://wikimediafoundation.org/wiki/Donate/Transparency/en it is possible to maintain strong consistency models such as sequential consistency. For instance, some P2P replication systems are based on consensus algorithm [START_REF] Schütt | Scalaris: reliable transactional p2p key/value store[END_REF]. However, if the number of replicas grows, the communication cost becomes too expensive. Collaborative editing can rely on weaker consistency criteria that generate less traffic and that are more efficient. For instance, Git [START_REF] Torvalds | [END_REF] distributed version control system relies on causal consistency, Usenet [START_REF] Salz | InterNetNews: Usenet transport for Internet sites[END_REF] on eventual consistency, and CoWord [START_REF] Xia | Leveraging single-user applications for multi-user collaboration: the coword approach[END_REF], a real-time editing systems relies on CCI consistency .

CCI consistency have been proven suitable for replicated collaborative system [START_REF] Sun | Operational transformation in realtime group editors: Issues, algorithms, and achievements[END_REF]. CCI consistency means Causality, Convergence, and Intention preservation. Thus, CCI consistency implies causal consistency and eventual consistency. Intention preservation means that an operation effect observed on a copy, must be observed in all copies whatever any sequence of concurrent operations applied before.

Many algorithms have been proposed for maintaining CCI consistency. Some approaches [START_REF] Suleiman | Concurrent operations in a distributed and mobile collaborative environment[END_REF], [START_REF] Roh | How to design optimistic operations for peer-to-peer replication[END_REF] do no support P2P constraints such as churn. The others [START_REF] Cart | Asynchronous reconciliation based on operational transformation for p2p collaborative environments[END_REF], [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF], [START_REF] Shapiro | Designing a commutative replicated data type[END_REF] rely on data "tombstones". In these approaches, a deleted object is replaced by a tombstone instead of removing it from the document model. Tombstones cannot be directly removed without compromising the document consistency. Therefore, the overhead required to manage the document grows continuously.

In this paper, we present a new optimistic replication algorithm called Logoot that ensures CCI consistency for linear structures, that tolerates a large number of copies, and that does not require the use of tombstones. This approach is based on non-mutable and totally ordered object position identifiers. The time complexity of Logoot is only logarithmic according to the document size. We validate the Logoot algorithm with real data extracted from Wikipedia. In this paper, we show and analyze the results of this experiment.

P2P Collaborative Editing System

We make the following assumptions about P2P Collaborative Editing Systems (P2P CE) and their correction criteria.

A P2P CE network is composed by a unbounded set of peer P . Objects edited by the system are replicated on set of replicas R (with 0 < |R| ≤ |P |). Each replica has the same role and is hosted on one peer. A peer can host many replicas, each one of a different object. Peers can enter and leave the network arbitrary fast. We assume that each peer possesses a unique comparable site identifier.

The modifications applied on a replica are eventually delivered to all other replicas. We make no assumption about the kind of dissemination routine through the P2P network or the propagation time of modifications. When a modification is delivered to a replica, the modification is applied. Thus, the replica diverge in the short term. This kind of replication is known as optimistic replication [START_REF] Saito | Optimistic replication[END_REF] (or lazy replication).

According to [START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF], a collaborative editing system is considered correct if it respects the CCI criteria: Causality: This criterion ensures that all operations ordered by a precedence relation, in the sense of the Lamport's happened-before relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF], will be executed in the same order on every copy (causal consistency). Convergence: The system converges -i.e. all replicas are identical -when the system is idle (criteria also known as eventual consistency). Intention: The expected effect of an operation must be observed on all replicas. One definition of operations intention for textual documents is : delete A line is eventually removed from the document if and only if it has been deleted on, at least, one replica. insert A line inserted on a replica eventually appears on every replica. Moreover, the order relation between the document lines and the newly inserted line must be preserved on every replica (as long as these lines exist). Along these criteria, we add a numerical scalability criteria from [START_REF] Neuman | Scale in distributed systems[END_REF]. Scalability: The system must handle the addition of users or objects without suffering a noticeable loss of performance.

Related Work

In this section, we present the optimistic replication approaches that are known to scale according to the number of users in the network.

WOOKI [START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF] is a P2P wiki system based on Wooto, an optimization of Woot [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF]. The main idea of Woot is to treat a collaborative document as a Hasse diagram that represents the order induced by the insert operations. Therefore, the Wooto algorithm computes a linear extension of this diagram. WOOKI barely respects the CCI correction criteria. Indeed, the causality is replaced by preconditions. As a result, the happened-before relation can be violated in some cases. The convergence is ensured by the algorithm by using tombstones.

TreeDoc [START_REF] Shapiro | Designing a commutative replicated data type[END_REF] is a collaborative editing system which uses a binary tree to represent the document. Deleted lines are also kept as tombstones. The authors propose a kind of "2 phase commit" procedure to remove tombstones. Unfortunately, this procedure cannot be used in an opennetwork such as P2P environments. However, this approach proposes also an interesting general framework called Commutative Replicated Data Type (CRDT) to build distributed collaborative editors ensuring CCI criteria.

[7] proposes a distributed optimistic replication mechanism in the CRDT framework, that ensures the CCI criteria but using tombstones and vector clocks. Vector clocks (aka state vector) have a size proportional to the number of replicas in the network, and thus are not scalable when the number of users grow.

The Operational Transformation approach [START_REF] Ellis | Concurrency control in groupware systems[END_REF], [START_REF] Suleiman | Serialization of concurrent operations in a distributed collaborative environment[END_REF], [START_REF] Sun | Operational transformation in realtime group editors: Issues, algorithms, and achievements[END_REF], [START_REF] Li | An approach to ensuring consistency in peer-to-peer real-time group editors[END_REF] is a framework for building distributed collaborative editor. Except MOT2 [START_REF] Cart | Asynchronous reconciliation based on operational transformation for p2p collaborative environments[END_REF], all algorithms in this framework require the use of vector clocks and, thus, do not scale. MOT2 is a P2P peer-wise based reconciliation algorithm. This algorithm assumes the existence of transformation functions satisfying some properties. To our best knowledge, the only transformation functions for text document adapted [START_REF] Weiss | An undo framework for p2p collaborative editing[END_REF] for MOT2 are the Tombstone Transformation Functions [START_REF] Urso | Tombstone transformation functions for ensuring consistency in collaborative editing systems[END_REF] which are based on tombstones.

Thus, all of the above approaches that are usable on P2P networks are based on tombstones. According to the scalability definition, the tombstone cost is not acceptable on massive editing systems. For instance, for the most edited pages of Wikipedia2 , the tombstone storage overhead can represent several hundred times the document size. Tombstones are also responsible of performance degradation. Indeed, in all published approaches, the execution time of modification integration depends on the whole document size -including tombstones. Therefore, letting the number of tombstones growing degrades the performance.

Proposition

Our idea is based on the CRDT [START_REF] Shapiro | Designing a commutative replicated data type[END_REF] framework for collaborative editing. In the CRDT framework, modifications produced locally are re-executed on remote replicas. There is no total order on operations, thus, concurrent operations can be re-executed in different orders. The main idea of this framework is to use a data type where all concurrent operations commute. Combined with the respect of the causality relationship between operations, this commutation ensures the convergence criteria.

To achieve commutativity on a linear structure, the authors propose a solution based on a total order between elements in the document. More precisely, there is two kinds of modification :

• insert(pid, text) that inserts the line content text at the position identifier pid.

• delete(pid) that removes the line at the position identifier pid. In the original paper, a tree structure is introduced to maintain the total order between positions identifier. However, safely removing elements from this tree requires tombstones. In [START_REF] Roh | How to design optimistic operations for peer-to-peer replication[END_REF], authors refer also to the CRDT framework but use vector clocks to obtain this order.

Our idea is to use a position identifier based on a list of integers for each line. With such an identifier, a line can be removed from the document model without affecting the order of the remaining lines.

Logoot model

A Logoot document is composed by lines defined by: pid, content where content is a text line and pid a unique position identifier. There is two virtual lines called l B and l E to represent the beginning and the ending of the document.

The main idea to insert a line is to generate a new position A such as P ≺ A ≺ N where P is the position of the previous line and N the position of the next line. To allow operations to commute, position identifiers must be unique. Also, since a user can always insert a line, we must be able to generate a position A such as P ≺ A ≺ N for any P and N .

In the following definition we assume that each site maintains a persistent logical clock clock s incremented each time a line is created.

Definition 1.

• An identifier is a couple pos, site where pos is an integer and site a site identifier.

• A position is a list of identifiers.

• A position identifier generated by a replica s is a couple pos, h s where pos = i 1 .i 2 . . . . .i n . p, s is a position and h s is the value of clock s .

Thus, every position identifier is unique since the last identifier of the list i 1 .i 2 . . . . .i n . p, s which contains the unique site identifier and the value of the logical clock of this site.

To obtain a total order between positions, we use the following definition.

Definition 2.

• Let p = p 1 .p 2 . . . p n and q = q 1 .q 2 . . . q m be two positions, we get p ≺ q if and only if ∃j ≤ m. (∀i < j. p i = q i ) ∧ (j = n + 1 ∨ p j < id q j )

• Let id 1 = pos 1 , site 1 and id 2 = pos 2 , site 2 be two identifiers, we get p 1 < id p 2 if and only if pos 1 < pos 2 or if pos 1 = pos 2 and site 1 < site 2 .

We only compare positions -and not logical clockssince there can not be, in the same model, two lines with the same position (see lemma 3).

Finally, the logical view of a Logoot document looks like:

1 0, 0 , N A, lB 2
1, 1 , 0, "This is an example of a Logoot document"

Modifying a Logoot document

On collaborative editing systems such as wiki or VCS, an edit on a document is not a single operation but a set of operations (a patch). Lines inserted by a patch are often contiguous. Thus, to apportion the line positions, we define the generateLinePosition(p, q, N, s) function which generate N positions between a position p and a position q using numbers in base M AXIN T (the maximum of the unsigned integer plus 1). To obtain short positions, it firstly select the smallest equal length prefixes of p and q spaced out at least N . Then it apportions randomly the constructed positions.

1 function generateLinePositions(p, q, N , s) The function prefix(p, i) returns a number in base M AXIN T which each digits is p i .pos the integers of the first i th identifiers of p (filled with 0 if |p| < i). The function constructPosition(r, p, q, s) constructs a position r 1 , s 1 . r 2 , s 2 ..... r n , s n where r i is the i th digit of r. We use the following rules to define each s i : 1) if i = n then s i = s, 2) else if r i = p i .pos then s i = p i .site, 3) else if r i = q i .pos then s i = q i .site 4) else s i = s

For instance, on a site s, insertion positions between p = 2, 4 and q = 10, 5 20, 3 are apportioned in the set

• { x, s |x ∈]2, 10[} if N < 8 • { 2, 4 x, s |x ∈ [0, M AXIN T [}∨ { y, s x, s |x ∈ [0, M AXIN T [, y ∈]2, 10[}∨ { 10, 5 x, s |x ∈ [0, 20[} if N ≥ 8
To choose the value of the value of the integer in the position, any arbitrary choice can be made. However, to restrain two different replicas to generate concurrently the same choice, and thus to reduce the grow rate of the position list, we apply a random function.

To delete a line, we simply generate a delete operation which contains the position identifier of this line. Then, we can completely remove this line from the document.

Integrating remote modifications

Both line insertion and removal can be integrated in a logarithmic time according to the number of lines in the document and constant according to the number of the user in the P2P network. Indeed, we simply use the binary search algorithm to find the position in the document corresponding to the position identifier.

Also, the integration of a delete operation can safely remove the line from the document model, since the total order between remaining lines is not affected. Moreover, this removal will free a position identifier that can be reused. This mechanism reduces the growing rate of position identifier as shown in section 5.

Correctness of the approach

To ensure convergence in the CRDT framework, concurrent operations must commute. If line positions are unique, non mutable, and totally ordered, the different replicas can apply any series of insert operations in any order and obtain the same result.

The following lemma states that there cannot be two different lines with the same position on one model.

Lemma 1. If causality is preserved, the position of a line is unique on each model.

Proof: The last element of the line position contains the unique identifier of the site which generates the line. As a result, two different replicas cannot generate the same position.

A replica can only generates a position different from every other position in its model.

A replica can generate an insert operation o i of line l 2 with the same position than a line l 1 it has previously generated. However, this is possible only if l 1 was previously deleted on that replica by a (remote or local) delete operation o d . Then, we have the following happens before relationship o d → o i . Thus, if causality is preserved l 2 can only be inserted on a replica where l 1 was deleted.

The following theorem states that Logoot ensures consistency criteria. Its correctness is based on the CRDT correctness proof of [START_REF] Shapiro | Designing a commutative replicated data type[END_REF].

Theorem 2. If causality is preserved, Logoot ensures consistency.

Proof: Since the couple composed of a site identifier and a clock value is unique, each position identifier is unique.

According to Lemma 3, each position is unique, and thus position identifier are totally ordered.

Finally, since Logoot position identifiers are unique, non mutable and totally ordered, every couple (insert/insert, insert/delete and delete/delete) of concurrent operations commutes. Thus, Logoot data type is a CRDT.

The following theorem states that Logoot respects the intentions of the insert and delete operations as defined Section 2.

Theorem 3. If causality is preserved, Logoot ensures intentions.

Proof: Since position identifiers are unique and non mutable, delete operation intention is respected.

According to Lemma 3, each position is unique. Thus, the Logoot is always able to compute a new position between two lines. Since positions are non-mutable and totally ordered, the line order observed on the generation replica will be preserved on each other replica.

P2P constraints

In order to be deploy on a P2P network, our approach needs to satisfy some constraints. It must scales in terms of peers and support the churn of the network (i.e. peers which enter and leave the network arbitrarily fast).

Logoot position identifiers support these constraints since their size and space complexity are constant according to peers number (no vector clock). We only assume that each site has a unique identifier. Additionally to position identifiers, Logoot only require a causal dissemination mechanism. To obtain it, a scalable broadcast such as the lightweight probabilistic broadcast [START_REF] Eugster | Lightweight probabilistic broadcast[END_REF] in association with causal barriers [START_REF] Prakash | An adaptive causal ordering algorithm suited to mobile computing environments[END_REF] can be used.

Also, the Logoot framework supports network churn since it does not require any group membership mechanism or consensus algorithm. It also does not require to know the number of peers.

The following section discuss about Logoot scalability in terms of number of edits.

Evaluation

The size of Logoot position identifiers is unbounded. Theoretically, position identifiers can grow each time a line is inserted. Thus, if no line is ever removed, the size of the document model overhead can be n i = O(n 2 ) where n is the total number of inserted lines. However, due to the randomized nature of the algorithm, such a worst case can only arrive with a probability equal to 1/M AXIN T n which is negligible. In practice, lines are often removed and position identifier are apportioned, thus the overhead size remains low.

In order to effectively measure the Logoot overhead, we have replayed the modifications made on some Wikipedia pages in a Logoot document. For instance, in the proportionally worst result of our test bed (case 2, Figure 4), their is a total of 43352 identifiers, to be compared with the number of inserted lines n = 623863.

On another hand, in tombstones-based approaches, the size of the document model is also unbounded. The Wooto and Treedoc approaches have a constant overhead for each inserted line, thus strictly proportional to n. Comparing to the number of tombstones, the size of each position identifier remains low. Our approach is sightly less efficient only in a specific case (see Section 5.2.3).

Methodology

In our implementation, we use 8-bytes integers for site identifiers and positions, and 4-bytes integers for the logical clock, hence, a position identifier contains at least 20 bytes.

For the Wooto approach, we use an 8-bytes integer for the site identifiers and 4-bytes integers for the logical clock and the degree. Then, the overhead for each line is 16 bytes.

About the TreeDoc approach, we do not consider the tree overhead, we only count one 8-bytes integer for the site identifier and one 4-bytes integer for the counter. Finally, the overhead for each line is 12 bytes.

To replay the histories of some Wikipedia pages, we use the MediaWiki API 3 to obtain an XML file containing several revisions of a specific Wikipedia page. Then, using a diff algorithm [START_REF] Myers | An o(nd) difference algorithm and its variations[END_REF], we compute the modifications performed between two revisions. Modifications are simply re-executed in our model. Since our approach generates each position randomly, we re-executed ten times each page history to obtain average values.

We also measure the overhead for Wooto and TreeDoc. The result obtained for TreeDoc does not take account of the "stabledel" and "gc" procedures which aim to remove tombstones. We motivate this choice by the fact that these procedures require to know the exact number of replicas which is unknown, unbounded and unstable in P2P networks.

The overhead of Wooto and TreeDoc are directly computed from the number and the type of operations performed 3. http://www.mediawiki.org/wiki/API:Query -Properties#revisions . 2F rv on the document. Indeed, their overhead are directly proportional to the number of inserted lines in the document since deleted lines remain as tombstones.

We have applied this schema on the top pages of three categories 4 :

• The most edited encyclopedic pages,

• The most edited pages,

• The biggest pages. For each of the treated pages, we present the average -over the last 100 edits -overhead of the Logoot, Wooto and Treedoc approaches. We present the average size of the page and the number of patches (i.e. edits on the page).

Results

Figure 1 shows the relative (size of the overhead divided by the size of the visible document on a logarithmic scale) overhead of the three different approaches on the most edited encyclopedic page of the English Wikipedia. Figure 2 shows the absolute overhead. The Logoot overhead remains constant all along the editing session, while the overhead of tombstones-based approaches continuously grows.

Finally, the Logoot overhead is inferior to the document size while tombstones-based approaches require more than 100 times the document size and continuously grows. While the "George W. Bush" page contains only about 553 lines, the number of deletions is about 1.6 million. As a consequence, tombstones-based systems are not well-suited for such documents since we obtain 1.6 million tombstones for only 553 lines.

Most of the modifications done on Wikipedia pages consists in updating the content of some existing lines. To ensure user's intentions, distributed editing systems handle such an update as deleting the old content and inserting the new content. Thus, the number of tombstones grows quickly.

Also, the figure 1 shows several peaks which are mainly due to vandalism acts. Indeed in some of the most edited encyclopedic pages of Wikipedia, there is a lot of vandalism acts done by users, including erasing the whole content of the page. Every vandalism is reverted by re-introducing the previously erased content or removing malicious content introduced. This process adds each time a lot of tombstones (up to the page size). Introducing a specific undo mechanism that reuses tombstones such as [START_REF] Weiss | An undo framework for p2p collaborative editing[END_REF] should reduce the overhead due to tombstones. The Figure 3 presents the results obtained on the most edited encyclopedic pages. The histories of such pages show a lot of edits as well as vandalism acts. A huge number of deletions has been performed on such pages, hence, tombstones-based approaches show an important overhead. On the contrary, the Logoot overhead remains low.

Most edited

Pages. These pages (Figure 4) are discussion pages or special pages mostly edited by bots. In such pages, there is no or very few vandalism acts but a lot of edits.

For all these pages, the Logoot approach is more efficient than tombstones-based approaches. However, we can notice that the difference is far more important for pages were data are very volatile for instance like case 1 (a communication channel to detect and block vandals) or like case 4 (a sandbox). The other cases represent discussion pages. Users ask questions, and other users reply by modifying the page. Each topic is removed after one week. They are edited in the same way : mostly adding content at the end of the page and removing week old topics content at the beginning. Thus, there is, in these pages, a lot of tombstones but the Logoot position identifiers grow as well.

5.2.3. Biggest Pages. These pages (Figure 5) are often lists of elements. If these lists are always edited in the same way (for instance adding elements at the end of the page), they represent the worst cases for our approach. Indeed, the Logoot position identifier will grow the quickest, especially if insertions are done in many different occasions. Effectively, in cases 4, 9, and 10, our approach is less efficient than tombstones-based approaches.

However, these results show that our approach is in average, even in these disadvantageous real cases, less costly than tombstones-based approaches.

Limits of the experimentation

Since Wikipedia uses a centralized wiki, we can expect a slightly different behavior in a P2P system. For instance, Wikipedia reduces the impact of concurrent modifications. In a P2P environment, preventing users to make concurrent modifications is not a realistic hypothesis. Therefore, concurrent modifications are automatically merged. This will certainly produce an "inconsistent" document which requires the intervention of some user to correct it. Therefore, the number of edits will certainly be more important in a P2P wiki than in a centralized wiki.

In Wikipedia, some pages are protected to reduce the number of vandalism acts. However, such protection mechanism is not compatible with P2P constraints. Therefore, in a P2P wiki, the number of vandalism acts is certainly more important. Therefore, we expect to obtain more edits and vandalism acts on a P2P wiki system.

Contrary to the Woot approach, CRDT approaches, including ours, requires a causal broadcast to achieve convergence. However, a causal delivery implies an overhead on each message sent by each replica. The two main mechanism to achieve a causal delivery are vector clocks [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF] and causal barriers [START_REF] Prakash | An adaptive causal ordering algorithm suited to mobile computing environments[END_REF]. Vector clocks are not usable in P2P networks since their sizes are proportional to the number of replica. Causal barriers have a smaller size, that depend only on the degree of concurrency of the operations in the network. On collaborative editing system, this degree remains low : less than 3 edits per second on the whole English Wikipedia in average 5 . However, a realistic measure of the communication overhead can only be achieved with a corpus of concurrent collaborative editions.

Conclusion

In this paper, we have presented the Logoot algorithm. Logoot is an optimistic replication algorithm that ensures CCI consistency on linear structures. Logoot can be used on structured or unstructured P2P networks. It does not require tombstones. Therefore, the space overhead remains linear during the life of the document and no garbage collector is required.

We validated the logoot algorithm on a corpus extracted from Wikipedia. The experimentation demonstrates that the Logoot unbounded list of identifiers associated to each line In the future, we plan to evaluate Logoot overhead in time and to extend it to manage more structured data such as XML documents. We are also working on a group undo feature.

1 pid0, lB 2 pid1,

 12 "This is an example of a Logoot document" 3 pid2, "Here, pid1 ≺ pid2 " 4 pid3, "And pid2 ≺ pid3 " 5 pid∞, lE

3 1, 1 . 1 , 5 , 4 1, 3 , 2 , 5 M

 31154325 [START_REF] Myers | An o(nd) difference algorithm and its variations[END_REF], "How to find a place between 1 and 1" "This line was the third made on replica 3" AXIN T, 0 , N A, lE

2 3 6 7

 26 list := {}; 4 index := 0; 5 interval := 0; while (interval < N ) 8 index++; 9 interval := prefix(q, index)prefix(p, index); 10 endwhile 11 step := interval / N ; 12 r := prefix (p, index); 13 for j:=1 to N do 14 list.add(constructPosition(r + Random (1, step),p,q,s)); 15 r := r + step; 16 done 17 return list;

5. 2 . 1 .

 21 Most edited encyclopedic Pages. The Figures3, 4and 5 show the average relative overhead (i.e. the size of the overhead divided by the size of the visible document) 4. According to http://en.Wikipedia.org/wiki/Wikipedia:Most frequently edited pages and http://en.Wikipedia.org/wiki/Special: LongPages on end of November 2008. However, due to some technical issues (i.e. invalid characters, missing patch, ...), we skipped some of the top pages, but the first page of each category is presented.

Figure 1 .

 1 Figure 1. Relative overhead for "George W. Bush" page.

Figure 2 .

 2 Figure 2. Absolute overhead for "George W. Bush" page.

Figure 5 .

 5 Figure 5. Biggest pages

http://en.Wikipedia.org/wiki/Wikipedia:Most frequently edited articles


Stéphane Weiss
email: weiss@loria.fr

Pascal Urso
email: urso@loria.fr

Pascal Molli
email: molli@loria.fr

An Undo Framework for P2P Collaborative Editing

Keywords: Group undo, P2P Collaborative Editing, Operational Transformation

Existing Peer to Peer (P2P) collaborative editing systems do not allow any user to undo any modification. However, in such systems, users are not aware of others' modifications, hence, they could obtain duplicate work, conflicting modifications or malicious contents. In this paper, we propose a new undo framework called "UNO: Undo as a New Operation" in the Operational Transformation approach which does not limit the scalability of P2P algorithms. As a proof of concept, we apply our framework to build a P2P collaborative editor with undo capabilities in which any user can undo any modification.

Introduction

Collaborative editing systems allow people distributed in time and space to work together on shared documents. The major benefits of collaborative writing include reducing task completion time, reducing errors, getting different viewpoints and skills, and obtaining an accurate document [START_REF] Tammaro | Collaborative Writing Is Hard to Support: A Field Study of Collaborative Writing[END_REF][START_REF] Noël | Empirical study on collaborative writing: What do co-authors do, use, and like?[END_REF].

Nowadays, collaborative editing systems are becoming Peer to Peer (P2P): Version Control Systems (VCS) turn into Distributed Version Control Systems (DVCS), Wiki systems become P2P Wiki system [START_REF] Morris | Distriwiki: : a distributed peer-to-peer wiki network[END_REF][START_REF] Kang | Repliwiki: A next generation architecture for wikipedia[END_REF][START_REF] Weiss | Wooki: a p2p wiki-based collaborative writing tool[END_REF] and even softphones change into P2P softphones such as skype. P2P architecture provides massive collaboration, resistance to failure and censorship. Such systems could also increase data availability and allow off-line work.

In a P2P environment, users are not immediately aware of others' concurrent modifications. Therefore, a site merging its document with another peer could obtain duplicate work, conflicting modifications or malicious contents. In such a context, an undo feature is mandatory. Every user must be able to revert any undesired change. Moreover, the modification to undo is not necessary the last received one, hence, users must be able to undo any operation in their history. Therefore, we need to provide the most general model of undo mechanism which allows any user to undo any edit operation at any time.

All existing undo approaches in the literature [START_REF] Berlage | A framework for shared applications with a replicated architecture[END_REF][START_REF] Prakash | A framework for undoing actions in collaborative systems[END_REF][START_REF] Choudhary | A general multi-user undo/redo model[END_REF][START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF][START_REF] Sun | Operation Context and Context-based Operational Transformation[END_REF] are specific to a collaborative editing system. Unfortunately, none of these systems is designed to support P2P architectures. Therefore, none of the existing approaches could provide an undo for P2P systems. On the other hand, some existing collaborative softwares such as Wiki or DVCS propose an undo mechanism. However , wiki systems may fail to undo any operation. Moreover, such systems are centralized, hence, they cannot be used in P2P environment. DVCS allow any user to undo any operation. Nevertheless, DVCS do not bring any warranties about data consistency.

The Operational Transformation (OT) [START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF][START_REF] Ellis | Concurrency control in groupware systems[END_REF] framework, purposes a consistency model (CCI) to preserve Causality, Converge and Intention. OT is recognized as a suitable approach to maintain consistency of shared documents. This approach is applied to develop both real-time and asynchronous collaborative editors [START_REF] Molli | Using the transformational approach to build a safe and generic data synchronizer[END_REF][START_REF] Cart | Asynchronous reconciliation based on operational transformation for p2p collaborative environments[END_REF]. It consists of two main components: a generic integration algorithm which manages concurrent operations and transformation functions specific to a data model. For instance, MOT2 [START_REF] Cart | Asynchronous reconciliation based on operational transformation for p2p collaborative environments[END_REF] is an integration algorithm designed for P2P architecture.

In this paper, we propose an undo in the OT framework that respects P2P algorithms' constraints. We call our approach UNO : Undo as a New Operation, because it aims to treat undo operation as any other operation newly generated by users. This approach, inspired from well established collaborative tools, allows building a generic schema which can be introduced in any OT approach without affecting its scalability.

As a proof of concept, we apply our framework on the TTF functions which are also the only published set of transformation functions which can be used with MOT2 (See appendix section A). Therefore, in this paper, we obtain a P2P collaborative text editor with undo features.

The structure of the paper is as follows. We first motivate the need of a novel undo approach for P2P systems in Section 2. We explain the main idea of the UNO in Section 3. Then, we briefly describe the OT approach in Section 4. We present our approach in Section 5 and apply it on the TTF functions in Section 6. Section 7 deals with the UNO framework correctness. Finally, we compare our approach with existing undo approaches in Section 9.

Motivation

P2P collaborative systems bring several exciting features:

-Massive editing: thousand of users can work on the same project and reduce drastically the task completion time, -Off-line work: users edit their own copy, hence, they can work online or off-line, -Privacy: users decide when they want to publish their modifications, -Mobilibity: such systems support ad-hoc collaboration.

However, merging data over a P2P network implies some inconvenient behaviors:

-Obviously, each user cannot know what other users are doing: we can have duplicate work or conflicting modifications, -Malicious peers could degrade existing work, merging with such peers will propagate this alteration to the whole network.

Such scenarios are not problematics as soon as users are capable of quickly reverting undesired changes. Therefore, in such systems, the undo feature is mandatory.

In OT, several approaches allow undoing any operation at any time such as GOTO-ANYUNDO [START_REF] Sun | Consistency maintenance in real-time collaborative graphics editing systems[END_REF], COT [START_REF] Sun | Operation Context and Context-based Operational Transformation[END_REF]. The GOTO-ANYUNDO approach uses state vectors (aka vector clocks [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF]) while the COT approach uses extended state vectors [START_REF] Sun | Operation Context and Context-based Operational Transformation[END_REF] called "context vectors". A state vector is a vector which contains a logical clock entry per host present in the network. As a consequence, state vector's size grows linearly with the number of site in the system. In P2P networks, the number of site is potentially unbounded and not even known by network participants. Therefore, state vectors are not compatible with P2P constraints such as scalability or churn.

Finally, we need to design an undo approach which does not limit the integration algorithm's scalability.

UNO idea

The main idea of our approach is to treat undo operations as any other operation generated by users. To illustrate this idea, assume that a text document is replicated (Figure 1). At the beginning, the document contains only "Rendezvous". Then a first user inserts the sentence "at nine." at line 2. Concurrently, a second user inserts "At 8 in the park:" at the beginning of the document. And finally, a user wants to undo the operation "ins(2, at nine. )".

Text document History

Rendezvous ins(2, at nine.)

G G ins(2, at nine.) G G undo(ins(2, at nine.)) =del(3, at nine.) (b) UNO Idea Existing OT undo approaches roughly consist in forming do-undo-pair by coupling the undo operation with the undone operation (Figure 1(a)). Unfortunately, integration algorithms are designed to generate and integrate operations only on the current state. Thus, specific mechanisms, such as "context vectors" [START_REF] Sun | Operation Context and Context-based Operational Transformation[END_REF], are designed to support such insertion. As a result, these undo mechanisms are tightly coupled to a specific integration algorithm that may not scale.

To obtain a generic undo mechanism, we propose to use the same schema as massively used in collaborative tools such as VCS or Wiki. For instance, in SVN ( [START_REF] Collins-Sussman | Version Control with Subversion[END_REF] page 91), undoing a previous revision consists in applying a modification and then committing it normally. In the UNO, we produce a new operation that has the wished effect on the current state, then we integrate it as any other user's operation. Therefore, the undo operation will be placed in the history according the user's real schedule (Figure 1(b)).

Thus, we obtain an undo mechanism that can be introduced in any OT collaborative editing system without modifying the way operations are integrated. Consequently, the scalability of the targeted OT system is not limited by the undo mechanism.

In the Figure 1, when we want to undo the operation "insert(2, at nine. )", we want to remove the third line "at nine.". Our idea is simply to generate a new operation which removes the third line instead of undoing the insertion (see Figure 1(b)). This new operation is generated on the current state, hence, all integration algorithms can handle it.

In the following sections, we give the details required to implement this idea.

The Operational Transformation (OT) approach

In the OT approach, shared documents are replicated. Each site contains its own copy of the document, and a user is supposed to work at one site. OT approach allows any user to modify at any time his own copy of the document. Therefore, different copies of the same document can be modified in parallel. In the OT model, a modification is represented as an operation. Each site sends all the locally generated operations to the other sites. On these other sites, such operations are seen as remote operations which have to be integrated for execution.

To allow convergence, these algorithms use a transformation function T to modify remote operations according to local ones. For instance, we consider two sites sharing the same text document (Figure 2). We call T (op 1 , op 2 ) the remote operation op 1 transformed against the local operation op 2 . Of course the definition of the function T is specific to the targeted data type. However, defining a transformation function is not sufficient to ensure correctness, the transformation function must also respect some formal properties (see Section 7).

Proposition: Undo as a New Operation

The main advantage of our undo scheme is that undo operations are treated as regular ones, i.e. do-operations, when integrated on local and remote sites. Thus, undo operations do not require any special treatment on remote sites.

Site1 "Cat" Site2 "Cat" ins(2, 'o ′ ) B B U U U U U U U U U U U U U U U U U U U U U U U U U U U ins(4, 's ′ ) t t i i i i i i i i i i i i i i i i i i i i i i i i i i i "Coat" "Cats" T (ins(4, 's ′ ), ins(2, 'o ′ )) = ins(5, 's ′ ) T (ins(2, 'o ′ ), ins(4, 's ′ )) = ins(2, 'o ′ ) "Coats" "Coats" Fig. 2. Transformations
Given a set of operations, an instance of the UNO framework is built in three steps. First, we define the (possibly new) operations that counterbalance original ones. Second, we define the transformation functions for these new operations, if any. Third, we formally verify the properties required by the targeted integration algorithm.

Then, a simple algorithm is used to provide the undo feature.

Algorithm We call undo(op) the undo operation of op, i.e. the operation which counterbalances the effect of op, if op is the last executed operation. undo(op) can be either a newly defined operation or an operation from the initial set. However, since op may not be the last executed operation, we need to compute an operation undo(op) ′ which is defined on the current state. undo(op) ′ is the transformation of undo(op) according to all operations which have been executed on the local site since the execution of op. To compute undo(op) ′ , we use the following algorithm (also illustrated in Figure 3): UNO(HB, i): op:= undo(HB.get(i )) j := i+1 while( j <= HB.size) do op:= T(op, HB.get(j )) j := j+1 endwhile return op Therefore, undo(op) ′ is defined on the current state of the document. Thus, undo(op) ′ is considered as a normal operation directly done by a user when it will be integrated and transformed on remote sites.

Since undo operations are treated as normal operations, these transformation functions are standard transformation functions, and thus must be proven correct according to CCI criteria, see Section 7 about correctness of the approach.

Complexity of the UNO framework The UNO algorithm's time complexity is linear with the number of operation received. The space complexity is constant, indeed, the algorithm does not require any data structure except one operation. Since the UNO framework complexity does not depend on the number of site, it can be applied to P2P architecture.

Instantiation

Now, we want to apply our undo framework to provide the undo feature in a P2P collaborative text editor built with MOT2 and TTF.

The Tombstones Transformation Functions

The TTF approach is divided in two parts: the model and the transformation functions. A detailed explanation of the TTF approach and its correctness can be found in [START_REF] Oster | Tombstone transformation functions for ensuring consistency in collaborative editing systems[END_REF].

The main idea of the model is to keep deleted characters as tombstones. The document's view only shows visible characters: tombstones are hidden. Consequently, the model differs from the view. Figure 4 illustrates this. Assume that a document is in a state "abcd". Now, a user deletes the character 'b'. In the TTF model, the character is replaced by a tombstone (i.e. the character with a visibility flag set to false). The view differs from the model as the view only contains "acd" while the model contains "ab /cd". Since tombstones are necessary to achieve consistency, they cannot be removed and thus, the operation "Ins" is not inversible.

Undo operation

The first step in applying the UNO framework is to define the undo operations and their effects. Undoing an operation must return the system to a state on which the undone operation was never performed. In our context, this definition implies that a character deleted concurrently by N sites should not be visible unless each of these N delete operations are undone. To achieve such a behavior, we simply propose to replace the visibility flag of each character by a visibility level. This visibility level is an integer. Initially, an inserted character has a visibility level of 1. Each time we undo an insertion operation, the visibility level of the corresponding character is decreased. Each time we undo a deletion, we increase the visibility level of this character.

A character is said "visible" and appears in the document's view if its visibility level is at least 1. Similarly, a character is said "invisible" and does not appear in the document's view if its visibility level is less than 1. Since characters are just marked as invisible, we introduce a new operation "Undel(p,sid)" which effect is to increase the visibility level of the character at position "p". The use of visibility levels is illustrated in Figure 5. The second step is to write transformation functions for all operations. The definition of the transformation functions for the operations "Ins" and "Del" are the same as in original TTF approach.

T( Ins (p1, c1, sid1),Undel(p2, sid2)):

return Ins (p1, c1, sid1) end T( Del(p1, sid1), Undel(p2, sid2)):

return Del(p1, sid1) end T( Undel(p1, sid1), Ins(p2, c2, sid2)):

if (p1 < p2) return Undel(p1, sid1) else return Undel(p1 + 1, sid1) end T( Undel(p1, sid1), Undel(p2, sid2)):

return Undel(p1, sid1) end T( Undel(p1, sid1), Del(p2, sid2)):

return Undel(p1, sid1) end Moreover, since these transformation functions are bijective, they can easily be reversed. Consequently, we can apply this approach with integration algorithms as SOCT2, GOTO which require reversible transformation functions.

Correctness

An OT system is considered as correct if it respects the CCI [START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF] criteria: Causality: This criterion ensures that all operations ordered by a precedence relation, in the sense of the Lamport's happened-before relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF], will be executed in the same order on every copy. Convergence: The system converges if all copies are identical when the system is idle. Intention: The expected effect of an operation should be observed on all copies. It must be ensured by the transformation functions and by the integration algorithm.

In [START_REF] Cart | Asynchronous reconciliation based on operational transformation for p2p collaborative environments[END_REF], the authors show how MOT2 ensures Causality. Convergence is achieved if the transformation functions satisfy two properties [START_REF] Ressel | An integrating, transformationoriented approach to concurrency control and undo in group editors[END_REF]: * T P 1: The transformation property T P 1 defines a state equality. The state obtained by the execution of an operation op 1 on a state S followed by the execution of the operation T (op 2 , op 1 ) should be equal to the state obtained by the execution of op 2 on a state S followed by the execution of T (op 1 , op 2 ) :

T P 1 : S • op 1 • T (op 2 , op 1 ) = S • op 2 • T (op 1 , op 2 )
* T P 2: The property T P 2 ensures that the transformation of an operation against a sequence of operations does not depend on the transformation order of operations in this sequence.

T P 2 :

T (op 3 , op 1 • T (op 2 , op 1 )) = T (op 3 , op 2 • T (op 1 , op 2 ))
Based on some problematic scenarios called "undo puzzles", prior works expressed the need of additional properties to obtain a correct undo. Two properties IP 2 and IP 3 are proposed [START_REF] Prakash | A framework for undoing actions in collaborative systems[END_REF][START_REF] Sun | Undo as concurrent inverse in group editors[END_REF] to solve these scenarios. However, none shows that these properties are necessary and sufficient to ensure a correct undo. For instance, the property IP 2 is not respected by our transformation functions while the corresponding problematic scenario does not appear (Figure 6).

Site1 Site2

"ab ′′ "ab ′′ generate the same operation. Site1 generates undo(op) and transforms it against following operations T (seq, op). Site2 undoes the last received operation which is T (op, seq). These two undo operations are defined on the same state, they undo the same operation, so the resulting operation must be the same. The verification of this property ensures that whenever an operation is undone, the undo effect remains the same.

Site1 Site2

undo(op) B B op o o D D X X X X X X X X X X X X X X X X X X X X Seq r r ff ff ff ff ff ff ff ff ff ff Seq ′ = T (Seq, op) op ′ = T (op, Seq) G G undo(op ′ ) s s undo(op) ′ = T (undo(op), Seq ′ ) undo(op ′ ) = undo(T (op, Seq))
Fig. 7. Respect of the undo effect So, there are properties to verify in order to ensure a correct OT system with undo. Due to their conciseness, these properties are theoretically easy to prove. However, one of the particularity of the OT approach is the huge numbers of cases to check.

In such conditions, a hand proof is error-prone. Indeed, many hand-proven transformation functions were finally revealed false (all counter examples can be found in [START_REF] Oster | Tombstone transformation functions for ensuring consistency in collaborative editing systems[END_REF]).

On another hand, each of the cases to check can be easily handled by an automated formal theorem prover. Consequently, we choose to use the proof environment VOTE [START_REF] Imine | Vote: Group editors analyzing tool: System description[END_REF] based on the theorem prover Spike [START_REF] Nieuwenhuis | Rewriting Techniques and Applications, 14th International Conference, RTA 2003[END_REF][START_REF] Stratulat | A general framework to build contextual cover set induction provers[END_REF] which generates all the cases and ensures the verification of all properties.

Using the proof environment VOTE [START_REF] Imine | Vote: Group editors analyzing tool: System description[END_REF], we have proven that our transformation functions verify the properties T P 1, T P 2 and IP 3. The system specification given to the theorem prover Spike1 can be reviewed and tested at the following url: http: //graveyard.sf.net/.

Integrating the UNO with existing integration algorithms

In the OT framework, integration algorithms (SOCT2, SOCT4, GOTO, COT, MOT2) are defined for operations (with no assumption about the number or the kind of operations) and need transformation functions to deal with these operations.

The UNO framework extends a set of operations and transformation functions to support a recovery mechanism. We obtain a new set of operations and transformation functions. Consequently, the resulting set can be handled by any existing integration algorithm.

Our framework also requires the UNO algorithm. To undo an operation op, we generate an undo operation undo(op). The UNO algorithm transforms undo(op) against all operations which have been executed after op. For this stage, undo(op) is considered as concurrent to all operations after op. Fortunately, the main goal of every integration algorithm is to transform an operation against a set of concurrent operations.

Consequently, any OT integration algorithm can determine the undo operation. The resulting operation is treated as a normal operation. Thus, the UNO algorithm can be easily integrated in any integration algorithm. Of course, this requires to remove the undo dedicated treatment from these algorithm (such as the "mirror" and "fold" functions of adOPTed or "ensure-IPXSafety" of COT).

As a proof of concept, we build the Graveyard prototype 2 . Graveyard is an opensource collaborative text editor that allow any user to undo any operation. It relies either on the MOT2 algorithm or on the SOCT2 algorithm for integrating concurrent operations and it uses the TTF transformation functions with related undo operations. However, we can replace MOT2 by SOCT4, adOPTed or GOTO and obtain the same result.

Related Work

The first selective undo was proposed in [START_REF] Prakash | A framework for undoing actions in collaborative systems[END_REF]. To undo an operation, the authors propose to swap it with following operations in the history. Then, the resulting operation's inverse is applied. However, swapping two operations in the history is not always possible, hence, the authors also add the notion of conflict. If a conflict occurs, the undo is aborted. Therefore, this framework does not allow undoing any operation.

In [START_REF] Ressel | Reducing the problems of group undo[END_REF], the authors introduce an undo specific to the adOPTed algorithm by adding two functions called "mirror" and "fold". This solution allows undoing operations in the inverse chronological order, i.e. from the last operation to the first one without skipping one. This approach does not allow undoing any operation. Since the adOPTed algorithm requires transformation functions satisfying T P 1 and T P 2, we can use the TTF functions in association with our undo approach to provide an undo for any operation.

The GOTO-ANYUNDO approach [START_REF] Sun | Undo as concurrent inverse in group editors[END_REF] is associated with the GOTO integration algorithm. This approach introduces a new undo algorithm called ANYUNDO-X. This undo approach is the first to solve known undo problematic scenarios while allowing any user to undo any operation at any time. GOTO-ANYUNDO treats specifically undo operations: undone and undo operations are grouped to create do-undo pairs. While integrating an undo operation, the history buffer is modified in order to remove the undone operation effect from the history. The GOTO-ANYUNDO approach is designed for real-time editing. In such a context, state vectors are adequate, however they are not compatible with P2P environment.

In [START_REF] Ferrié | Concurrent undo operations in collaborative environments using operational transformation[END_REF], the authors define two properties C3 and C4 which are similar to IP 2 and IP 3. To ensure the verification of these two properties, the authors introduce a specific operation "undo(op)". This approach defines generic transformation functions for this operation "undo(op)" using the proposed transformation functions. The main idea to enforce C4 is to swap the operations and undo the resulting operation. Unfortunately, the authors do not discuss the case of causally dependent operations. This leads to incorrect results.

The COT approach [START_REF] Sun | Operation Context and Context-based Operational Transformation[END_REF] is an OT system designed for real-time editing which introduces the notion of "context vector". A context vector is associated to each operation and represents the operations executed before its generation. Unlike state vectors, context vectors captures undo operations causality and concurrency. As state vectors, the cost of context vector is compatible with real-time editing, however, they are not suitable in a P2P environment.

Distributed version control systems (DVCS) as Git3 are P2P collaborative systems mainly used for source code editing. They propose an undo comparable to the UNO approach: they compute a new patch to remove the effect of a previous one and treat it as a new patch. However, DVCS lack of a formal framework, indeed, there is no property to validate DVCS' correctness. On the contrary, the UNO approach is based on the CCI framework.

Repliwiki, Distriwiki and Wooki are P2P wiki systems. Unfortunately, they do not provide an undo mechanism.

Discussion Algorithms similar to the UNO algorithm already appear in the literature. For instance, [START_REF] Ferrié | Concurrent undo operations in collaborative environments using operational transformation[END_REF] calls it the naive undo algorithm. However, it was never supported as a correct undo algorithm. The reason is its apparent inability to solve known undopuzzles.

In this paper, we have shown that it provides a correct undo -even if the IP 2 condition is relaxed -and if the operation set and the transformation functions are able to respect the CCI criteria including the undo intentions.

For instance, the operation "Ins" does not realize exactly the undo intention of the operation "Del", in Figure 8, this leads to swap the characters 'a' and 'b'. The intention of "Ins" is "insert a new element". On the other hand the operation "Undel" realizes the intention "makes a deleted element reappear". Thus, if a framework wants to use the operation "Ins" to undo the operation "Del", it is forced to introduce complex integration mechanisms to avoid undo-puzzle to occurs. On the contrary, using an operation expressing the undo intention solves this puzzle as show in Figure 6. We thus strongly claim, that operations and transformation functions which ensure undo intention preservation allow building more generic, more efficient and correct undo mechanism.

Conclusions

In all existing OT approaches, undo is designed for real-time editing. In this paper, we introduced our undo framework which provides undo feature for all integration algorithms even P2P ones.

In this paper, we propose: u u j j j j j j j j j j j j j j j j j j j -a generic undo framework: This framework can be applied to all set of transformation functions to provide an undo mechanism on several date type. An important feature of our approach is that the resulting transformation functions remain generic towards integration algorithms. Consequently, we can apply these functions with COT, SOCT2, SOCT4, MOT2, GOTO and adOPTed. -a CCI compliant framework: The CCI criteria is a formal framework for collaborative editing correctness. The UNO framework uses the CCI to ensure its correctness. -a scalable framework: The UNO approach time and space complexity is constant with the number of site. Therefore, it is particularly adequate for P2P environment. The UNO algorithm is efficient since it is only linear in time with the number of operation received. We also show that a simple and efficient algorithm considered incorrect can be instantiated to provide a correct undo. -an implementation: We have a complete solution to build correct P2P text editors with a flexible undo capability. The TTF transformation functions with the undo proposed in this paper are implemented in the Graveyard4 collaborative text editor.

Graveyard is a prototype which can be used with MOT2 for P2P or SOCT2.

The CCI framework includes the Intention definition which is not formally defined in the general case. In the UNO, the undo behavior depends on the Intention criterion. Therefore, as future work, we will try to formally defined the Intention. We plan also to implement a DVCS and a wiki system using the UNO approach.

Fig. 1 .

 1 Fig. 1. UNO idea.

Fig. 3 .

 3 Fig. 3. Naive undo Algorithm

Fig. 4 .

 4 Fig. 4. Model in the TTF approach.

1 "a /0b1c ′′ 1 Fig. 5 .

 115 Fig. 5. Visibility level

  undo(op): IF op = Ins(p, c, sid) THEN undo(op) := Del(p, sid) IF op = Del(p, sid) THEN undo(op) := U ndel(p, sid) IF op = U ndel(p, sid) THEN undo(op) := Del(p, sid)

  Del(0, b)) = Ins(0, b)

Fig. 8 .

 8 Fig. 8. IP2 undo puzzle

Fig. 9 .

 9 Fig. 9. Divergence scenario

  "ac′′ "abXc ′′ "aY bc ′′ "ac ′′ "abXc ′′ "aY bc ′′ o o G G"aY c ′′ "abXc ′′ "aY bc ′′ "ac ′′ "abXc ′′ "aY c ′′ ′′ "abXc ′′ "aY bXc ′′ "ac ′′ "aY bXc ′′ "aY bc ′′ ′′ "aXY c ′′ "aY Xc ′′ "aY Xc ′′ "aY bXc ′′ "aY bc ′′

	Site1	Site2	Site3	Site4	Site5	Site6
	"abc"	"abc"	"abc"	"abc"	"abc"	"abc"
	Del(1, b) Ins(2, X) Ins(1, Y )
	"ac ′′	"abXc ′′ "aY bc ′′	"abc ′′	"abc ′′	"abc ′′
	o o			G G
		o o			G G
			o o			G G
			o o		G G
	o o	G G	o o	G G

"aY c "aXY c

http://lita.sciences.univ-metz.fr/ ˜stratula

http://graveyard.sf.net

http://git.or.cz/

http://graveyard.sf.net

t t h h h h h h h h h h h h h h h h h h h h h h h h h

"ab ′′ "ab ′′ Fig. 6. IP2 undo puzzle

The condition IP 3 is formally defined as:

To illustrate this condition, Figure 7, two sites make concurrent operations. Site1 generates op while site 2 generates a sequence of operations seq. Both sites receive remote operations, transform and integrate them. Now, they are on the same state. Consequently, if they want to undo the same operation on the same state, they must obviously

A MOT2 and TTF

In [START_REF] Cart | Asynchronous reconciliation based on operational transformation for p2p collaborative environments[END_REF], the authors claim that MOT2 only require the T P 1 property. Therefore, we could use the following transformation functions since they satisfy T P 1.

T( Ins (p1, c1) , Ins (p2, c2) ): if p1 < p2 or ( p1 = p2 and c1 < c2 ) Ins (p1, c1) else Ins (p1 + 1, c1) T( Ins (p1, c1 ), Del(p2, c2) ):

Unfortunately, Figure 9 illustrates a divergence scenario which can occur. This problem is an instance of the T P 2 puzzle [START_REF] Oster | Tombstone transformation functions for ensuring consistency in collaborative editing systems[END_REF].

Finally, MOT2 requires transformation functions which satisfy the properties T P 1 and T P 2. Therefore, the TTF transformation functions are particularly adequate for


Pierdomenico Paolino

Bruno Tiribilli

Ludovic Bellon
email: ludovic.bellon@ens-lyon.fr

Direct measurement of spatial modes of a micro-cantilever from thermal noise

Measurements of the deflection induced by thermal noise have been performed on a rectangular atomic force microscope cantilever in air. The detection method, based on polarization interferometry, can achieve a resolution of 10 -14 m/ √ Hz in the frequency range 1 kHz-800 kHz. The focused beam from the interferometer probes the cantilever at different positions along its length and the spatial modes' shapes are determined up to the fourth resonance, without external excitation. Results are in good agreement with theoretically expected behavior. From this analysis accurate determination of the elastic constant of the cantilever is also achieved.

Introduction

Atomic force microscopy (AFM) is currently used in a great variety of studies involving small forces measurement [START_REF] Butt | Force measurements with the atomic force microscope: Technique, interpretation and applications[END_REF] including unfolding of protein [START_REF] Fisher | The micromechanics of single molecules studied with atomic force microscopy[END_REF][START_REF] Vazquez | Mechanical and chemical unfolding of a single protein: A comparison[END_REF], probing the structure of biological membranes [START_REF] Frederix | Atomic force microscopy of biological membranes[END_REF] and monitoring the mechanical response of living cells [START_REF] Radmacher | Studying the mechanics of cellular processes by atomic force microscopy[END_REF][START_REF] Sbrana | Role for stress fiber contraction in surface tension development and stretchactivated channel regulation in C2C12 myoblasts[END_REF] as well as Micro-Electro-Mechanical Systems (MEMS) and other nanotechnological devices [START_REF] Bhushan | Nanotribology, nanomechanics and nanomaterials characterization[END_REF][START_REF] Lavrik | Cantilever transducers as a platform for chemical and biological sensors[END_REF].

All those applications exploit the great accuracy in measuring the cantilever deflection offered by AFM and converting this measurement in units of force assuming the cantilever behaves like a spring with known stiffness. Manufacturers often specify the spring constant of their cantilevers in a wide range of values, mainly because of the great uncertainties in the dimensions, particularly the thickness, resulting from the fabrication process. To overcome this problem several techniques have been proposed to calibrate cantilever spring constant [START_REF] Butt | Force measurements with the atomic force microscope: Technique, interpretation and applications[END_REF][START_REF] Cook | Practical implementation of dynamic methods for measuring atomic force microscope cantilever spring constants[END_REF][START_REF] Levy | Measuring the spring constant of atomic force microscope cantilevers: thermal fluctuations and other methods[END_REF][START_REF] Hutter | Calibration of atomic-force microscope tips[END_REF][START_REF] Sader | Calibration of rectangular atomic force microscope cantilevers[END_REF]. The reader is referred to the work of Burnham and co-workers [START_REF] Burnham | Comparison of calibration methods for atomic-force microscopy cantilevers[END_REF] and the references therein for a comparative summary of the different techniques.

One of the first and still most commonly used is the so called thermal calibration method [START_REF] Hutter | Calibration of atomic-force microscope tips[END_REF] based on the measurement of the vibration amplitude of the free end of a cantilever exited by thermal noise. The first peak of the thermal noise spectrum is related back to the spring constant of the cantilever modeled as an harmonic oscillator. In a more accurate model, Butt and Jaschke [START_REF] Butt | Calculation of thermal noise in atomic force microscopy[END_REF] introduced a correction factor deduced from the Euler-Bernoulli description of the flexural dynamic of a free-clamped beam.

In this work we measure thermal noise spectrums of the cantilever deflection along its length, and compare the rms amplitudes of the first four modes of vibration as a function of spatial position with the eigenmodes of the Euler-Bernoulli model. Furthermore, we present an extention of the thermal noise calibration method for the spring constant based on the multi-mode measurement.

Theoretical background

L W T z d(x,t) y x
Figure 1: The thermal fluctuations of deflection d(x, t) of a rectangular cantilever (BS-Cont-GB-G) are measured with a differential interferometer : the optical path difference between the reference beam, reflecting on the chip holding the cantilever, and the sensing beam, focused on the cantilever, directly gives a spatially resolved and calibrated measurement of deflection d [START_REF] Bellon | Procédé de mesure de la déflexion d'un levier de microscope à force atomique[END_REF]. The whole cantilever can be probed by displacing the beams along its length (x axis). Length L, thickness T and width W of the cantilever are indicated on the figure.

Let us first recall the main lines of Butt and Jaschke's work [START_REF] Butt | Calculation of thermal noise in atomic force microscopy[END_REF] to interpret our measurements. The cantilever is sketched on Fig. 1. Its length L is supposed to be much larger than its width W , which itself is much larger than its thickness T . We will limit ourself in this study to the flexural modes of the cantilever: the deformations are supposed to be only perpendicular to its length (along axis z of Fig. 1) and uniform across its width. These deformations can thus be described by the deflection d(x, t), x being the spacial coordinate along the beam, and t the time. The generic solution of the Euler-Bernoulli equation can be expressed as follows:

d(x, t) = ∞ n=1 d n (t)φ n x L (1)
in which the spatial solutions are in the form

φ n x L = cos α n x L -cosh α n x L - cos(α n ) + cosh(α n ) sin(α n ) + sinh(α n ) sin α n x L -sinh α n x L (2)
where the α n satisfy the relation

1 + cos(α n ) cosh(α n ) = 0 (3)
which leads to α 1 = 1.875, α 2 = 4.694, . . . , α n ≈ (n -1/2)π. The amplitude d n (t) of each modes are governed by harmonic oscillator equations, with spring constants k n , mass m and resonance frequencies f n :

k n = α 4 n 3 k c = α 4 n 3 EW T 3 4L 3 (4)
m = m c = ρLW T (5)
f n = 1 2π k n m (6)
where k c and m c are the static stiffness and mass of the cantilever, and E and ρ are the Young's modulus and density of its material. We furthermore consider, under the hypothesis of thermal equilibrium, that the thermal noise driven deflection follows the equipartition theorem and each resonance mode can be considered as an independent harmonic oscillator [START_REF] Butt | Calculation of thermal noise in atomic force microscopy[END_REF] with mean quadratic fluctuations d 2 n :

1 2 k B T = 1 2 k n d 2 n (7)
where represents time average.

Experimental methodology and results

In our experiment, we measure both the amplitude of the thermal noise distibution among the modes d 2 n and their spatial shape φ n (x/L). We use gold coated BudgetSensors Atomic Force Microscopy (AFM) cantilevers (Cont-GB-G). They present a nominal rectangular geometry: L = 450 µm long, W = 50 µm wide and T = 2 µm thick, with a 70 nm gold layer on both sides. We observe the fluctuation of the cantilever deflection induced by thermal noise. The measurement is performed with a home made interferometric deflection sensor [START_REF] Bellon | Procédé de mesure de la déflexion d'un levier de microscope à force atomique[END_REF][START_REF] Paolino | Quadrature phase interferometer for afm measurement[END_REF], inspired by the original design of Schonenberger [START_REF] Schonenberger | A differential interferometer for force microscopy[END_REF] with a quadrature phase detection technique [START_REF] Bellon | Differential interferometry with a complex contrast[END_REF]: the interference between the reference laser beam reflecting on the chip of the cantilever [START_REF] Bellon | Procédé de mesure de la déflexion d'un levier de microscope à force atomique[END_REF] and the sensing beam on the cantilever gives a direct measurement of the deflection d(x, t), with very high accuracy (see Fig. 1).

A first advantage of this technique is that it offers a calibrated measurement of deflection, without conversion factor from angle to displacement, as in the standard optical lever technique common in AFM. A second advantage of our detection system is a very low intrinsic noise, as illustrated in Fig. 2 with the power spectrum density of a rigid mirror (bottom black line): the light intensities on the photo diodes are tuned exactly as during the measurement on the cantilever, but since the mirror is still, the measured spectrum reflects only the detection noise. This background noise is as low as 3 × 10 -28 m 2 /Hz in the frequency range from 1 kHz to 800 kHz, just 10 % higher than the shot noise limit of our detection system. A third advantage is that the precision of the measurement is independent of the focused beam size on the cantilever, which was tuned as small as 10 µm to ensure good spatial resolution along the cantilever length.

When translating the focusing lens with respect to the cantilever, both reference and sensing laser beams are shifted along the chip and cantilever respectively [START_REF] Bellon | Procédé de mesure de la déflexion d'un levier de microscope à force atomique[END_REF]. The chip's first structural mode is at very high frequency compared to that of the cantilever, hence it is considered as a rigid fixed mirror independently of the actual reference beam position on top of it. The measured interference signal is therefore only due to the thermal noise driven deflection of the cantilever. Fig. 2 illustrates such a spectrum when the sensing beam is close to the free end. The signal to noise ratio is good enough to identify the first four flexural resonances (as well as the first two torsional resonances, which are visible due to imperfect centering of the spot laterally). The relative frequencies of the peaks should obey the following relation that directly derives from equations 4 and 6:

f n f 1 = α 2 n α 2 1 (8)
The experimental ratios of resonance frequencies are in good agreement with the expected values (see table 1).

Mode A precision screw allows adjusting the horizontal position of the focusing lens and locating the sensing beam at different positions along the cantilever length while the reference beam is always on the chip [START_REF] Bellon | Procédé de mesure de la déflexion d'un levier de microscope à force atomique[END_REF]. For each measurement, the x position of the laser spot on the cantilever can be estimated from the image acquired by a simple CCD camera. The spot center in the images can be detected with ±1.4 µm accuracy on the cantilever. Measurements were repeated with approximative 15 µm steps. At every position we measure the deflection d(x, t) produced by thermal excitation of the cantilever and evaluate the Power Spectrum Density (PSD) S d (x, f ). The complete set of results is reported in Fig. 3 as a 3D representation. The first four oscillation modes can be clearly seen with their respective number of nodes. Two further peaks can be noted, the first at about 220 kHz and a second, of smaller amplitude, at 790 kHz, that we attribute to the first and second torsional modes.

f n /kHz f n /f 1 α 2 n /α 2 1 Q n Q
For a quantitative characterization of the shape of the modes we determine the rms amplitude of each resonance δ 2 n (x) as a function of the position x, by integrating the PSD in a convenient frequency interval 2∆f around each peak: This quantity is computed directly from the experimental spectrums, without any fitting process of the resonances. We anyway take care to subtract contribution of the background noise of the interferometer and to compensate for the finite integration range in frequency. Experimental data computed this way is plotted on Fig. 4. Error bars correspond to the equivalent noise of the detection system in the bandwidth chosen around each resonance (a very conservative estimation of uncertainty).

δ 2 n (x) = fn+∆f fn-∆f S d (x, f )df (9)
According to equation 1, we should have

δ 2 n (x) = d 2 n φ n x L 2 (10)
Using the expression of d 2 n (eq. 7), it is therefore possible to fit the data with 3 adjustable parameters: the length of the lever L ′ , the clamping position x 0 and the static spring constant of the cantilever k ′ c . We realize the fit on the rms amplitude simultaneously on the 4 modes with the following functions:

δ 2 n (x) = 3 α 4 n k B T k ′ c φ n x -x 0 L ′ (11)
where n = 1, ..., 4. The red curves in Fig. 4 represent the fits of the four considered modes, in good agreement for all modes. The best fit values are: L ′ = (450 ± 5)µm and k ′ c = (0.376 ± 0.015)N/m. These length and stiffness are compatible with the values provided by the manufacturer (L = (450 ± 10)µm and k c from 0.07 N/m to 0.4 N/m).

It is worth noting that the accuracy of our instrument provides a precise measurement of the thermal noise driven deflection along the cantilever length and allows to verify the Euler-Bernoulli model for the microlever. Furthermore this multi-mode approach provides a more reliable way to estimate the spring constant of a cantilever with respect to the standard thermal noise calibration method, which is limited to the integral of the first mode only and just at the cantilever free end (circled point in Fig. 4). Actually a precise measurement of stiffness could be obtained from the first 3 modes only, the presence of the nodes providing a favorable constraint to the fitting process. Moreover, the use of the interferometric set-up allows one to avoid the calibration of the segmented photodiode response as in the classical optical lever readout scheme: this step implies a contact between the AFM tip and a hard sample which is translated of a known amount, a process that may be undesirable to preserve the probe's sharpness or its coating. Our calibration method leaves only a small 4 % uncertainty on the spring constant value for the cantilever used here (confidence interval corresponding to one standard deviation estimated during the linear least square fitting process).

Experimental PSD curves show that resonances have a mode number dependent frequency width. This effect is mainly due to the viscous drag of the fluid, an point that is not considered in the Euler-Bernoulli framework. A simple model that accounts for this aspect, for each eigenmode, is a damped harmonic oscillator characterized by three parameters: the resonance frequency f n , the elastic constant k n and the quality factor Q n . The PSD of the damped oscillator can be expressed as:

S d (f ) = 2k B T k n πf n Q n (1 -u 2 ) 2 Q 2 n + u 2 (12)
with u = f /f n the normalised frequency. For each mode the PSD depends on the spatial coordinate along the cantilever length still according to |φ n (x)| 2 . The Q n are evaluated from experimental data by a fit in the region around the peaks of each node (see Fig. 5). Those values are constant along the cantilever. Since the elastic constant k n and resonant frequency f n of each mode is known, the quality factor Q n is the only free parameter in these fits. In table 1 the Q n values of the first four modes are compared with the hydrodynamic predictions of the Sader model [START_REF] Sader | Frequency response of cantilever beams immersed in viscous fluids with applications to the atomic force microscope[END_REF] that account for viscous effect in the fluid. These predictions were computed with tabulated values of silicon and gold for Young's modulus and density, and the physical dimensions of the cantilever (length, width and thickness) were tuned within the manufacturer tolerance to match the experimental observations. Note that the elastic modulus of gold and silicon are of the same order of magnitude, whereas the density of gold is about eight times that of silicon, therefore even a thin coating layer of 70 nm produces a mass increment of about 60% that cannot be neglected in the evaluation of total mass. A good agreement between the model and experiment is observed for the first three resonances, but at the highest frequency a deviation is observed: a lower dissipation than that foreseen by the Sader model. This behavior was already observed by Maali et al [START_REF] Maali | Hydrodynamics of oscillating atomic force microscopy cantilevers in viscous fluids[END_REF]. This deviation is expected since the original Sader model neglects the 3D nature of the fluid flowing around the cantilever, an effect increasing with mode number [START_REF] Sader | Frequency response of cantilever beams immersed in viscous fluids with applications to the atomic force microscope[END_REF]. In an extended model by Sader and co-workers [START_REF] Van Eysden | Frequency response of cantilever beams immersed in viscous fluids with applications to the atomic force microscope: Arbitrary mode order[END_REF], such a correction is also observed in the same direction as in our observation.

Conclusions

We presented in this paper a high precision measurement of thermal noise induced deflection of a soft rectangular micro-cantilever as a function of frequency and position along the mechanical beam. The 4 first flexural spatial modes could be studied without any external forcing. Their shapes are very well fitted by the Euler-Bernoulli model, and their vibration amplitudes accurately described within the Butt and Jaschke [START_REF] Butt | Calculation of thermal noise in atomic force microscopy[END_REF] framework. Furthermore this multi-mode approach provides an extension to the standard thermal noise calibration method for the spring constant of the cantilever, with a more robust estimation: it is obtained by a simultaneous fit on several modes, when the classic measurement is limited to the integral of the first mode only and just at the cantilever free end. Here, the stiffness of our cantilever could be determined with only 4 % uncertainty. Quality factors of resonances are also robustly extracted from the measurements and compare well to the Sader estimation [START_REF] Sader | Frequency response of cantilever beams immersed in viscous fluids with applications to the atomic force microscope[END_REF].

The very simple geometry considered here, a rectangular AFM probe, is commonly used in many other applications. In fact single-clamped structures, similar to cantilevers, are often the basic elements of complex MEMS devices. Many physical, chemical and biological sensors, a large family of micro-devices, are based on cantilever shaped structures. They respond to an external change with a small, barely detectable, mechanical movement. The proposed calibration method would be directly applicable to these objects. The characterization of more complex structures (bi-dimensional for instance) such as arrays, double clamped elements, membranes and other micro-mechanical structures could also be performed, although it would also require a proper theoretical treatment to extract the relevant physical parameters from the measurement. The absence of external forcing (that may not be controlled or hard to characterize) thanks to the use of thermal noise and the great resolution of the interferometric setup make our approach a very promising tool for the mechanical characterization of MEMS. Even beyond such calibration, our setup proves to be a valuable tool to perform measurements of extremely small mechanical displacements with a high bandwidth. We subtract from the raw measurement (dashed blue) the background noise (black) to estimate the mechanical noise of the cantilever (blue), then we perform a fit with a simple damped harmonic oscillator model (dashed red). For each plot, the horizontal scale spans ±10f n /Q n around f n .

Figure 2 :

 2 Figure 2: Power Spectrum Density (PSD) S d (x ≈ L, f ) of thermal noise induced deflection (red curve) measured close to the free end of the cantilever as a function of frequency f (log scale on both axis). The first 4 flexural modes and first 2 torsional modes are clearly above the background noise (bottom black line), measured with a rigid mirror. With our interferometric setup, resolution better than 1.7 × 10 -14 m/ √ Hz can be achieved on the whole frequency range explored here (1 kHz -800 kHz).

Figure 3 :

 3 Figure 3: Power Spectrum Density (PSD) S d (x, f ) of thermal noise induced deflection as a function of frequency f and position x along the cantilever. The first 4 normal modes are clearly visible, with a vanishing amplitude toward the clamped extremity of the mechanical beam and the nodes of each mode. Another vibration peak with no nodes is also visible close to the third mode, it is attributed to the first mode in torsion, but is not studied in this paper.

Figure 4 :

 4 Figure4: Amplitude of thermal noise for the first 4 flexural modes along the cantilever. Errors bars correspond to the equivalent noise of the detection system in the bandwidth chosen around each resonance (a very conservative estimation of uncertainty). The simultaneous fit (red curves) of the 4 resonances with the normal modes shapes is excellent and leads to a precise measurement of the stiffness of the cantilever. The common calibration method for the spring constant considers only the value of δ 2 1 (L), the circled point in the upper graph.

Figure 5 :

 5 Figure5: Power Spectrum Density (PSD) S d (x ≈ L, f ) of thermal noise induced deflection measured close to the free end of the cantilever as a function of frequency f around each resonance f n . We subtract from the raw measurement (dashed blue) the background noise (black) to estimate the mechanical noise of the cantilever (blue), then we perform a fit with a simple damped harmonic oscillator model (dashed red). For each plot, the horizontal scale spans ±10f n /Q n around f n .

Table 1 :

 1 Measured and expected parameters for first 4 flexural modes.

	Sader
	n

Acknowledgements The authors thank F. Vittoz and F. Ropars for technical support, and S. Ciliberto, A. Petrosyan and J.P. Aimé for stimulating discussions. One of us (B.T.) thanks École Normale Supérieure de Lyon for invited professor position. This work has been partially supported by contract ANR-05-BLAN-0105-01 of the Agence Nationale de la Recherche in France.