Re: Abt project

On Thu, Mar 13, 2003 at 01:42:48AM -0000, Atul Vidwansa wrote:
> Dear Peter,
>        I beg your pardon for not contacting earlier, but now my all
>        lecture are finished and I can concentrate fully on the
>        project. According to the university time table, now onwards
>        I can devote all my time to the project. I have been
>        preparing to present a project proposal by the end of next
>        week to the university. After reading the Intersync paper and
>        going through the code once I am able to understand basic
>        working. Also I read some more journals regarding similar
>        implementations in Ficus FS, Conflict resolutions in mobile
>        clients and multi agent co-operation in DFS (references given
>        below).
>       I want to ask you some basic question, like

> 1) what are your expectations from fully featured Intersync?

That it automatically resolves conflicts where conflicting files are
moved "aside" according to one of the two policies stated in the
paper (they are almost identical policies, the difference being who is
the "winner"). 

> 2) what exactly do you mean by making the algorithm more robust?

Proven correct, working efficiently on large conflict sets (like two
clients untarring 100,000 files & 10,000 directories right on top of
each other.

> 3) Are we looking towards some particular performance gain, if yes what are  our limits?

There should be no scalability limits that are not normally present.
I.e. you cannot assume that all your conflict objects fit in memory at
the same time. 

>     Until now I was looking for what other people did in the same
>     area, but I don't know if I am going on a right track. Can you
>     please suggest me any further reading or coarse of action. 

I think the papers below tell you what kind of conflicts can be
present.  That is useful to know.  The first paper omitted one which
was found in the second.

We have taken a completely operation based approach and we ignore
conflicts in file data (as in 5), we simply select the "winning file".
The operations are discussed in (2) and more in the Kumar's server
replication Coda thesis, but I think the discussion in the intersync
paper is more useful.  Don't spend too much time on these papers.

For us a file system is a set of operations changing file trees and
these operations are encoded in the KML records.

The first steps would be to define elementary operations on the KML
records, such as "are in conflict or not (i.e. commute)", and
commutator functions:

  if ab = ba' a' then is derived from a,b as follows a' = a'(a,b)

With these the proposed algorithm can probably be sketched out in some
detail and then implemented.

Another thing that would be good to do is to formalize the algorithm
and the correctness further.  I have never seen a mathematical
definition of a file system. The state of a file system is clearly a
map from a tree into a space of inodes with some constraints.  Then
the basic operations on the trees can be defined as mathematical
relations between the two trees, before and after the operation.  So a
file system evolves as a family of maps of trees into graphs, where
the family is consists of the state of the file system after each
operation (this is like a fibration in mathematics, but not
quite). With such definitions in hand, some correctness proof that is
mathematical, as opposed to "almost certainly good" as I did it in the
intersync paper.  Elementary concepts such as the "support of the map"
(what is the map changing) will be good things to use to reason with. 

> The journals I read about similar implementations are:
> 1) Resolving File Conflicts in the Ficus File System    [ www.isi.edu/~johnh/PAPERS/Reiher94a.pdf ]
> 2) Disconnected Operation in Distributed File System [http://citeseer.nj.nec.com/kistler92disconnected.html ]
> 3) Supporting Conflict Resolution in Cooperative Design Systems [ http://ccs.mit.edu/klein/papers/smc-91.pdf ]
> 4) Multi-Level Conflict in Multi-Agent Systems [http://www.cs.umass.edu/Dienst/UI/2.0/Describe/ncstrl.umassa_cs%2FUM-CS-1999-017 ]
> 5) Supporting Application-Specific Resolution in an Optimistically Replicated File System [ http://www-2.cs.cmu.edu/afs/cs/project/coda/Web/docdir/wwos4.pdf]
> 
>      I look forward towards your suggestions.
> 
> regards,
> -Atul

- Peter -


-------------------------------------------------------
This SF.net email is sponsored by:Crypto Challenge is now open! 
Get cracking and register here for some mind boggling fun and 
the chance of winning an Apple iPod:
http://ads.sourceforge.net/cgi-bin/redirect.pl?thaw0031en