Subject: RE: 5. "Oscillation"

From: "Ramsay, Ron" <[email-masked]>
Date: Tue, 18 Jul 2000 12:13:03 +1000

Albert,

I don't accept your proof. My eyes are URP-glazed but I think you proof
fails from common sense alone.

Your proof depends on ordering of CSNs, as if they can be ordered. Yet,
presumably, the CSNs are originated by the source. They will, therefore, be
capable of ordering in general, but clashes may occur. To construct a
counter-example, you will probably set the CSNs to all the changes to be the
same, say 7.

Of course, mostly the CSNs will be different and this will produce a
deterministic result. Semantically, it feels odd as the server with the
highest CSNs will, in effect, arbitrate the result.

Ron.

-----Original Message-----
From: Albert Langer [mailto:[email-masked]]
Sent: Tuesday, 18 July 2000 10:20
To: [email-masked]
Cc: [email-masked]
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.

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: "Albert Langer" <[email-masked]>
Date: Tue, 18 Jul 2000 18:20:18 +1000

[Ron]

[Albert]
The URP CSN is defined with four components as specified in the architecture
draft, 4.5.1:

"In order of significance they are; the time, a change count, a Replica
Identifier, and a modification number. The CSN is composed thus to ensure
the uniqueness of every generated CSN."

I believe that clearly does ensure the uniqueness of every generated CSN as
intended. The three components time, change count and modification number
ensure uniqueness within a replica, and the remaining component, replica
identifuer, ensures global uniqueness within the replication set.

Therefore no counter-example could be based on CSNs for different changes
having the same value.

4.5.1 continues: "When CSNs are compared to determine their ordering, they
are compared component by component. First the time, then the change count,
then the replica identifier, and finally the modification number."

This does establish a strict ordering of CSNs. Whenever the other 3
components of two CSNs generated at different replicas happen to have the
same time, change count and modification number, the result is arbitrarily
determined by the replica with the highest replica identifier. I agree that
"feels odd", but it does guarantee convergence.

In my view it is a clumsy and confusing way to do it, but that isn't worth
arguing about at this late stage, as long as it does do it. The "change
count" is really an internal implementation detail for coordinating multiple
threads within a DSA, and need not be carried by protocol at all. MDCR just
uses the timestamp plus version number to guarantee uniqueness of USNs
generated by a DSA (for a single entryID).

The difference is simply that URP gives priority in the lexical ordering to
the combined timestamp represented by the time and change count, while MDCR
gives priority to the version number. Both apply the last component, replica
identifier in the same way to guarantee uniqueness among all DSAs and
arbitrarily impose a strict ordering. However MDCR applies this only as a
last resort and treats the version number as the principal determinant of
priority among concurrent changes. In practice the fact that URP applies
that arbitrary last resort slightly earlier does not really matter as the
whole ordering is arbitrary anyway and the remaining three components will
almost always be unique.

The precise ordering of timestamps generated for concurrent changes at
different replicas is inherently arbitrary as clocks are not synchronized.
All it creates is the *illusion* of time ordering. The reality is that
changes are concurrent, not serialized, when made at different replicas to
the same entry state. It doesn't really matter which change succeeds as long
as no more than one of them does.

This seems a good point to mention a significant advantage of the
Coda/Active Directory method of using version numbers as the primary
determinant of priority for resolving conflicts among concurrent changes.

Typically, concurrent changes will have different timestamps. The fact that
occasionally they will have identical timestamps is focussed on by URP, thus
distracting attention from the fact that they are still concurrent, not
serialized, whether they have the same timestamp or not. The simple fact is
that each concurrent change was made without knowledge of the state
resulting from the other(s).

MDCR makes this explicit by recognizing concurrency whenever the version
numbers are different (or are the same but generated at different replicas,
hence the need for a tree).

A consequence is that regardless of timestamps, the final state of an entry
that is changed more frequently at a particular replica during a conflict
will ultimately prevail over conflicting changes made at other replicas.

Typically a conflict will simply occur between just two changes made at two
different replicas and MDCR will arbitrarily converge to the change made by
the replica with the highest replica number, regardless of timestamps.

But on the rare occasions when there is a non-trivial tree of conflicts,
because additional changes have been applied to the visible changed entries
at a replica before they become "durable", MDCR will recognize this and give
priority to the longest possible sequence of changes that could have been
serialized.

For example if two successive changes are made to a single replica at A,
while a concurrent single change is made at B, the result will converge to
the final state represented by the second change at A.

This is more significant than it seems. The entries that are being changed
most often are those being actively worked on. If an application is trying
to coordinate a transaction by first setting some sort of transaction
identifier on all the related entries, then changing them and all and coming
back to finalize the transaction, it is more likely to ultimately succeed
and become durable, than a conflicting single change made by another DUA
that is not part of a transaction.

Although the main point is to ensure that conflicts are actually resolved,
not merged. This is a significant optimization of the resolution. The Coda
research has full details.