The original question was (paraphrased) "what happens when two client each
alter the text "15", one to "16" and the other to "17".
Or put another way, what happens when two or more clients concurrently
insert text at the same position.
I believe I have an answer to both the stated question and the implied
question "How should clients maintain consistent state when there are
unacknowledged edits?"
Given the wave transform function T(C, S) where C is the client operation
and S is the server operation:
T(A, B) = {A', B'}
T(A, B){C} = A'
T(A, B){S} = B'
If A is:
A.deleteCharacters("15")
A.characters("16")
and B is:
B.deleteCharacters("15")
B.characters("17")
Then T(A, B) = {A', B'} produces:
A'.characters("16")
A'.retain(2)
B'.retain(2)
B'.characters("17")
And T(B, A) = {B', A'} produces:
A'.retain(2)
A'.characters("16")
B'.characters("17")
B'.retain(2)
So, you'll notice that swapping A and B for server and client operations
produces different results.
This means that:
T(A, B){C} != T(B, A){S}
This is very important. Past discussions have been using a notional
transform function that only produces one output and this is not correct
when discussing wave OT.
In a client that can have unacknowledged deltas, there will be two kinds of
deltas. The first is a transmitted but unacknowledged delta, and the second
is a un-transmitted delta. The transmitted delta becomes immutable as soon
as it's transmitted, but the un-transmitted delta can be composed with other
client generated edits prior to it being transmitted.
Given the composition function C(X, Y) = Z:
If A ia:
A.characters("16")
and B is:
b.deleteCharacters("15")
b.characters("16")
then C(A, B) produces:
C.characters("16")
For this next bit the conventions are:
D = A delta
D{v} = The version against which this delta is intended to be applied.
D{a} = The version at which this delta was applied by the server (possibly
after transformation).
D{o} = The operation for this delta.
D{1, 3, X} = A delta with version 1, "applied at" version 3 and operation X.
H = An array of deltas.
H <- X = H with X appended.
H[2, 4] = The set of deltas with "applied at" versions 2 through 4
inclusive.
H[last] = The last delta in H
N = The transmitted but unacknowledged client delta.
Nt = N transformed against any deltas that occurred before it on the server.
P = The composition of all un-transmitted changes at the client.
Q = A set of deltas ordered by their "applied at" version.
Q{first} = The delta in Q with the lowest "applied_at" version.
Q{next} = The delta in Q with the lowest "applied_at" version is removed and
returned.
R = The composition of all client generated operations and all server deltas
excluding client acknowledged deltas.
C(H[1, 3]) = The composition of all deltas between 1 and 3 inclusive.
When the server receives a delta it does:
H <- T( C1, C( H[ D{v}+1 , H[last]{a} ] ) ){C}
When the client produces a new operation O, it does:
R = C(R, O)
IF N == NULL
N = D{H[last]{a}, ?, O}
Nt = O
ELSE
IF P == NULL
P = O
ELSE
P = C(P, O)
IF D is the original untransformed delta AND D{V} + 1 < D{A}
H <- T( D{O}, C( H[ D{V} + 1, D{A} ] ) ){C}
ELSE
H <- D{O}
WHILE Q{first}{a} - 1 == H[last]{a}
D = Q{next}
IF D == N
IF P != NULL
IF D{V} + 1 < D{A}
P = T( C( H[ D{V} + 1, D{A} ] ), P ){S}
N = {D{A}, ?, P}
Nt = P
ELSE
Ot = H[ D{A} ]
IF N != NULL
{Nt, Ot} = T(Nt, Ot)
IF P != NULL
Ot = T(Ot, P){C}
R = C(R, Ot)
You'll notice that D{O} is treated as a server operation with respect to
N{O}, but is treated as a client operation with respect to P. This is
because N and P have already been applied to R and D{O} must be transformed
such that it appears as if it was applied before N{O} but after P.
--
You received this message because you are subscribed to the Google Groups "Wave
Protocol" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/wave-protocol?hl=en.
