5. "Oscillation"

["Albert Langer" <Albert.Langer@xxxxxxxxxxxxxxxxxxxxx>]

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