incubator-wave-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Joseph Gentle <jose...@gmail.com>
Subject Re: Future of Apache wave [Was: Re: Advantages of P2P messaging?]
Date Wed, 12 Jun 2013 18:19:38 GMT
Yep. Similar but better, because using OT we can guarantee eventual
consistency  we don't need conflict markers and there's a bunch of
edge cases darcs can't handle.

Likewise, the current OT algorithm we use is remarkably similar to
subversion/cvs. (We currently use a server-side version number that
increments with every change, etc). But again, with a transform
function mixed in to make it better.

Basically, my proposal to make a P2P OT system moves from SVN's
architecture to GIT's architecture.

-J

On Wed, Jun 12, 2013 at 10:59 AM, Bruno Gonzalez (aka stenyak)
<stenyak@gmail.com> wrote:
> This sounds *awfully* similar to darcs patch theory. If the concepts are
> the same, then all the theory is already worked out if i'm not mistaken.
> http://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory#Merging_is_symmetric
> http://darcs.net/Theory
>
>
> On Wed, Jun 12, 2013 at 7:39 PM, Joseph Gentle <josephg@gmail.com> wrote:
>
>> Did you meet Torben at the wave summit? He took me through his way to
>> mitigate this problem. He describes it briefly here:
>> https://github.com/josephg/lightwave/blob/master/ot/README
>>
>> In short, give every operation a unique hash. Each peer stores its own
>> (transformed) history list.
>>
>> When two peers sync with each other, they need to figure out which
>> operations they are each missing (still not sure what the best way to
>> do this is). They send missing operations to one another, with some
>> context.
>>
>> Locally, imagine I've applied:
>> X A' B' C
>> and I want to sync with a peer which has ops:
>> A B D
>> ... Obviously, I need to apply D locally. But I don't have an X' that
>> I can transform D by! We can solve this by rewriting our history.
>>
>> So Torben came up with the idea of a prune function (inverse
>> transform). Then we can define:
>>
>> swap = (a, b) ->
>>   b' = prune(b, a)
>>   a' = transform(a, b')
>>
>> I can use that to take my local history:
>> X A' B' C
>> and swap X past A B to get:
>> A B X' C
>> Then I can transform D by X' C to get D', that I can apply locally.
>>
>> I don't need to re-save the new operation history if I don't want to -
>> A B X' C D' is just as valid as X A B C D'. I think there's some
>> clever decisions we can make there to decrease the number of
>> transforms that the network will need to perform.
>>
>> I made a proof-of-implementation last week, and it works & converges.
>> (It was really exciting, even though Torben beat me to the punch a
>> couple of years ago):
>> https://github.com/josephg/tp2stuff/blob/master/node.coffee
>>
>> -J
>>
>>
>> On Wed, Jun 12, 2013 at 9:38 AM, Michael MacFadden
>> <michael.macfadden@gmail.com> wrote:
>> > Other ways to mitigate this are interesting areas of research.
>> >
>> >
>> > ~Michael
>>
>
>
>
> --
> Saludos,
>      Bruno González
>
> _______________________________________________
> Jabber: stenyak AT gmail.com
> http://www.stenyak.com

Mime
View raw message