Re: load time regression: Re: commit: Change Record UUID's

Hi Martin, Matthew (and everyone else),

msevior@physics.unimelb.edu.au wrote:
>>Counter will not work in whatever shape and form: think of two users
>>running two instances of AW on two different computers editing the same
>>document via the collab features, and hence generating change records.
>>It must be possible to order the change records in absolute (i.e., not
>>relative) manner to create a single change record queue, and that
>>requires that the change record id carries a reasonably accurate
>>timestamp.
>
> I'm not so sure about that. I think that after synchronization we actually
> do want counters running on each users document. The counters will inform
> other members of the abicollab network if there has been a clash of edits
> due to network latency.
>
> ie if Alice and Bob are both editting the same document then there was no
> latency issues something like this would happen:
>
> Alice Bob
> counter Counter
> 1 1 (initially)
> 2 1 (Alice edits)
> 2 > 2 (Alice's edit is tranmitted to Bob and is applied)
> 3 2 (Alice edits again)
> 3 > 3 (Transmitted to Bob)
> 3 4 (Bob edits)
> 4 < 4 (Transmitted to Alice)
> 4 5 (Bob Edits again)
> 5 < 5 (Transmitted to Alice)
> 6 5 (Alice edits)
> 6 > 6 (Transmitted to Bob)
>
> OK Now suppose we have a latency issue....
>
> 7 7 (Alice and Bob both edit before seeing the other)
> 7? <> 7? (When the packets arrive they see counters equal
> or greater than themselves. So they know they need
> to do some sort of conflict resolution.)
>
> I talk about how to solve this sort of problem in the GOCollab document.

There is also the alternative where the simultaneous operation 7 by A
and B gets lost in transmission:

7 >|< 7
8 > 8

At this stage A and B have different documents, but are not aware of it;
there is no way that simple counter can catch this, nor can a timestamp
-- you need a much more sophisticated algorithm, which deals not only
with the latency, but in general with divergence, causality violations
and intention violations as is described in the Sun98 paper
(http://citeseer.ist.psu.edu/sun98operational.html).

The Lamport paper that Matthew linked
(http://research.microsoft.com/users/lamport/pubs/time-clocks.pdf)leads
to similar conclusion that I reached trying to trash out the 'AbiTalk'
protocol: if you only use logical clocks (aka counters), you need some
kind of a token passing. As soon as you start thinking about this in
real life (packets arriving out of order and getting lost, etc.), this
becomes quite complicated, because the token is subject to the same
problems as the sending of a single change record (latency, loss); the
AbiTalk document might not be of any practical use, but the complexity
of this should be clear from it (http://www.abisource.com/~tf/AbiTalk.zabw).

The whole matter is a non-trivial problem. My overall feeling about this
is that we should not try to reinvent the wheel, which is the reason I
stopped working on the AbiTalk proposal once Matthew pointed us to the
Sun98 paper. The paper gives us an algorithm that deals with the three
basic issues of divergence, causality violation and intention violation,
and I think we should use it, or some other algorithm that handles these
problems.

At the end of the day, whether we use logical or real timestamps, we
still will have to keep the clocks synchronised, so we endup with
absolute time. If we use real time stamps, we should be able to delegate
the synchronisation to a suitable underlying carrier protocol; if we use
logical clocks, we will have to do that ourselves, and devise an
handshake for this.

As for the change record ids, I simply used the existing uuid class for
this because it was convenient and because we needed it without messing
too much with the code; the offending code should definitely be #if 0
from the 2.4.1 branch.

Tomas

                
___________________________________________________________
To help you stay safe and secure online, we've developed the all new Yahoo! Security Centre. http://uk.security.yahoo.com
Received on Mon Oct 24 19:15:45 2005