[<<][math][>>][..]
Fri Jan 11 17:13:19 EST 2013

Synchronizing "simultaneous" distributed updates.

Suppose 2 data stores D and D' are linked by a non-instantaneous link
which is used to keep the state in both stores the same D == D'.

However, it might happen that a data item d @ D gets updated at the
same time as its twin d' @ D', both to different values.  The finite
time delay between the updates makes this problem a practical one.

How does this usually get solved?  Supposedly there is some kind of
arbitration order imposed on the updates, either by site or in real
time.

EDIT: I found a solution I like because of its simple symmetric
implementation:

- store prev and cur values in both A and B sides.
- if (cur != prev) { send(cur); prev = cur; }

This works well for non-simultaneous updates.  E.g. if a value in A
changes, a message A->B is sent once.  After B receives, it will send
this value back to A.

This has the problem of concurrent updates causing an oscillation if
queue read and write are interleaved as follows:

A: B->set(1)
B: A->set(2)

A: receive set(2)
A: B->set(2)

B: receive set(1)
B: A->set(1)

...

To break this oscillation some kind of order needs to be introduced:
set one of the two as master. E.g. A will always propagate on receive,
but B will never.

Note that one of the two needs to bounce the value, otherwise
simultaneous value changes will not be resolved, and both sides will
end up with different states.



[Reply][About]
[<<][math][>>][..]