[ogpx] State "Partitions" should be Abelian (was: My take on Teleports and protocol resilience)

[Carlo Wood <[e-mail]>]

On Tue, Oct 27, 2009 at 10:32:39PM +0100, Vaughn Deluca wrote:
> OK, you convinced me regarding the bandwith. We are talking very low frequency
> user generated changes, and a small amount of data is passed by reference.
> Should be no problem.
> 
> I am still worried about the detour, but  i have no argument, just a gut
> feeling  :)
> 
> I do not see the need to send the movement instructions via the AS. It will ony
> generate unneeded delays, and that info is not part of the avatar state anyhow.
> Why "even" movment?

I meant that even movement of the avatar is low bandwidth.
But you're right that for teleportation it is not needed to use
the AS as authority, because movements are location updates
and that state is replaced during change of region.

---

Note that, apart from the authority- and unidirectional- story,
it is in general also important that state changes are ordered.

If we expect messages that update state to be lost, then there
two several ways to recover:

1) ask for a resent and queue "later" messages until the missing
   one is received.
2) send a full resync every time.

1 introduces possible lag, and in the case of extreme packetloss
might even cause memory problems because the later messages have
to be queued. 2 is only possible when the total state data is
very small, but possible for example in the case of attachments.

Abstract example:

Consider a case where a state has three possible values:
    A, B or C; which are internally represented by 1, 2 and 3.

Instead of sending only *changes*: +1, -1, +2, -1, -1, ...
It makes much more sense to send "full updates": B, A, C, B, A, ..

In both cases however it is necessary to include a sequence
number if the messages can be received out of order.

---

Thus, assuming that sending "full states" makes sense in most
cases, we have to try to devide a state into uncorrelated parts.

Example, suppose a state exists of a vector of uncorrelated
data: { d1, d2, d3, d4, ... }, then instead of sending the
whole vector when 'd3' changes, it suffices to only send the
"full update" for 'd3'.

The question is: what means uncorrelated here?

In the light of synchronization (our main concern), I believe
that it means that a commutating operator can be defined. That means,
if two (or more) state-parts correlate but the net result is the same,
independent of the order they are applied in, then we can treat
them as "uncorrelated" in the light of the above, and send separate
"full state changes" for each (or state updates if we wish, of course).

Example: If the sum (f) of states a and b can be considered
as a binary operator f(a, b), and f(a, b) = f(b, a) (commutative)
then a and b can be treated as uncorrelated because their
order (in which they are applied) doesn't matter.

This is the case for animations of different priority (I believe,
but I might be wrong), and for animations that act on a different
part of the avatar. It is also the case for attachments of different
attachment points.

Hence, we can send "full updates" PER attachment point (just send
"attachment point XYZ now contains attachment ABC"), and ignore
all the other attachment points, BECAUSE the net result of such
operations of all attachments points is order-insensitive.


The reason I brought this up is because, in the past, I've been
thinking about the implementation of multiple attachments on a
single attachment point and from a (human) management point of
view came to the conclusion that attach/detach operations for
a single attachment point also have to commute. Meaning, if you
attach X to point P, and then attach Y to point P, then the
result must be the same as first attaching Y to point P and
then X to point P.

Now note that if that is the case, then you can consider the
full set of attachments as a binary vector of zeroes and ones,
one for each attachment (not point), and send "full updates"
per bit. Basically you'd be saying: XYZ is now attached (plus
sequence number) and XYZ is now detached, etc.

So, in that case we have all the benefits :)... these ARE
"full updates", but clearly they are also "state CHANGES"
for the whole-state "attachments".


Conclusion, we have to keep a close eye on the commutativity
of operations and use it to dissect larger states into smaller
parts and use that to our advantange. We have to be aware of
the crucial part that commutativity plays, down to the lowest
level of protocol and synchronization issues.

-- 
Carlo Wood <[e-mail]>