[<<][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][>>][..]