• Rym KHawam? : rym.khawam@gmail.com
• Muhammad Naneh : mnaneh@gmail.com
• Ikbal Mansour (Supervisor) : ikbal.mansour@gmail.com

Original topic: Attach:alep07.pdf Δ

Well, Muhammad has to work on Woot ⚠ {[mybib.bib,oster06cscw]} , and Rym on TTF ⚠ {[mybib.bib,oster06collcom]}, but the problem is common : how to flag and unflag conflicts occuring during merge in decentralized collaborative editing systems?

For bibliographic research, you can use :

• DBLP : http://www.informatik.uni-trier.de/~ley/db/
• ACM Digital library : http://portal.acm.org/dl.cfm
• Google Scholar : http://scholar.google.com/
• CiteSeer? : http://citeseer.csail.mit.edu/

Use these references to get interesting papers related to your topic. i.e. search with keywords, follow bibliographic references of selected papers, track papers that cite selected papers... Sometimes you cannot access papers, do not hesitate to ask us, we have agreement with ACM and we can download it for you.

A Master report must include:

1. The context
2. The problem
3. The state of art
4. A proposition
5. A prototype (can be optional)

TODO

1. Read papers referenced below...
2. Formalize the algorithm in proposition and apply to your context (WOOT or TTF). You have to detail new data needed for this algorithm, new operations required etc...
3. Implement (if you have time on prototypes). For accessing existing source code, you need a password and login.You can take mine : momo54, tagada

Questions

Ask your question here ! Me and Gérald will answer as soon as possible. You can reach us by phone or google talk (i am momo54@gmail.com, gérald is oster54@gmail.com)

The context : Decentralized Collaborative editing

You can read this paper for your culture on collaborative editing Attach:taxonomy.pdf Δ

1. Collaborative editing : Definition, why is it important ?
2. Decentralized Collaborative editing : Why ? Expected benefits ?
3. Existing systems in this field and current limitation...

The Problem : Conflict awareness

P2P? collaborative editing can lead to a state merged by the computer and not reread by anybody. It is not the case with a central server. For example with CVS, The last state is produced by a human, not the computer.

Rim should illustrate this with a TTF execution, Muhammad with a WOOT execution

State of art

1. Optimistic replication (⚠ {[biblio.bib,Saito05]}). This paper gives a good overview about optimistic replication (OR) and tries to classify most of the existing OR mecanisms from a distributed system point of view.
2. Operation Transformation ⚠ {[biblio.bib,Ressel96]},⚠ {[biblio.bib,Sun98]}. These two papers are major references about operational transformation (OT) approach. Some papers about other OT algorithms are available and are maybe easier to read ⚠ {[biblio.bib,Suleiman98]} ⚠ {[biblio.bib,Vidot00]}.
3. WOOT ⚠ {[mybib.bib,oster06cscw]}. This paper presents WOOT an optimistic replication algorithm that might be suitable for P2P? collaborative editing systems. This algorithm relies in some way on a serialisation mechanism and consequently is not based on OT approach.
4. Decentralized Version Control and conflict representation

http://www.zooko.com/revision_control_quick_ref.html

1. PB: DVCS does not converge (TP2? Puzzle),

See ECSCW03? for TP2? puzzle ⚠ {[mybib.bib,abdessamad03]}. Attach:TP2.png Δ

1. Conflicts are represented within files, Merging and Awareness are not separated

1. Awareness :
   1. Conflict objects ⚠ {[mybib.bib,OsterCIM02]},
   2. Divergence Metric ⚠ {[mybib.bib,molli02a]},
2. State treemap ⚠ {[mybib.bib,molli01b]}

Proposition

Concurrent operations leads to conflict in every case ! There is no need for overlapping concurrent operations. For example, suppose the initial text:

• l1 : 2+2
• l2 : =4

User 1 insert 1+1 before l1, Concurrently, user 2 delete l1.

The system will converge to:

• l0: 1+1
• l2: =4

There is no "syntactic conflict" such as overlapping, but the result is semantically inconsistent.

Our idea is to make the difference between reviewed state and merged state. When a user review a state, this state identified by its state vector (see ⚠ {[biblio.bib,Mattern89]}) is marked as reviewed. If two or more concurrent operations are merged on state, the new state is not reread, and concurrent operations can be "highlighted on this state".

Concurrent operation can be detected by comparing their state vectors. Last common ancestor state can be detected by taking the minimum of each entry of state vector.

Question : IMHO, this state can be a unread state, so we have to find maybe the first common ancestor reread state and then highlight all concurrent operation to this state.

We think that the final algorithm should be like the garbage collector algorithm detailed in TOCHI98? paper ⚠ {[biblio.bib,sun98tochi]}.

On the same example:suppose the initial state is already marked as read, so the state [0,0] is red. There is two concurrent operations

1. [1,0], ins('1+1',pos=0)
2. [0,1], del(1)

So state [1,0] and [0,1] are reviewed too.

After merge we will obtain on boh sites the state [1,1] with :

• l0: 1+1
• l2: =4

This state is not reviewed ! the min between [1,0] and [0,1] is [0,0] and this state is reviewed. So we must highlight operations [0,1] and [1,0]. If final state is considered ok by a user, he can mark this state as reviewed. So wee need a new operation review(statevector).

Prototyping

1. Woot for Muhammad... http://potiron.loria.fr/projects/woot
2. GraveYard? for Rym... http://potiron.loria.fr/projects/TTF