RE: 5. "Oscillation"

["Steven Legg" <steven.legg@xxxxxxxxxxxxx>]

Albert,

> -----Original Message-----
> From: owner-ietf-ldup@xxxxxxxxxxxx
> [mailto:owner-ietf-ldup@xxxxxxxxxxxx]On Behalf Of Albert Langer
> Sent: Tuesday, 18 July 2000 10:20
> To: steven.legg@xxxxxxxxxxxxx
> Cc: ietf-ldup@xxxxxxx
> Subject: 5. "Oscillation"
>
>
> Steve,
>
> Here's the response to item 5, which I summarized as:
>
> ***
> 5. "Oscillation". Implicit agreement that no protocol should
> oscillate. No
> need to state in requirements as both obvious and covered by
> 4 above. Steve
> says he has an example showing that MDCR oscillates. I say
> that neither MDCR
> nor URP oscillates. Unfortunately the margin of this email is
> too small for
> the proof ;-) Fortunately it is short enough to present in
> another email
> rather than leaving the world waiting breathlessly for
> hundreds of years...
> or subjecting it to eyeglazing discussion of examples.
>
> http://www.imc.org/ietf-ldup/mail-archive/msg00614.html
>
> ***
> Comments follow original below.
> ***
>
> [Steven]
> Also, I can also construct examples where two replicas endlessly flip
> back and forth between two competing strands with no entry
> versions ever
> becoming durable.
>
> > A simpler approach to conflict resolution would just resolve
> > each conflict
> > immediately, at each DUA that encounters a conflicting change, by
> > suppressing the change with the lower version number etc and
> > propagating
> > only 1 survivor (which may itself be suppressed at another
> > DUA with the
> > survivor propagated from that conflict in turn reaching the
> > previous DUA and
> > suppressing the previous survivor there).
>
> I don't think this is enough to solve the problems mentioned above.
>
> [Albert]
> Well, all you need to do is exhibit just one of those
> examples and I am sure
> everyone, including me, will agree that MDCR is unacceptable.

Okay.

Suppose I have two replicas, R1 and R2, and an application that
modifies a particular entry, E, at intervals of one hour.
One instance of the application sends its modify requests to R1 every
15 minutes past the hour. A second instance of the application
sends its modify requests to R2 every 45 minutes past the hour.
The replication agreements are set up such that R1 initiates a replication
session with R2, every hour on the hour, and R2 initiates a replication
session with R1, every hour on the half hour.

I'm using the tuple (version, originator, previous)
to identify a record in the tree of changes to an entry.

Let's assume that E already exists and that the root of the changes tree
is identified as (1, R1, -) for both replicas.

At time 0:15, E is changed at R1. This creates a new change record
(2, R1, R1).

At time 0:30, R2 sends unreported changes to R1. At this time it is an
empty set so nothing interesting happens.

At time 0:45, E is changed at R2. This creates a new record (2, R2, R1).

At time 1:00, R1 sends changes to R2, i.e. (2, R1, R1). Since (2, R2, R1)
has a higher modify timestamp and R2 > R1, R2 doesn't alter its current
version of E.

At time 1:15, E is changed at R1. This creates a new record (3, R1, R1).

At time 1:30, R2 sends changes to R1, i.e. (2, R2, R1). Since (3, R1, R1)
has the highest version number, R1 doesn't alter its current version of E.

At time 1:45, E is changed at R2. This creates a new record (3, R2, R2).

At time 2:00, R1 sends changes to R2, i.e. (3, R1, R1). Since (3, R2, R2)
has a higher modify timestamp and R2 > R1, R2 doesn't alter its current
version of E.

... and so it goes on, ad infinitum, with the two replicas growing two
independent strands in the change tree for E. Neither strand ever becoming
the single durable strand.

If you set the replication schedules the right way (R3 <-> R1 at h:20,
R3 <-> R2 at h:50) a third replica will alternate between these two strands.

>
> I found the discussions of various examples of URP failures
> when wading
> through the archives quite eyeglazing, so I can sympathize with your
> reluctance to spark another such discussion.
>
> Here's a semi-formal proof that neither I nor anybody else
> will be able to
> come up with an example showing that URP also oscillates.
>
> Consider a finite set of N replicas and a finite set of
> changes applied to a
> single entry at some or all of those replicas within a finite
> time interval.
>
> 1. There is a finite set of CSNs resulting from the original
> entries and the
> changed entries that result, and a one to one association
> between the CSN of
> an entry at a replica and the state of that entry at that replica.
>
> 2. This finite set of CSNs is strictly ordered and imposes a
> corresponding
> strict ordering on entry states. Exactly one entry state
> corresponds to the
> highest CSN in that strict ordering.
>
> 3. That entry state will replace any other it encounters and
> will therefore
> propagate to all replicas. (Leaving aside the fixable problem
> with relying
> on time stamps etc).
>
> 4. Therefore all entries will converge to the same state.
>
> There may be a combinatorial explosion of transient states
> and some of them
> may be "Transient Extraordinary States", but URP *will*
> converge to some
> common state, which may be regular or "Extraordinary"
> depending on factors
> beyond the scope of this analysis (and possibly any other).
>
> If you accept that proof as showing URP converges you should
> accept that the
> same proof shows  MDCR converges, as you have agreed that
> CSNs and USNs are
> similar strict (lexical) orderings.

Your proof neglects the role of the purging mechanism. You have to show
that all replicas will get all changes in spite of the cleanup going on
in parallel, and in spite of the effects of restoring a replica from
backup.

Having shown that all replicas get all changes it is still necessary to
show that all possible processing orders of the change reports produce the
same outcome. The open-endedness of the list of changes can't be neglected
either.

Regards,
Steven

>
> The only differences are:
>
> a) In para 3, MDCR propagates all changes to all replicas whether they
> immediately replace the current entry there or not. It is
> slightly more
> obvious, though no more true, that the change with the
> highest USN will be
> propagated to all replicas, and therefore will become the
> convergent entry
> at all replicas.
>
> b) The number of visible entry states (and of tree history states) at
> different replicas is never greater than the number of actual
> changes that
> were made concurrently at different replicas. With MDCR there
> are no new
> "transient" states and no combinatorial explosion.
>
> c) The final result is completely predictable and never
> "Extraordinary".
>
>