Subject: RE: New LDUP requirements draft

From: "Ed Reed" <[email-masked]>
Date: Wed, 28 Mar 2001 06:22:22 -0700

Hahahaha...hahaha...haha...

This requirement is there, I believe, to placate Albert.

I believe the requirement MAY be satisfied IFF log-based replication
is used to retransmit the update via LDUP as long as no one else
has gotten to the modified entry first via an update to some other 
master (i.e, as long as there are no conflicting collisions).  If there
are conflicting updates, I think the result that Albert would like to
see is that the update that collides is bounced in some way for
administrative resolution.

For state-based replication the requirement is meaningless, since
state-based replication has as its goal to make all the replicas
hold the same values, and it never pretends to try to reproduce
the operations which were entered to get them to that state - 
it doesn't care, because it is the ultimate state that is important.

Believers in state-based replication believe the end justifies
whatever means are necessary to achieve a common view
of the data.  Believers in log-based replication think getting
there is most of the fun.

Thus, my long-held belief that it MAY BE possible to replicate
transactional semantics of some sort via log-based replication
schemes (who can record and playback the transactions
in question), but it will NEVER be possible to do so with
state-based replication schemes.

I would strike the requirement, as I don't think its either
useful or interesting to the class of applications for which
I expect LDUP to be used for - distributed administration
of policy information.

There are other applications, which require the behavior
specified in this requirement in order to provide a test-
and-set form of operation which I do not believe LDUP
will ever adequately support.  At least not with the
protocol mechanism as we've attempted to define it
so far.  

I honestly believe that the most useful protocol for us
to define at the moment is one that interleaves
non-conflicting attribute value changes occuring
to an entry at various master replicas in such a way that
when all the replicas have received the modifications
from all the other replicas, they all present the same
entry to readers.  The only way to achieve that is
to share administration of attributes "liberally", and
to restrict consistency requirements only on those
attributes that are effectively "private" to the application
that has the requirement for special consistency.

So my interpretation of the "be liberal in what you
accept and conservative in what you send" is that
applications ought not expect atomic in-sequence
application of modification operations to propagate
via replication (be liberal in what they accept from
the server), and servers ought not be obliged
to attempt to provide it (be conservative in what
they send during replication).

I'm so glad we ducked this converation at the meeting...
I could see this conversation coming from a mile off.

I've completed a review of the requirements document
from the perspective of the information model and
architecture documents, and will post my results
later this week.  

Ed
>>> "Timothy Hahn" <[email-masked]> 03/27/01 05:15AM >>>
Steven,

I agree that it seems there is a need to clarify this requirement.  I 
think that it may be interpreted differently.  If this is the intent (i.e. 
leave it intentionally vague - perhaps to allow for lattitude in 
implementations?) then so be it.  If the intent is to make something more 
clear, then the requirement should be clarified/explained in more detail.

Regards,
Tim Hahn

Internet: [email-masked] 
Internal: Timothy Hahn/Endicott/IBM@IBMUS or IBMUSM00(HAHNT)
phone: 607.752.6388     tie-line: 8/852.6388
fax: 607.752.3681

"Steven Legg" <[email-masked]>
Sent by: [email-masked] 
03/27/2001 02:30 AM
Please respond to steven.legg

        To:     "'Richard V Huber'" <[email-masked]>, <[email-masked]>
        cc:     Ellen Stokes/Tivoli Systems@Tivoli Systems, <[email-masked]>, 
<[email-masked]>
        Subject:        RE: New LDUP requirements draft

Rick, et al,

> -We feel that discussion of propagating end state vs. changes is about
> implementation.  Rather, P6 (now P7 due to other changes) has been
> rewritten to explicitly require propagation of atomicity of LDAP
> operations as defined in RFC 2251. We feel it is now self justifying.

I don't know how I should interpret the new P7 requirement, reproduced
immediately below.

> P7.  The protocol MUST preserve atomicity of LDAP operations as defined
> in RFC2251 [RFC2251].

The wording is the same in draft-ietf-ldup-replica-req-07.txt and
draft-ietf-ldup-replica-req-08.txt.

At face value P7 could be interpreted as requiring a previously accepted
update to be rejected during replication processing if any part of the
update, e.g. a single modification in a modify request, is not performed
because it is redundant, e.g. it attempts to insert a value that already
exists, or has been superseded, e.g. a more recent update deleted the
value.

This interpretation is at odds with other sections of the requirements
document, contrary to the author's position as I understood it, and
contrary to the working group consensus, so P7 must mean something else.

What exactly is P7 requiring of the LDUP protocol ?

Regards,
Steven

=================
Ed Reed
Reed-Matthews, Inc.
+1 801 796 7065
http://www.Reed-Matthews.COM

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Wed, 28 Mar 2001 10:21:55 -0800

>This requirement is there, I believe, to placate Albert.

it placated me as well.  :-)

I believe it critical that the replication system be capable
of detecting and reporting operations which would were guaranteed
to fail in the X.500 data and service model.  In particular,
if two clients independently request (in a single modify)
"Delete value X, Add value Y" to the same attribute (which
has value X) of the same entry and the directory system only one
can succeed (per existing LDAP/X.500 specification).  However,
in face of multiple-master replication (with less than model 1
consistency between masters), both could succeed (if issued on
different masters).

As there are existing applications which make use of the
atomic properties of LDAP/X.500, it is critical that if
conflicts were to arise in a deployment, the system should
be capable of notifying the administrator of the conflict.

I concur with Ed in that this requirement would rule out
state-based replication designs.  I disagree that the
requirement should be stricken.

Kurt

---

From: "Albert Langer" <[email-masked]>
Date: Thu, 29 Mar 2001 10:19:26 +1000

[Ed]

[Albert]
The proposed requirement is there because the requirements editors
have proposed it. They have certainly made no attempt to placate
me concerning the meaningless requirements to support ACID
transactions and eventual divergence, so I doubt that they
are unduly concerned about placating me ;-)

I fully agree with all of the following included in the original
messages you are responding to:

a) Tim's view that it needs to be explained and justified (whether
in the requirements document or elsewhere).

b) Steven's view that it is contrary to what was previously
understood to be the prevailing view in the WG and cannot be
regarded as indicating any kind of consensus on that proposal.

Ed, you chose not to respond further after initiating this
discussion yourself during the last WG call and indicating
in email that you would be doing so.

http://www.imc.org/ietf-ldup/mail-archive/msg00855.html

http://www.imc.org/ietf-ldup/mail-archive/msg00873.html

You of all people should have seen it coming.

Like it or not any decision either way will have to be thoroughly
justified to the WG in technical discussion on this list - and very
likely in I-Ds if disagreement continues at IETF final call.

If it had not come up as a result of WG last call, it would have
come up at IETF last call.

Somebody is going to have present arguments for the current
conflict resolution approach in the architecture that will
withstand careful IETF scrutiny. Judging from Steven's
remark so far that "it must mean something else", it looks like
that person may have to be you.

Please put aside anything else and focus entirely on those
arguments. You aren't going to get past IETF final call with
either "it must mean something else" or
"Hahahaha...hahaha...haha..." etc.

This is your chance to polish up the arguments - *now*.

[Ed]

[Albert]
The definition of atomicity is that an operation either succeeds
or fails as a whole. There is a clear separate requirement which
has been there since September last year that if any directory
information is lost as a result of conflict resolution there must be
administrative notification. If you are opposed to that requirement
you should have said so then, and should say so now, and should
do so without attributing to me views opposite to those I have
repeatedly stated.

My view is that it is sufficient in the requirements document to
only require administrative notification only because that is enough
to be able to move on and start actually reviewing the architecture.
It ensures that any architecture which actually meets the requirement
will be capable of being extended to support notification to whoever
is responsible for the DUA that changed whatever got "bounced" (eg
by email and/or LCUP).

However I do not believe administrative notification is sufficient
even for create/rename conflicts and have already put on record that
I will oppose at IETF final call any architecture that does not
actually implement direct notification of any loss of directory
information arising out of multi-master replication that would
not have occurred with single master.

My reasons are:

a) Multi-master will be deployed alongside single master in a
developing global internet (not "enterprise") directory service
specifically designed to present a uniform "Directory Information
Tree" in which applications do not need to know much about the
specific servers they are using provided they are LDAP servers,
and are routinely given referrals to other servers that they
have no previous knowledge of.

Applications already deployed to expect the behaviour of single
master (immediate failure response for operations that fail),
will break when referred to servers that do not support the
existing behaviour. Unexpected behaviour cannot be avoided with
multi-master, but everything possible must be done to minimize
any negative effects while obtaining the positive benefits.
Prompt notification as soon as possible after the unexpected
event is both the most and the least we can do, so as an IETF
WG concerned with global internet standardization we have an
obligation to do it. Standards are about *squelching* ideas
that hinder interoperability, not about endorsing vendors
bad ideas.

b) Multi-master is unsuitable in situations where update
conflicts frequently occur within the period for propagation
of updates across the replication network. As well as you
having explicitly agreed with that, nobody has so far
expressed any continuing disagreement, so I believe it is
safe to assume there is a consensus on that unless somebody
speaks up now. (Though it would probably be useful to
document an explanation of why, as there is obvious
confusion about many such issues).

Consequently any architecture that can support the long
standing proposed requirement for administrative notification
will not be greatly burdened by adding support for direct
notification to DUAs. The minimum just needs some work on
the information model to specify that the originator DSA
of a change that "bounced" is responsible for promptly
informing the email address listed for the DN of the DUA
that was the creator or modifier of the lost information,
plus a format for such messages. Further extensions may be
desirable, but that's the minimum and it's no big deal.

c) Even a very low rate of lost directory information
is completely inappropriate for manual resolution by
administrators. They aren't the sources of the data
and would either have to ignore the notifications
or contact the users concerned to fix the problem.
Directory administration is being delegated downwards
to end users with no technical knowledge, and to
automated applications, as rapidly as possible and
DSA or DMD administrators have more important things
to do than fix broken protocols manually.

If you disagree with that perspective it would be helpful
if you presented your arguments about it at the same time
as this atomicity discussion as the two are closely related
and will both end up having to be discussed during
architecture review and/or IETF final call.

[Ed]

[Albert]
There is a clear requirement for eventual convergence which
nobody has dissented from and can be assumed to be a consensus.
Assuming that you are not suggesting that atomic replication
cannot support eventual convergence, there is no technical
content in the above paragraph.

There is no proposed requirement that we use a state-based
replication scheme. If you think there should be such a requirement
you should have proposed it two years ago rather than designing
an architecture before signing off on requirements and you should
propose it now since it simply isn't there.

[Ed]

[Albert]
There is no technical content in that paragraph whatever,
with or without any plausible assumption about what you may
or may nor believe.

I do not find a "belief" that the "end justifies whatever
means are necessary" an appealing philosophy. The issue is
what is the end and what means are necessary. Figuring out
where we want to go and how to get there can indeed be fun.

[Ed]

[Albert]
As part of this discussion I believe it would be very useful
both for LDUP work and possible publication for the benefit
of users to reach a common understanding of terminology and
publish that as soon as possible as an I-D.

The current discusison is about requirement P7, not about
"transactional semantics".

Are you saying above that "it will NEVER be possible" to comply
with P7 "with state-based replication schemes"?

If so:

1. You were a co-author of the first architecture draft (00), dated
1 August 1998 and submitted prior to the WG charter being approved.

That draft included the following provisions:

3.2 Document Objectives
[...]

  c) To preserve the atomicity of LDAP operations.  Updates to an entry,
    from multiple sources, will be combined such that the resultant
    entry is equivalent to a serial execution of the operations.

8.2.2 Incremental Update Transfer
[...]

  Each individual change may contain a sequence of entry modifications
  that must be preserved when transferred. The atomicity of the LDAP
  operation must be preserved when it is applied to the Consumer
  Replica.

http://www.imc.org/ietf-ldup/mail-archive/msg00138.html

1. Did you believe then that the objective and specification you
proposed was:

1.1 Desirable.

1.2 Required in order to comply with LDAP standards and obtain a
charter for the LDUP WG?

1.3 "NEVER be possible to do so with state-based replication schemes"

2. Was any technical explanation published when you decided to
remove these from the architecture draft? If so, please provide
the URL.

3. What is the protocol distinction relevant to IETF standardization
of the "on the wire" protocol, between the term "state-based"
replication scheme and the term "non-atomic" replication
scheme? Does a "state-based" replication scheme have some other
feature that distinguishes it from a replication scheme capable
of complying with P7 and RFC 2251?

3.1 What are the technical benefits of a "state-based" replication
scheme that would justify not preserving the atomicity of LDAP
operations as defined in RFC2251? (In other words, why should the
IETF care about whether a "state-based" scheme could comply,
as opposed to a vendor proposing a "state-based" scheme caring?)

3.2 Are "state based", ie non-atomic, replication schemes capable
of reliably supporting an access control standard similar to either:

	a) The current LDAP-EXT draft.

	b) The X.500 standards

	c) Any non-proprietary widely used approach to access
control such as those derived from UMich implementations?

3.3 What are the consequences for deployment of LDAP and X.500
applications across the global internet with DSAs passing
referrals to other DSAs, some of which support atomic operations
when others do not?

3.4 Should RFC 2251 be altered to remove the requirement for
atomic operations?

3.5 Should similar changes be made to the X.500 international
standards?

3.6 Has anyone proposed any such changes?

These are questions which should all have been addressed when
LDUP first considered adopting a non-atomic replication scheme
and must be addressed now. It is up to you to address them.
Please do so - *now*.

4. Do you agree with the proposed requirements then numbered P6,
and MM5 and MM6 (unchanged) and the definitions that have been
in previous drafts since September last year:

vvvvvvvvvvvvvvvv
Atomic operation - A set of changes to directory data which the LDAP
standards guarantee will be treated as a unit; all changes will be made
or all the changes will fail.

Atomicity Information - Information about atomic operations passed as
part of replication.

Conflict - A situation that arises when changes are made to the same
directory data on different directory servers before replication can
synchronize the data on the servers.  When the servers do synchronize,
they have inconsistent data - a conflict.

Conflict resolution - Deterministic procedures used to resolve change
information conflicts that may arise during replication.

Update Propagation - Protocol-based process by which directory replicas
are reconciled.

P6.  The protocol MUST support propagation of atomicity information.

MM5.  Multi-master replication MUST NOT lose information during
replication.  If conflict resolution would result in the loss of
directory information, the replication process MUST store that
information, notify the administrator of the nature of the conflict and
the information that was lost, and provide a mechanism for possible
override by the administrator.

MM6.  Multi-master replication MUST support convergence of the values
of attributes and objects.  Convergence may result in an event as
described in MM5.
^^^^^^^^^^^^^^^^^^^^^

4.1 If you support the above, how could a "state-based"
implementation support the propagation of information about atomic
operations required in order to store directory information that
would otherwise be lost, notify administrators and provide an
overide mechanism, if it is not also able to "preserve atomicity
of LDAP operations as defined in RFC2251". In particular why is
it both possible and desirable to do so for create and rename
conflicts handled atomically by "state-based" implementations
but either not possible and/or not desirable to do so for other
conflicts as specified in the LDAP standards?

4.2 If you do not agree with those requirements and definitions,
why did you as an author of the architecture draft, not
raise any objection to them in the last six months during which
they went through revisions 04, 05, 06 and 07 before reaching
the purely editorial corrections announced for 08?

4.3 Do you now agree with my view that those requirements
did not clearly enough resolve an issue that must be resolved,
one way or another?

[Ed]

[Albert]
What is there about distributed administration of policy
information that makes preservation of atomic operations
less useful for that class of applications than for other
applications envisaged by the X.500 and LDAP standards in
imposing that requirement on DSAs?

In the earlier discussion at the first two URLs above,
you quoted my statement:

"My view is that the critically important requirement that
applications depend on is simply that a change can be
reliably made to exactly the entry you thought you
were changing and not result in some mixture of
updates combined with unknown concurrent changes
by some other application."

You agreed that this was "the crux of the matter" in
rejecting that view. You have not responded to my
reply and I cannot even imagine why you would think
that administration of policy information (eg access
control information) is *less* dependent than
other applications on being able to reliably change
exactly what you thought you were changing rather
than implementing a "policy" based on a combination
with unknown concurrent changes.

[Ed]

[Albert]
What specifically are those other applications and why
do you think the X.500 standards and the LDAP standards
made provision for their needs?

[Ed]
entry to readers.

[Albert]
There nothing in the technical part of the above
paragraph that is either inconsistent with P7 or not
completely covered by:

M3.  An attribute in an entry must eventually converge
to the same set of values in every replica holding
that entry.

I will not form an opinion about the non-technical
part of this paragraph until after I have carefully
studied your response to all my questions above.

If you stick to relevant technical arguments from now
on I will respond to those arguments on their merits
regardless of what opinion I may form as to matters
that are now in the past. We have a job to do and
it must be done on the basis of the WG as a whole
fully understanding the technical issues, and reaching
a "rough consensus", which may well include strong
disagreements, but must be based on a common
understanding of the issues being resolved.

That cannot be based on discussion of what anybody
believes about "non-conflicting attribute value
changes" or "eventually converging to the same
set of values", or how honestly they believe it.

[Ed]
The only way to achieve that is

[Albert]
I do not understand these two paragraphs at all.
Please elaborate. My view is that multi-master
replication with "eventual convergence" necessarily
requires absolutely identical behaviour - both as
to what is received and as to what is sent, by all
DSAs holding a replica. Therefore I do not regard
the well known architectural principal of "be
liberal in what you accept and conservative in
what you send" as being applicable to LDUP work.

If it is applicable, I simply do not understand
what you are getting at in your application of it.

[Ed]

[Albert]
I too am glad that we are now having a technical
discussion on these issues in the WG mailing list.
I was much further away and saw it coming much earlier.

"Hahahaha...hahaha...haha..."

Sorry, couldn't resist ;-)

[Ed]

[Albert]
Looking forward to it.

It would also be helpful if Steven and Alison
were now to follow up on the following item from the
minutes of the Adelaide IETF WG session a year ago:

vvvvv
7) LDUP Update Reconciliation Procedures (Steven)
file: draft-ietf-ldup-urp-02.txt

This draft did seem ready for last call, but now we may need
to reconsider it given Mr. Langer’s alternate proposal. The
authors are looking at making a future revision to accommodate
the updating of partial replicas.  Steven and Alison point out
that the main difference between URP and other approaches is
whether conflicts are merged or resolved immediately. Steven
and Alison also note that this subject keeps coming up.
Therefore, Steven and Alison have volunteered to write up a
new document that describes why URP ended up the way it did.
The working group members that that this was a good idea, and
Patrick OKed it. Chairs to revise the charter and send to list.
^^^^^

There is no need to revise the charter in order to submit an
ID explaining issues under discussion and following up on
that would be far more useful than Steve's statement below
that "it must mean something else".

The subject did keep coming up in the previous year, has
continued to keep coming up in the year since and should
now be settled through the IETF process of open and fair
technical discussion.

Alison posted a valuable "Contribution to Profiles Document
(Consistency Discussion)" which does explain some of the
consequences of the URP approach to multi-master replication
and should be included together with the explanation of why
URP ended up the way it did.

http://www.imc.org/ietf-ldup/mail-archive/msg00548.html

The Word version with properly formatted tables is at:

http://www.imc.org/ietf-ldup/mail-archive/doc00000.doc

It was never discussed and should be discussed now.

(Remainder below is the originals Ed was responding to).

Steven,

Regards,
Tim Hahn

        To:     "'Richard V Huber'" <[email-masked]>,
<[email-masked]>
        cc:     Ellen Stokes/Tivoli Systems@Tivoli Systems,
<[email-masked]>,
<[email-masked]>
        Subject:        RE: New LDUP requirements draft

Rick, et al,

Regards,
Steven

=================
Ed Reed
Reed-Matthews, Inc.
+1 801 796 7065

---

From: "Steven Legg" <[email-masked]>
Date: Thu, 29 Mar 2001 17:47:24 +1000

Ed,

> state-based replication schemes.

I thought about this today and I think I've found a relatively painless
way to add atomicity information and conflict detection to LDUP that is
friendly to state-based implementations.

The conflict detection scheme I'm about to describe relies on comparing
the before and after states of entries being updated. Updates on a single
master will produce a neat sequence where the after state of one update
matches the before state of the next update in the sequence. In the
multimaster case, there will be some updates that share the same before
state and some updates whose before states reflect different incomplete
sequences of updates. These are the updates in conflict.

The before state of an update is described by a start vector, which is
a set of CSNs that is formed by looking at the CSNs on the contents of
the entry being modified. The highest CSN for each replica ID is retained
in the start vector. I started out by just copying the current update
vector but this approach produces more false positive indications of
conflicts.

The after state of an update is described by an end vector that is
formed in the same way as the start vector, except it looks at the
entry after the update has been performed.

I'll collectively refer to start and end vectors as state vectors.
A state vector SV1 "covers" another state vector SV2 if the CSN in
SV1 for each replica ID is greater than or equal to the CSN for the
same replica ID in SV2.

The start vector tells us what updates have been applied prior to
the update of interest, i.e. the previous updates that are "seen".
Two updates are in conflict if neither of them completely sees the
after state of the other. More precisely, two updates U1 and U2 are
not in conflict if and only if the start vector for U1 covers the end
vector for U2 or the start vector for U2 covers the end vector for U1.
If the start vector for U2 covers the end vector for U1 then U2 "sees"
the entry after U1 has been performed, and therefore logically follows
U1 and there is no conflict. Similarly for the reverse case.

In the simplest cases, two updates are in conflict if they modify the
same entry "simultaneously" at different replicas, without regard to
what they are actually doing to the entry. Consequently, some of the
detected conflicting updates might actually turn out to be independent
changes to the same entry.

Time for an example of conflict detection. Let's suppose there are two
replicas R1 and R2, where everything is in a quiescent state. A state
vector would actually use CSNs but it is sufficient for this example to
just use the timestamp component. I'll represent a state vector as a
tuple (x, y) where x is a timestamp (CSN) generated by R1 and y is a
timestamp (CSN) generated by R2.

At time t0, the state vector for the entry E is (t0,t0) at both replicas.
Update U1 on entry E is performed at R1 at time t1. Thus the start vector
for U1 is (t0,t0) and the end vector is (t1,t0). Simultaneously,
update U2 is performed at R2. The start vector for U2 is also (t0,t0)
and the end vector is (t0,t1). At time t2, U1 is propagated to R2. The
effects of U1 and U2 are merged as described by URP giving a new state
vector for E of (t1,t1). Update U3 on entry E is performed at R1 at
time t3. The start vector for U3 is (t1,t0) and the end vector is (t3,t0).
Update U4 on entry E is performed at R2 at time t3. The start vector for
U4 is (t1,t1) and the end vector is (t1,t3).

I'll summarize the start and end vectors to make this easier.

    start      end
U1: (t0,t0) -> (t1,t0)
U2: (t0,t0) -> (t0,t1)
U3: (t1,t0) -> (t3,t0)
U4: (t1,t1) -> (t1,t3)

Using the conflict detection rule above we come up with the following
conflicts:

U1 conflicts with U2.
U2 conflicts with U1 and U3.
U3 conflicts with U2 and U4.
U4 conflicts with U3.

Of particular note, U4 does not conflict with U1 or U2. It sees the
merged output of these conflicting updates but that doesn't make it
"conflicted" itself. We have to draw a line somewhere.

To detect conflicts we need to propagate the start and end vectors of
an update in the protocol, along with the UUID of the relevant entry.
The end vector is just the start vector with the CSN for the
originating replica replaced by the CSN for the update, so we can
condense this to a single CSN, which also serves to uniquely identify
the update. The start vector is a set of CSNs, like an update vector, but
generally shorter since not all replicas will be represented by CSNs
on the entry contents (because they've never made a change to the entry,
or the CSNs on their changes have long since been purged, or these CSNs
are now old enough to be purged).

The CSN on the conflict detection information can be used in the same
way as the CSN on a replication primitive to decide when the information
needs to be propagated. Because the conflict detection information and
the replication primitives for a specific update have the same CSN
they will necessarily propagate around together. State-based
implementations can still propagate only the net state change,
i.e. they can omit superseded replication primitives, because no
information from the primitives is being used to detect conflicts.

The above provides enough information for any replica to detect every
conflict. Given M replicas originating an average of N updates,
that's roughly (M by N) squared comparisons. If we leave it up to the
originating replica to test only for conflicts against its own updates
the number of comparisons can be reduced to N squared by M.

The scheme extends easily to accommodate grouped operations. All the
replication primitives generated from the one set of grouped operations
really need to have the same CSN (ignoring the least significant
modification number component) so one CSN is still enough for the end
vector. The start vector is generated by considering all the entries
targeted by the grouped operations, instead of just one entry.

Transactions can be similarly accommodated, though if searches are
part of the transaction we should drop the UUID and test the vectors
against updates for all entries when looking for conflicts.

We can also tighten up the conflict detection by adding to the conflict
detection information, lists of the attribute types the update reads
and writes. If the read and write sets of two updates are mutually
disjoint they can't be in conflict even if they modify the same entry
at the same time

Comments anyone ?

Regards,
Steven

---

From: "Albert Langer" <[email-masked]>
Date: Fri, 30 Mar 2001 08:19:58 +1000

In response to Steve's request for comments:

1) The fact that Steve is now looking for a way to meet requirements is
a major step forward, which I welcome. By offering his new idea he
has at least confirmed that URP 03 currently lacks a "way to add
atomicity information and conflict detection".

2) I have read the material below several times but do not understand it.

3) That is not surprising as it states clearly that Steve "thought about
this today" (although the relevant requirements for "atomicity information
and conflict detection" were present since 04 in September 2000 after a
room consensus on that in June 2000).

4) Steve should now write an initial I-D giving a clear explanation of
his new idea so that the WG can discuss it properly. Then
a formal discussion should be opened, managed and concluded. We
should not attempt to do that while it is in it's present form as
it is clearly just initial thoughts about a new idea on the same day
that the idea was thought of.

5) I was given 1 week to produce such an initial I-D when bringing up
an alternative proposal a year ago. That was not unreasonable as it
was then understood that the WG had settled on Steve and Alison's
proposal after working for a year. It is now a year later and it is
clear that the WG has not in fact even reached real consensus on
requirements. So Steve should be given more time to do a presentable
draft. He should also first do the draft explaining "why URP ended
up the way it did" that he committed to a year ago.

6) I did a "necessarily half baked" proposal (MDCR) a year ago as
required and it has still not been properly discussed, so I have let
it expire. I am posting that to the WG list in my next message.

7) A facilitator should be appointed to conduct the necessary
discussions in the list, insist on questions and arguments being
answered, sum up issues outstanding etc etc, so that we actually
converge on a decision rather than just exchanging and ignoring
various "points".

BTW for some insight into design issues, consider the problems of conflict
resolution within LDUP WG itself in the absence of a functioning
conflict resolution mechanism and accurate propagation of knowledge
of what the current state actually is. The inevitable result has
been periodic announcements that documents are "ready" when they
are not, without actual progress towards getting them ready
and much time lost ;-)

8) My preliminary view of what I can understand of Steve's idea is
that it still appears to be based on a fundamental misconception
that there exists some inherent total ordering of conflicting
updates to an entry which can be approximated in some way by
timestamps.

In reality multi-master conflicts form a tree which is only
partially ordered.

I do not think it is *possible* to "add in" atomicity information
and conflict detection as an afterthought to a replication scheme
that was not designed for it from the ground up. Conflict detection
is after all a necessary precondition for conflict resolution, which
is the part of the architecture that URP was supposed to have been
providing. Alarm bells should have gone off when it was renamed to
"update reconciliation". I will nevertheless study Steve's
proposal carefully when he presents it.

Meanwhile, here's some points to think about.

Once an initial version of an entry last changed at R0 has split into two
versions R0.R1 and R0.R2 due to concurrent changes at different replicas R1
and R2, it can, and therefore will, sometimes split into further versions
eg R0.R1.R3 and R0.R2.R4 as a result of both those versions being visible
and available for DUAs to make further changes to until the conflict is
resolved. Depending on replication links and schedules the original
"stable" version R0 and the first two variations R0.R1 and R0.R2 may also
all be visible at some replica at once.

Each variation can be named by
the series of replica Ids at which the change was made, starting from
the original stable version. As shown in MDCR it is not necessary to
store the entire path name, as the "version" number or depth in the
tree, plus the previous and current replica Ids of the originator DSAs
for the two most recent changes is sufficient in the report propagation
protocol to maintain the links between conflicting versions in the tree.
This only requires storing the previous replica Id and version
number in the visible entry at each replica.

But it is not possible to serialize operations without some means
of maintaining the tree and it is not possible to maintain
information about atomic operations or detect conflicts between
them without a means for serializing the operations.

I see no recognition of that in Steve's material below.

Any partially ordered tree can be embedded in
a total ordering, but a total ordering based on timestamps would
simply be arbitrary. The problem to be solved is how to deal with
the fact that each replica only has an incomplete knowledge of
both the actual state of the tree and of the similar knowledge
possessed by other replicas while the conflict remains unresolved.

For atomicity and eventual convergence, the algorithm must result in
each replica only making visible entries that represent the result of
a serializable sequence of successful operations that have actually been
performed by DUAs and must *not* make visible "transient states" arising
from internal processing by the DSAs.

Otherwise access control and other decisions would be based on those
transient states intended by nobody and not on the intended policies.

The unavoidable "loose consistency" inevitably results in changes
that will ultimately not be converged to being initially reported
as having been successfully made, and therefore results in further
changes based on those changes sometimes being made. But it must
never result in entry state that is not the result of a serializable
sequence of changes made by some DUAs becoming visible at any DSA and
it must be capable of generating notificatins when a DUA has been
told that it's change was accepted but the change is eventually
suppressed due to conflicts.

A necessary precondition is that all replicas must eventually
receive the same set of reports about all the conflicting changes.
This precludes a design where changes are merged while being
transitively replicated and only the merged changes based on
incomplete knowledge of the conflict reported to other
replicas. A separate report propagation layer is essential,
as required by sound architectural principles anyway.

Since multi-master is inherently unsuitable for any situation
with a high rate of concurrent changes there is no significant
increase in bandwidth as a result of forwarding all changes
to all replicas. Not doing so "saves" transmission of precisely
the information needed for conflict detection by discarding it
on the way with different information discarded at different
replicas along each path.

For all replicas to eventually converge on the same visible
entries they must all eventually select the same sequence. Therefore
they must all keep track of the state of the entire tree while the
conflict is being resolved. That is not a burden on implementations
as the tree pointers only need about 12 bytes of RAM for each version
until the conflict is resolved. Most of the conflict trees are trivial
since multi-master is unsuitable for situations with a high rate of
concurrent changes anyway. Using a total ordering based on 32 bit
timestamps would just save about 8 bytes of RAM per unresolved
conflicting change, at the expense of correct serialization of
changes and therefore of any hope of maintaining atomicity
information and detecting conflicts. 64 bit timestamps
would only save 4 bytes of RAM.

Version numbers are needed for correct serialization as recognized
in all research on distributed concurrent changes. They also
simplify and compress report propagation and tree storage by
making it unnecessary to transmit and store the full path names
of the variations or do complex calculations, let alone the
O3 comparisons mentioned by Steve below.

Detecting atomicity conflicts requires that all replicas receive reports
of all changes, update their trees based on their current knowledge of
conflicting changes, make entries visible based on a common algorithm
for selecting a serialized sequence and do not purge the information
they need until they know that other replicas have already seen
and rejected anything that could be a basis for future changes
that might be accepted.

I am unable to detect any trace of these fundamental principles
in the material below.

Maintaining distributed ACID transactions is of course much harder,
but I would recommend studying some of the concepts involved in
the serialization graphs for a replicated data history in a text
on that subject before embarking on protocol design for the
simpler problem LDUP has to deal with. One needs to understand
what serializability graphs and replicated data histories are,
in order to design procedures for detecting atomicity conflicts.

See for example chapter 8 at:

http://research.microsoft.com/pubs/ccontrol/

The Coda papers recommended a year ago are of course a better
introduction for the simpler problems in directory replication
(as are the Bayou materials referenced there).
http://www.cs.cmu.edu/afs/cs/project/coda/Web/docs-coda.html 

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of Steven Legg
Sent: Thursday, March 29, 2001 5:47 PM
To: 'Ed Reed'
Cc: [email-masked]
Subject: Conflict Detection within the Current Architecture, was RE: New
LDUP requirements draft

Ed,

    start      end
U1: (t0,t0) -> (t1,t0)
U2: (t0,t0) -> (t0,t1)
U3: (t1,t0) -> (t3,t0)
U4: (t1,t1) -> (t1,t3)

U1 conflicts with U2.

Comments anyone ?

Regards,
Steven

---

From: "Albert Langer" <[email-masked]>
Date: Fri, 30 Mar 2001 08:19:58 +1000

-----Original Message-----

Ed,

    start      end
U1: (t0,t0) -> (t1,t0)
U2: (t0,t0) -> (t0,t1)
U3: (t1,t0) -> (t3,t0)
U4: (t1,t1) -> (t1,t3)

U1 conflicts with U2.

Comments anyone ?

Regards,
Steven

---

From: "Steven Legg" <[email-masked]>
Date: Fri, 30 Mar 2001 15:16:01 +1000

Albert,

> atomicity information and conflict detection".

Just reading URP makes it clear that it says nothing about conflict
detection. Conflict detection has always been considered outside the
scope for that document, so it lacks nothing it was supposed to have.

> 2) I have read the material below several times but do not 

At what point did I lose you ?

> room consensus on that in June 2000).

I wasn't aware of a requirement to satisfy all requirements immediately
upon them becoming known. In any case, I spent a few hours having a
preliminary look at a solution on August 14, 2000, which was enough to
give me confidence that a suitable mechanism could be added to the
current architecture. Ed's email and the discussion about requirement
P7 prompted me to have a closer look. The solution turned out to be
easier than I expected.

> In reality multi-master conflicts form a tree which is only

In reality, the working group has decided that none of the updates in
conflict are going to be rejected. The end states of the updates
in conflict are to be merged instead. This means that conflicts have
to be modelled as a directed acyclic graph instead of a tree. I liken
it to a braided stream, where streamlets constantly split and merge.

> that was not designed for it from the ground up.

Strange. I thought I just did.

Regards,
Steven