Subject: 5. "Oscillation"

From: "Albert Langer" <[email-masked]>
Date: Tue, 18 Jul 2000 10:20:28 +1000

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.

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.

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".

---

From: "Steven Legg" <[email-masked]>
Date: Wed, 19 Jul 2000 14:34:28 +1000

Albert,

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Albert Langer
> Sent: Tuesday, 18 July 2000 10:20
> To: [email-masked]
> Cc: [email-masked]
> Subject: 5. "Oscillation"
>
>
> Steve,
>

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.

> 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