In this page is presented the operational transformations used in file system conciliation.Four operations are defined :
- AddFile(p,t) : add a file having path p. Example : operation AddFile('/a/b', t) will add a file b in directory /a/
- AddDir(p,t) : add a directory having path p. There is no operational transformation definition for this method because they can be obtained with AddFile algorithms.
- Move(p,np,t) : move object with path p to the new path np. The deletion of a file or a directory is assimilate to a move operation to a "special" directory like a trash. For example, if a user delete the /a/file, the corresponding operation will be Move('/a/file', '/trash/a/file', t).
- UpdateFile(p,c,t) : This operation is useful to describe the effect of a file update according to others operations : AddFile(p,t), AddDir(p,t) and Move(n,np,t). The c value is a meta-data of the object. This value can be the property of a directory or the content of a file. There is no differences between these two update operations. More information is necessary only is there are two concurrent UpdateFile(p,c,t) operations.
Two concurrent add operations
There is only one conflict possible : two users add the same file in the same directory. In this case, we use the second parameter (site id) to choose the file that will be added with another name. This choice allow the conservation of the two files. The function uniquePath() calculate the new unique name of the second file (for example, concatenation of old name and site id).T(AddFile(p 1,t 1), AddFile(p 2,t 2)) = if (p 1 = p 2) then if (t 1 < t 2) then return AddFile(uniquePath(p 1),t 1) else return [ Move(p 1,uniquePath(p 1),t 1) ; AddFile(p 1,t 1) ] endif else return AddFile(p 1,t 1) endif;
- b.1 (file added by first operation)
- and b (file added by second operation)
Add and Move concurrent operations
There are two particular cases :- A file is added and is move to an other path : the file is added with a new unique path (function uniquePath())
- A file is added in a directory that is moved by second operation : it is necessary to change the path of the add operation.
- childOf(p1, p2) : return true if the path p1 is the child of the path p2.
- tail(p1, p2) : extract the end of the path p1 according to its father path p2 (tail('/a/b/c/d', '/a/b') return the path c/d).
- concat(p1, p2) : return the concatenation of the two paths p1 and p2 (concat('/a/b','c/d') return /a/b/c/dc/d).
T(AddFile(p 1,t 1), Move(p 2,np 2,t 2)) = if (p 1 = np 2) then if (t 1 < t 2) then return AddFile(uniquePath(p 1),t 1) else return [ Move(p 1,uniquePath(p 1),t 1) ; AddFile(p 1,t 1) ] endif else if (childOf(p 1,p 2)) then return AddFile(concat(np 2,tail(p 1,p 2)),t 1) else return AddFile(p 1,t 1) endif; T(Move(p 1,np 1,t 1), AddFile(p 2,t 2)) = if (np 1 = p 2) then if (t 1 < t 2) then return Move(p 1,uniquePath(np 1),t 1) else return [ Move(np 1,uniquePath(np 1),t 1) ; Move(p 1,np 1,t 1) ] endif else return Move(p 1,np 1,t 1) endif;
Move and Move concurrent operations
- move of two file to the same location : Move('/a','/c') and Move('/b','/c').
- move of a file to a path that has been moved by the other operation : Move('/a', '/b/c') and Move('/b', '/d').
- move of the same file to two differents locations : Move('/a/b', '/c') and Move('/a/b','/d')
T(Move(p 1,np 1,t 1), Move(p 2,np 2,t 2)) = if (np 1=np 2) then if (p 1=p 2) then return Id() else if (childOf(p 1,p 2)) then return Move(concat(np 1,tail(p 1,p 2)), uniquePath(np 1), t 1) else if (childOf(p 2,p 1)) then return [ Move(np 1,uniquePath(np 1),t 1) ; Move(p 1,np 1,t 1) ] else if (t 1<t 2) then return Move(p 1,uniquePath(np 1),t 1) else return [ Move(np 1,uniquePath(np 1),t 1) ; Move(p 1,np 1,t 1) ] endif else if (p 1=p 2) then if (t 1<t 2) then return Id() else return Move(np 2,np 1,t 1) endif else if (childOf(np 1,p 2)) then if (childOf(np 2,p 1)) then if (t 1<t 2) then return Id() else return [ Move(np 2,p 2,t 1) ; Move(p 1,np 1,t 1) ] endif else if (childOf(p 1,p 2)) then return Move(concat(np 2,tail(p 1,p 2)),concat(np 2,tail(np 1,p 2)),t 1) else if (childOf(p 2,p 1)) then return Move(concat(np 2,tail(p 1,p 2)),concat(np 2,tail(np 1,p 2)),t 1) else return Move(p 1,concat(np 2,tail(np 1,p 2)),t 1) endif else if (childOf(np 2,p 1)) then if (childOf(p 2,p 1)) then return Move(p 1,np 1,t 1) else if (childOf(p 1,p 2)) then return Move(p 1,np 1,t 1) else return Move(p 1,np 1,t 1) endif else if (childOf(p 1,p 2)) then return Move(concat(np 2,tail(p 1,p 2)),np 1,t 1) else if (childOf(p 2,p 1)) then return Move(p 1,np 1,t 1) else return Move(p 1,np 1,t 1) endif;
Add and Move + Update content concurrent operations
No problem with this operational transformation.T(AddFile(p 1,t 1), UpdateFile(p 2,c 2,t 2)) = return AddFile(p 1,t 1); T(UpdateFile(p 1,c 1,t 1), AddFile(p 2,t 2)) = return UpdateFile(p 1,c 1,t 1); T(Move(p 1,np 1,t 1), UpdateFile(p 2,c 2,t 2)) = return Move(p 1,np 1,t 1); T(UpdateFile(p 1,c 1,t 1), Move(p 2,np 2,t 2)) = if (childOf(p 1,p 2)) then return UpdateFile(concat(np 2,tail(p 1,p 2)),c 1,t 1) else return UpdateFile(p 1,c 1,t 1) endif;
Two concurrent Update content operations
As we have explained before, the transformation functions already defined don't care about the type of update made in the content of the file. If it's the update of a text bloc or the entire file replacement, we only update the path of the file.- If update is on a text file, we can reuse the text functions.The results will be merged in the file.
- If two concurrent updates occur on a binary file, it is not correct to merge the results in the file. We duplicate the file and apply each update on each copy.
T(UpdateFile(p 1,c 1,t 1), UpdateFile(p 2,c 2,t 2)) = if (p 1 = p 2) then if (c 1 = c 2) then return Id() else if (t 1 < t 2) then return [ AddFile(uniquePath(p 1),t 1) ; UpdateFile(uniquePath(p 1),c 1,t 1) ] else return [ Move(p 1,uniquePath(p 1),t 1) ; AddFile(p 1,t 1) ; UpdateFile(p 1,c 1,t 1) ] endif else return UpdateFile(p 1,c 1,t 1) endif;