On 24/02/2009, at 1:39 PM, Jeff Hinrichs - DM&T wrote:
scenario, master-slave -- slaves only keep the most recent, while the
master keeps complete. conflict resolution is handled solely by the
master.
scenario, first-among-equals -- multi-master where a single master is
used as the basis for conflict resolution, other masters keep only a
limited rev history and escalate to the first-among-equals when
Eventual Consistency can not be reached do to missing rev history on a
peer.
My initial thought is that Eventual Consistency amongst a set of peers
is dependent purely on anti-entropy guarantees, no partial
replication, and deterministic conflict resolution. The idea of
Eventual Consistency is that the peers will end up with the same
database contents. Given pruning or revision stemming, this is only
true if you regard database equality as not including revision history
e.g. it's the head revision + conflicts.
But then I developed a thought experiment where this wasn't clear - in
particular whether you can rely on conflicting versions being included
in the state. Consider 4 peers, with one document, each peer having a
different revision.
P1 = [ A1 ] & P2 = [ A2 ] & P3 = [ A3 ] & P4 = [ A4 ]
Now bidirectionally replicate P1 & P2: [ A1, A5=A2/A1 ] where A4=A3/A2
means A4 is the head revision, identical to A3 but with a conflict
reference to A2. This is Eventual Consistency for P1 & P2.
Now bidirectionally replicate P3 & P4: [ A3, A6=A4/A3 ]. This is
Eventual Consistency for P1 & P2.
Now replicate P1 and P3. Obviously one of { A5, A6 } will be chosen
deterministically, but are the conflicts chained? Do you end up with
[ A2, A3, A5=A2/A1, A7=A4/[A3,A5] ]. How is it intended to treat the
conflicts already present in documents undergoing conflict resolution?
Even writing this out is hard.
Antony Blakey
--------------------------
CTO, Linkuistics Pty Ltd
Ph: 0438 840 787
Always have a vision. Why spend your life making other people’s dreams?
-- Orson Welles (1915-1985)
