Subject: RE: WG Last Call on the LDAPv3 Directory Replication I-D

From: "Albert Langer" <[email-masked]>
Date: Tue, 20 Feb 2001 07:51:55 +1100

[Patrik]
I have seen discussions on this mailing list, and on some IETF
meetings, going around in circles regarding multimaster replication
where the wg chair(s) together with other wg participants have tried
to tell you that the model you propose is not what the wg is doing.
The discussion basically started (as far I can recollect) with your
submission of draft-langer-ldup-mdcr-00.txt in april 2000.

Do _you_ have any suggestion on how the wg can get some more progress?

[Albert] That draft expired long ago and I have not renewed it
because no interest was shown in it.

I do have several suggestions as to how the WG can get more progress.
They are in no way related to my MDCR draft.

I intend to make them when the WG chairs place the question
of revising the charter properly before the WG. I explained that
clearly in response to the proposed accelerated revision submitted
by the WG chairs:

***
[John and Chris revision]
Hi LDUPers,

below is a revised charter for our workgroup. Chris and I
need your comments asap, so that we can present our new
charter to our AD. Please especially note the new dates for
our delierables. I'd like this review closed as soon as
possible. If anyone objects to review ending next Friday 19
January, please object soon.

regards,
John and Chris

[Albert]
This was dated 13 January and received here on 14 January.

In my view charter revision should be taken as an opportunity
to formally review the progress and direction of the WG and
should therefore not be pushed through casually with less
time for comment than a WG final call.

[...]
[Albert]
Propos[al] to finalize the Update Reconciliation Procedures
four months [actually 3 -AL] prior to finalizing the Information Model and
Architecture
lacks common sense.

[revision]
Dec 01 Reevaluate Charter and Milestones

[Albert]
If nobody else thinks there should be an earlier reevaluation of the
progress so far in the light of earlier milestones, fine. But WG
members should be explicitly asked to reflect on this rather [than] treating
a consistent inability to achieve milestones as grounds for accelerating
the process by which new milestones are adopted, especially when the
proposed means to achieve new milestones is [..] for RFCs on detailed
implementation to be settled before Information Model and Architecture.

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

I am still waiting for the WG chairs to ask the question. It may well be
that
nobody else other than me (and perhaps you) does think some review of
progress is
desirable now, in which case it would be disruptive to simply proceed to
introduce a new agenda item that has not been agreed on.

We won't know whether the WG wants to discuss how to get more progress until
the WG chairs do ask the question, or delay doing so for unreasonably long,
- which is not the case yet, as I posted that request in mid-January which
is
often a vacation period and one of the WG co-chairs is (now) known to
be currently on vacation. I do however insist that they must ask the
question,
and have made that clear by promptly objecting to the unauthorized posting
of a
revised WG charter as soon as I noticed it.

If you want a "sneak preview" I believe that the fundamental problems are:

1) Natural consequence of having attempted to work through detailed protocol
issues before finalizing requirements, architecture and information model.

That *always* results in lack of progress and I see nothing surprising about
it
having happened here. What is surprising is the grim determination with
which
those who made that mistake two years ago refuse to learn from it.

2) Exacerbated by the failure of the WG chairs to actively participate in
technical discussions on the list and guide them towards resolution rather
than
aimless meandering. I have seen competent and useful summaries of
discussions at
IETF meetings in the minutes they have circulated, which provide a regular
quarterly survey of the (lack of) progress. But they do nothing
to ever pose issues for resolution, ask for clarification, attempt to
restate
different viewpoints etc etc in mailing list discussions as opposed to IETF
meetings,
although the mailing list is ultimately where the WG has to conduct its
business.

Consequently there is no sense of a discussion having actually "got
anywhere" and
people just view the passing parade of LDUP messages and assorted spam
traversing their
mailboxes as a sort of "spectacle" rather than an actual standards
development
process which they can contribute to bringing to fruition.

Although you refer to:

"(b) The number of issues which the wg chair have declared being
consensus in the wg -- and you still bring up the issues"

the real problem is opposite - the complete failure to actually put any
issues for
decision in the mailing list and then declare the question resolved.

If you believe your impression is accurate, please simply cite URLs from the
archives showing conclusions of discussions that have been announced as
consensus decisions
by the WG chairs followed by further discussion from me. Here are some
examples
of "action" items as far back as from the minutes of the August 2000 IETF:

***
3. Change reports - Use ProtocolOps or Primitives

Action: no consensus, need further discussion on the list.
It was note that we need to include how each addresses (or
doesn't address) atomicity.

4. Eventual convergence - Version numbers or timestamps

Action: looks like a religious argument; no consensus
reached.

5. Oscillation

The claim has been made that MDCR oscillates. Everyone
agrees that oscillation is bad. Needs more discussion on the
list.
***

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

All of these are explicit minuted recognition that various issues I have
raised have not reached consensus and should be discussed further on
the list. Now show me where the WG chairs have:

a) Opened the discussion
b) Led it to a conclusion
c) Announced the result

Your "plan" was that IETF meeting would simply adopt the "consensus" which
Chris
was thumping his chest about in email "then close the box by approving the
minutes".

If you believe that plan was successfully executed and are now trying to
carry through
your commitment "I will see, as AD, that the box will close, and stay
closed",
then you are simply hallucinating.

It was Chris who said:

***
1) I've read it CAREFULLY and believe that its ready.
2) My co-chair has read it CAREFULLY and believes that its ready.
3) Active members of the Working Group who represent a majority of
the most prevalent players in the LDAP industry have read it CAREFULLY,
many, many times and believe that its ready.
[...]
I can assure you that there is absolutely no chance I will ever agree
with you about whether or not the document is ready for IETF Last Call.
[...]
***

That was not a declaration of consensus by a WG chair but a personal
opinion by Chris. I wasn't at the IETF meeting so don't blame
me for him having got the actual situation so spectacularly wrong.

As for going around in circles on (atomicity) in multi-master that is really
the same problem. From time to time somebody says something, someone else
responds and so it goes. The WG chairs simply do not attempt to state
clear questions for resolution to the mailing list and have them resolved.

For my part I concluded long ago that further argument on atomicity would be
pointless within the WG and that the technical mistake I believe is being
made will ultimately have to be resolved elsewhere:

***
2. My objection to non-atomicity still stands for final call but I'm
assuming there is little point arguing about it further within LDUP unless
others want to take it up. The draft now at least makes it possible to have
serious discussion about the issue in IETF review and does include several
requirements which cannot in fact be met without atomicity, such as accurate
replication of access controls and attributes such as "modifiers name".
although I disagree with much of the analysis in appendix B.5 and also the
continued misunderstanding of applications for multi-master replication in
appendix A on usage scenarios. There are still some inadequacies in
presentation of the issue but the fundamental question is now simply whether
or not atomicity should be a requirement rather than whether a document that
shows no comprehension of the issue at all should be presented to the IETF
at all. I still believe a fundamental technical mistake is being made on
that question. I also still believe the requirements draft should be
actively seeking input from directory users on the impact of non-atomicity.

***
That was 20 October 2000.

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

***
I assume the absence of
expressed opposition from others, and the report of discussions at the last
LDUP meeting at IETF, does reflect a "rough consensus" within the WG against
"atomicity" etc. My understanding is that my continuing belief that this is
a fundamental technical mistake should therefore be expressed as opposition
to LDUP's final position rather than delaying LDUP from publishing that as
it's final position. The WG has had an adequate opportunity to change it's
position.
***
http://www.imc.org/ietf-ldup/mail-archive/msg00734.html

That was in response to Rick's request for a final call on 14 November:
http://www.imc.org/ietf-ldup/mail-archive/msg00733.html

It led to Rick apparantly wanting to pursue some further discussion on it:
http://www.imc.org/ietf-ldup/mail-archive/msg00736.html

Which was promptly squelched by chest thumping from Chris:
http://www.imc.org/ietf-ldup/mail-archive/msg00738.html

Needless to say, Chris did not keep his commitment to prepare some comments
on the
atomicity and access control issue (it would I believe have been his *first*
technical contribution to the list in the entire period I have been
participating).
Nor did he issue any final call as requested by the authors of the draft.
You can
hardly blame me for it *still* not being resolved, when I explicitly said
that I thought a consensus (which I disagreed with) existed, and that my
opposition
should not be grounds for further delay publishing the WG's position.

Unless of course you think the reluctance to actually finalize the matter
and get
on with it is due to knowing that there are no technical arguments available
to
defend the position in IETF final call and that therefore it is my fault
because
I have made it clear that it will be necessary to do so. My understanding is
that
posturing about how many people agree with you and how often they have said
so is
no substitute for technical argument in the IETF. If my technical arguments
are
rejected by the IETF that will be the end of it. So far no decision has been
taken
by LDUP WG, let alone the IETF.

Instead of acceeding to Rick's request for final call last millenium,
supported by me,
this little gem appeared in the draft minutes of the San Diego IETF LDUP
meeting:

***
  3. Atomicity issues.

RESPONSE: Albert wants all changes from a server to be
handled in an atomic fashion. This was basically the
same position as was argued in the last session
(please refer to the last minutes on this subject).
This requirement seems unreasonable. The obvious
counter-example is when multiple servers each write to
one or more attributes of the same entry. In a single-
master situation, one would hope that you would end up
with the cumulative changes, and there is no reason to
have a multi-master system not exhibit that same
behavior.

[...]

The room consensus was to keep the draft as is.
***

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

I'm seriously thinking of buying a printed copy of the formal
proceedings just so that I can have that laminated as a memento
that an entire room full of people at an IETF meeting actually
did endorse such patent nonsense.

(BTW there are still no final minutes from LDUP in the proceedings)

Reasonable people with an expert knowledge of LDAP can reasonably disagree
about what trade offs should be made concerning atomicity and other design
constraints in a multi-master context.

But there is absolutely no point discussing technical questions about
atomicity
in a WG where an entire roomful of people can be found *all* of whom agreed
with this "obvious counter example". They simply do not understand what the
issue is about and are therefore not qualified to take the final decision on
it.

They may have expert knowledge of LDAP and many other things, but they are
simply not qualified to be tackling issues concerning concurrent updates in
multi-master replication.

Nevertheless, when a final call is issued, with the words "silence is
consent", WG members have a responsibility to state their position before
taking
the issue elsewhere.

My position is that the whole point of the requirement for atomicity spelt
out in the specifications of the LDAP modify operation is precisely
to prevent cumulative changes from conflicting writes which could otherwise
occur even on a single server due to changes being made by other DUAs after
a
read and before a write. That is essential for applications that require
data integrity, which of course includes access control applications.

Without high integrity access control, interoperability is impossible.

If you have a WG chaired by someone who actually thinks accumulation of
changes
from conflicting writes is *desirable* and it is "unreasonable" to try and
prevent it, and nobody in the room can correct the mistake, then that WG is
simply not qualified to take the final decision.

Basically the WG is going around in circles on numerous issues concerning
multi-master replication because it simply does not have the technical
expertize to be tackling a project as difficult as multi-master replication
of directory services. Incidentally, if you check the archives, you will
find
that several people who do were actively involved in the WG when it was
first chartered but dropped out long before I joined.

I repeat my suggestion that in establishing liason with the ITU, the WG
should
study *why* they dropped the URP proposal as a work item. It was after all
introduced and originally accepted here as a joint project.

When the WG *does* take a decision it can be reviewed. Until then it can't
be.
Presumably a decision will *have* to be taken when either architecture or
URP
goes through final call. The responsibility for not having taken a decision
and moved on lies entirely with the WG chairs. Accusing me of "working
against"
a decision that has not been taken is absurd.

Chris, John and you should damn well stop the sniping and get on with the
job.

It is *especially* absurd that you 3 are the ones engaging in the sniping
when
*none* of you have participated in the various arguments in which I have
sharply
disagreed with the views of other members of the WG. It is not unusual for
sharp technical disputes to spill over into flame wars which require
intervention
by either WG chairs or even Area Directors to restore a sense of
perspective.

What is unusual is for WG chairs and Area Directors to be inflaming things
when others are able to simply agree to disagree, and do so without chest
thumping, accusations of "unprofessional" comments or nonsensical claims
about "working against" decisions that haven't been taken.

---

From: "Albert Langer" <[email-masked]>
Date: Sat, 24 Feb 2001 07:24:36 +1100

<js>
Albert, if you're this convinced that URP does not meet the requirements
document, please elaborate now, rather than later, in a separate thread
(since this one is already so long). Thanks.
</js>

Ok, here goes. I'm also CCing to ADs as advance notice of issues that are
likely
to be raised formally in a request for review of LDUP WG decisions if they
continue
unresolved. It will soon be a year since they were first documented.

Further discussion may just be to the LDUP list and can be either followed
there
now or retrieved from the archives later. References marked U are to the
last
available URP version, draft-ietf-ldup-urp-03.txt, presently "expired".
Other
references are to the current architecture and requirements drafts (-05
and -06).

I have categorized in two dimensions for resolution and severity plus a
separate
category for "Requirements Problem".

Needless to say these categories, like everything else I write, reflect my
opinion.

Requirements Problem: - The requirement could not or should not be
implemented. This
				is not intended as a catalog of requirements issues, but only
				those of which it might be said that URP and related parts of
				the architecture has failed to conform, or that conformance
				to it provides an explanation for not conforming to another
				requirement. The requirement should	be changed or removed,
				not the specification.

Severity:

Show Stopper - Prevents achieving fundamental LDUP goals.

Non-compliance - Somebody (else) might argue that the requirement should be
changed or
			removed to accommodate the proposed specification.

Resolution:

Fatal - Meeting the requirement would need a fundamentally different design
approach from that
		adopted by URP and the architecture. A fix could include work derived from
the
		URP related work (eg for resolving create and rename conflicts), but would
		negate the core of the current design. These relate to the use
		of attribute value granularity replication in a directory service where
the
		granularity of operations is at the level of entries and the consequent
loss
		of atomicity information and loss of directory information without any
means
		for even manual recovery.

Fixable - Changes to URP and architecture within the current framework could
meet the
		requirement. These mainly relate to the change report propagation
mechanism
		which can be separated from the core aspects of URP and fixed without
		affecting the integrity of the core design.

Some items have been placed in more than one category due to different
consequences
of the requirement. This is also implicitly a requirements issue as
requirements could
be separated to avoid that.

The URP issues are generally a result of URP complying with the architecture
as
specified (although I gather those aspects of the architecture are largely a
description of URP). Therefore they are also architecture issues. I have not
generally
considered issues arising only out of the specific text of URP and am
strongly opposed to
a final call on that text until an architecture has been agreed on. (BTW one
that should be
easily fixed for any future draft is removal of all references to X.500 DAP
and DSP as
IETF has no authority over such work and URP was dropped as a work item by
those who do,
perhaps due to the "Fatal" problems. A follow up on the liaison with ITU
specified
by the WG charter should be done before further consideration of URP).

Some issues involve the *absence* of something in the architecture.
Resolution
might well involve a separate document from the specifications for conflict
resolution. The assertion in these cases is that the design of URP could not
integrate with such a
specification, not that the specification should have been included within
the text
of URP when it is not even mentioned in the architecture.

* A) Fatal Show Stoppers *

1) Atomicity and information loss

First, some background definitions from the requirements draft.

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.

Requirements:

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.

The apparant intention is not to require that replication
produce the same results as atomic operations, but to ensure that
the information necessary for administrators to manually fix any
problems that may result from not doing so is propagated, stored
and notified.

If an attribute value that would not have been deleted by an atomic
operation is in fact deleted as a result of multi-master replication
procedures, that clearly constitutes "loss of directory information",
and information about that loss must be propagated, stored and notified
to administrators so that they can fix any resulting problems. Likewise
if information about which user is responsible for modifying an entry
is lost.

To understand that there are indeed problems, which an administrator
would need to fix, consider the following example, a slightly modified
version of the example given in B.5.3 of the requirements draft and now
in 4.3.3.1 of the new profile draft: draft-ietf-ldup-usage-profile-00.txt.

Here is the original example:

***
There is an entry with distinguished name DN that contains attributes
X, Y, and Z.  The value of X is 1.  On replica A, a ModifyRequest is
processed which includes modifications to change that value of X from 1
to 0 and to set the value of Y to "USER1".  At the same time, replica B
process[es] a ModifyRequest which includes modifications to change the
value of X from 1 to 0 and to set the value of Y to "USER2" and the
value of Z to 42. The application in this case is using X as a lock
and is depending on the atomic nature of ModifyRequests to provide
mutual exclusion for lock access.

In the single-server case, the two operations would have occurred
sequentially.  Since a ModifyRequest is atomic, the entire first
operation would succeed.  The second ModifyRequest would fail, since
the value of X would be 0 when it was attempted, and the modification
changing X from 1 to 0 would thus fail.  The atomicity rule would cause
all other modifications in the ModifyRequest to fail as well.

In the multi-master case, it is inevitable that at least some of the
changes will be reversed despite the use of the lock.  Assuming the
changes from A have priority per the conflict resolution algorithm, the
value of X should be 0 and the value of Y should be "USER1" The
interesting question is the value of Z at the end of the replication
cycle.  If it is 42, the atomicity constraint on the change from B has
been violated.  But for it to revert to its previous value, grouping
information must be retained and it is not clear when that information
can be safely discarded.  Thus, requirement G6 may be violated.
***

Here is the modified version:

There is an entry with distinguished name DN that contains an attribute
L, with 3 values X, Y, and Z that was last modified by User C.

User A issues a ModifyRequest which includes modifications
to change that attribute from X, Y, Z to Y, Z without regard to any
other values (leaving them "as is").

Using LDIF notation (RFC 2849):

dn: DN
changetype: modify
delete: L
L: X
L: Y
L: Z
-
add: L
L: Y
L: Z
-
replace: modifiersName
modifiersName: A

At around the same time, user B issues a ModifyRequest which includes
modifications to change the attribute L from X, Y, Z to X, Y again
leaving any other values "as is".

dn: DN
changetype: modify
delete: L
L: X
L: Y
L: Z
-
add: L
L: X
L: Y
-
replace: modifiersName
modifiersName: B

Both operations are relying on the published standards to ensure that
"what you read is what you changed". If some other user had removed
any of X, Y or Z between the read and write in either case, those
published standards guarantee that the entry will not be changed to delete
X or to delete Z respectively. Presumably the changes are designed to
ensure that Y is associated with either X or Z and does not stand alone
regardless of any race condition.

If user A's change is processed first, the result will be Y, Z and
the change by user B will fail because of the absence of X, which
user B had assumed was present when making the change.

If user B's change is processed first, the result will be X, Y and the
change by user A will fail because of the absence of Z, which user A
had assumed was present when making the change.

Either way, one of the users will achieve exactly what they intended,
the name of that user will be listed as modifiersName and the other
user will be safeguarded from achieving a result not intended.

With the pre-LDUP use of changelog single master replication, and with
the initial installation of LDUP compliant servers in single master
mode, for a trial run, everything works as before. But one day a
sysadmin turns on multi-master and strange things start to happen.

If user A and user B happen to make the changes on the same server,
everything works as before. But sometimes they make the changes on
different servers (and are unlikely to know this since LDAP is
designed to hide which server is being accessed from applications).
So sometimes the result is quite different. According to URP a
"primitive" to delete X will be replicated with a CSN larger than
any existing CSN for X at any replica (and no primitive to add
X will be replicated since the only change in state from either
of the modify operations did not cause X to be added). Likewise
for Z. So both will eventually be deleted at all replicas (with
all sorts of possible transient conditions).

Regardless of which change is processed first, the final result will
be Y and both X and Z will have been deleted. However you look at it,
directory information has been lost that would not have been lost
if LDUP was not used, or if exactly the same operations had been
performed at exactly the same times on a single multi-master server.

Responsibility will be arbitrarily assigned to either A or B as
modifiersName although neither made the change that actually
occurred.

No conflict will be notified to an administrator because as far as
URP is concerned, no conflict occurred and no conflict resolution
procedure was invoked.

No atomicity information will be propagated because as far as URP
is concerned, the only state changed by either modify operation
was the deletion of X or Z, so no other primitives were ever
generated and there is no information about the other aspects
of this "atomic" operation to replicate. The core design principle
of URP is not to treat modify operations as an atomic unit but split
them into sub-atomic "primitives", precisely so that each can
succeed or fail independently of the others and thus avoid any need for
"conflict resolution" and replace it by "update reconciliation".

As specified in U4.3:

   The p-add-attribute-value(uid, csn, type, value) primitive is used to
   describe the addition of a single attribute value to an entry.  The
   type argument contains the attribute type of the value and the value
   argument contains the attribute value.

   The p-remove-attribute-value(uid, csn, type, value) primitive is used
   to describe the removal of a single attribute value from an entry.
   The type argument contains the attribute type of the value and the
   value argument contains the attribute value.

   [...]

   These primitives reflect the intended *final* state of an update
   operation rather than the *specific* changes required to achieve that
   state. [emphasis added]

The architecture draft purports to support the requirements by the
following text:

***
10.3 Replication Update Generation

The Supplier generates a sequence of Replication Updates to
be sent to the consumer. To enforce LDAP Constraint 20.1.6,
that the LDAP Modify must be applied atomically, each
Replication Update must contain the entire sequence of
Update Primitives for all the LDAP Operations for which the
Replication Update contains Update Primitives. Stated less
formally, for each primitive the update contains, it must
also contain all the other primitives that came from the
same operation.

[...]

10.4 Replication Update Consumption

A Consumer will receive Replication Updates, extract the
sequence of Update Primitives, and must apply them to the
DIB in the order provided. LDAP Constraint 20.1.6 states
that the modifications within an LDAP Modify operation must
be applied in the sequence provided.

Those Update Primitives must be reconciled with the current
replica contents and any previously received updates.  In
short, updates are compared to the state information
associated with the item being operated on. If the change
has a more recent CSN, then it is applied to the directory
contents. If the change has an older CSN it is no longer
relevant and its change must not be effected.

If the consumer acts as a supplier to other replicas then
the updates are retained for forwarding.
***

The above text conveys the impression that atomicity
information is propagated. Any casual reader would draw that
conclusion.

Looking closely at the fine print it turns out that these "Update
Primitives" which are religiously applied in the same sequence,
are not the sequence of modify add, delete and replace components
from the original LDAP ModifyRequest operation as would be
necessary to propagate the atomicity information specified by 4.6
of RFC 2251.

Instead, 10.3.2 specifies that:

Each *state* change (entry, attribute, or value - creation,
deletion, or update) is mapped onto the equivalent Update
Primitive. [emphasis added]

The URP introduction elaborates as follows:

U3 "Each DAP, LDAP or DSP operation successfully performed by a directory
   server is subsequently reported to other directory servers with which
   it has a replication agreement as a set of one or more simple
   timestamped replication primitives.  These primitives reflect the
   intended *final* state of an update operation rather than the *specific*
   changes required to achieve that state. [emphasis added]

The whole point of this is to split the original atomic operation into
"primitives" so that no part of it can affect the outcome of any other
part - ie so that it will cease to be atomic.

The core design of URP drops all atomicity information and therefore
cannot propagate it or notify any administrator about resulting loss
of directory information.

The entire elaborate exercise of carefully numbering the sequence of
modifications and applying them in order is *completely* pointless,
achieving
absolutely nothing apart from self-deception.

The whole point of applying the modifications in sequence as specified by
the LDAP standards is so that by deleting a value and then adding it, in
the same operation, one can guarantee that the operation will fail if that
value had been removed by some other DUA since the entry was read by the DUA
that intends to change some related value with another part of the same
modify operation. If the components of the modify were applied in the
opposite sequence the operation would fail, even if the value was still
present because an attempt would be made to add a value that was
already present. That and the converse is the only function it serves.

This ensures that applications requiring data integrity can
avoid a race condition in which some other DUA has made changes to the
entry by adding values that the DUA had specified were not there in it's
modify operation or deleting values that the DUA had specified were there.

It is of course impossible to immediately notify the DUA of the failure in a
multi-master context when the conflicting write occurs at another DSA. But
it is entirely possible to at least ensure that the final result is the
same outcome as would have occurred with single master, by converging to
the outcome of only one of the conflicting operations.

The requirements draft does not insist on that (although it should and in
any
case, conformance to the LDAP standards requires it). Neither does the draft
explicitly authorize or require the opposite. What it does do is just
require that it be possible for administrators to manually fix any problems
that may result. Instead of meeting that requirement, the text merely
conveys
a misleading impression that it does so.

2) Access Control

Requirements:

M4.  LDAP replication MUST encompass schema definitions, attribute
names and values, access control information, and name space
information.

AM6.  Access control information (ACI) associated with sensitive data
MUST be deleted after or simultaneously with the deletion of the
sensitive data.  Likewise, during Adds, ACI MUST be added first or
simultaneously with the addition of that data.

URP does not support the replication of access control at all as a direct
consequence of item 1, because access control requires data integrity. In
particular any attempt to ensure that ACI is added or deleted simultaneously
with associated sensitive data becomes impossible because the only mechanism
available for doing so has been broken.

Many similar problems also arise but detailed consideration is not
necessary since that alone is a Fatal Show Stopper.

Consider the example above with attribute L being ldapACI as
specified in draft-ietf-ldapext-acl-model-06.txt and X, Y, Z
as follows:

 dn: ou=policy, o=agalaxyfaraway
 ldapACI: subtree#deny:w#[all]#group:cn=marketing

 ldapACI: subtree#grant:w#[all]#group:cn=involved

 ldapACI: subtree#deny:w#[all]#role:cn=madhatter

Originally the entry was setup to allow anyone involved to write
policy, except for the madhatter.

Then a marketing group was setup for convenience in adding others who should
not have that permission, but the madhatter was not removed.

Eventually all except the madhatter were removed from the excluded group.

Then user A notices that the two entries X and Z are redundant
since the madhatter is now the only member of the marketing group.

A decides to cleanup by deleting X, the redundant deny entry for the
marketing group. A does this safely to ensure no possible
race condition.

Meanwhile user B also notices and decides to cleanup, but
makes the opposite decision, deleting Z, the redundant deny
entry for the madhatter who is a member of the marketing group anyway.
B also does it safely.

Result, intended by neither, is that the madhatter is allowed
to write policy.

---

From: Patrik Fältström <[email-masked]>
Date: Fri, 23 Feb 2001 14:02:00 -0800

At 07.24 +1100 01-02-24, Albert Langer wrote:
>now or retrieved from the archives later.

FYI, I am on the LDUP list, and get all email. And, yes, LDUP is 
mine, and not Ned's. I will forward things to Ned if that is needed.

If something is to be sent more formally to the AD, it should be sent 
to me and Ned -- both of us -- and addressed to us.

cc:ing is not needed.

   paf

-- 
Patrik Fältström <[email-masked]>       Internet Engineering Task Force
Area Director, Applications Area                   http://www.ietf.org
Phone: (Stockholm) +46-8-4494212            (San Jose) +1-408-525-8509
        PGP: 2DFC AAF6 16F0 F276 7843  2DC1 BC79 51D9 7D25 B8DC

---

From: "Ryan Moats" <[email-masked]>
Date: Sat, 24 Feb 2001 18:09:46 -0600

Since the following is a comment about the requirements draft, I'll
reply to it...

>any case, conformance to the LDAP standards requires it).

Where precisely does it do this?  I see the client needs to recive "notice
of the results of the LDAP protocol operation on the server contacted".
Any extention to cover changes from replication is architecturally identical
to what LCUP is trying to accomplish in terms of notifing clients of changes
to directory entries they are interested in.  Currently, this requires
maintaining open TCP connections to all clients, which has been shown in
other situations to not scale.

Further, a directory administrator may have an application that does not
require this behavior, and if so, why should the directory administrator
require it.  I think what we state in the requirements is reasonable: The
protocol must be able to carry atomicity info in the protocol (directory
administrators don't have to use it) and a directory administrator can
require notification of replication changes (a la LCUP) if they need it,
but that's the directory administrator's requirements, not the WG as a
whole.

>2) Access Control

The example you give for access control is merely a repeat of the first
point that you have.  I think an independent example would be better or
some folks inclination would be to think "ah, AC issues are just a
specialization of information loss issues".

Ryan

---

From: "Albert Langer" <[email-masked]>
Date: Mon, 26 Feb 2001 00:59:51 +1100

[Ryan] http://www.imc.org/ietf-ldup/mail-archive/msg00892.html
Since the following is a comment about the requirements draft, I'll
reply to it...

[Albert]
BTW, I have also removed Chris and John from CC list in light of Patrik's
request, as they can also be assumed to be subscribed.

I'm not sure whether we are at cross purposes here.

There is now a very clear definition in the requirements draft:

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

Once that has been adopted I would respond to anyone claiming that
there is no such guarantee in the LDAP standards by simply referring
them to what LDUP has formally agreed to as a "rough consensus".
I would hope that the WG chairs would insist that we move on and not
reopen the clearly settled question of whether the LDAP standards
do "guarantee" that all changes will be made or all changes will
fail. It will be much easier to move on once the WG actually
has adopted something.

So if, as an author of that draft you are asking me where "conformance
to the LDAP standards requires it" I would refer you to the same
place from which you drew the conclusion about the "guarantee".
(Presumably section 4.6 of RFC 2251).

Meanwhile, I have to assume you are in fact asking about proposals
for notifications concerning constraints that were not enforced
immediately but are subsequently discovered in the course of
conflict resolution, although that is not mentioned in the
paragraph you quoted and replied to.

The way I see it LDAP standards specify what can be written to the directory
so as to determine what can be read from it and thus enable globally
deployable
directory applications to work with any conformant server and any conformant
client using a standardized client server protocol. As part of that they
specify *both* what must be the outcome of an update write invoked by a
client
and what response and error messages must be returned to the client
immediately.

There is no provision for subsequent notifications to clients in the base
standards because the response returned immediately is entirely sufficient
in
a single server or a single master environment.

That environment necessarily provides only "loose consistency" in which
inconsistent
data may be read from different servers because even single master
replication does
not happen until *after* the response is returned to the client and even
single
servers use referrals to other servers in the distributed global directory,
with
no mechanisms for referential integrity.

Strict conformance to the LDAP standards requires conforming to *both*
aspects and
maintaining that "loose consistency" model.

Multi-master inherently *cannot* conform to the second aspect of notifying
clients
of the results immediately. That is an argument for keeping it
"experimental" as
Kurt suggested, until such time as operational experience has been acquired,
and the
impact on existing standards evaluated and any necessary revisions
undertaken.

Nevertheless, the WG has been explicitly chartered to develop multi-master
standards track RFCs as well as single master, so it is safe enough to
assume
that we have not been chartered to do the impossible and we would be
entitled
to get quite indignant at any work done here being rejected for not having
achieved the impossible. That certainly does not excuse us from meeting the
other aspect of the constraints by ensuring that eventual convergence is to
the same outcome as the existing data model - not an outcome with loops in
which
entries can be their own ancestors or mandatory attributes can have no
values
or entries can have no names or in which any other inconsistent operations
will corrupt the integrity of directory information. The only one of those
enforced by URP is loops.

Remember only inconsistent reads are an issue in single master.

Inconsistent update operations are the very essence of what multi-master
standards have to deal with. They are dealt with as regards create and
rename
conflicts, and must also be dealt with as regards other write operation
conflicts.

The architecture draft explains this quite adequately in section 3.7. I
propose
that text be moved to the requirements draft as there may be some ongoing
confusion
within the WG about it and it would certainly be a new concept to other
readers:

***
In the case of a single-server or single-mastered
Replication Context all LDAP Constraints are immediately
enforced at the single updateable replica. An error result
code is returned to an LDAP Client that presents an
operation that would violate the constraints.

In the case of a multi-mastered Replication Context not all
LDAP Constraints can be immediately enforced at the
updateable replica to which the LDAP Update Operation is
applied. This loosely consistent replication architecture
ensures that at each replica all constraints are imposed,
but as updates are replicated constraint violations arise
that cannot be reported to the appropriate client. Any
constraint violations that occur are repaired by a set of
update resolution procedures.

Any LDAP client that has been implemented to expect
immediate enforcement of all LDAP Constraints may not behave
as expected against a multi-mastered Replication Context.
***

That to me is a reasonable statement of what LDUP MUST do in order
to be acceptable as a standards track protocol consistent with
deploying multi-master servers in the same *global* environment
as those using existing standards. So how about putting it in
the requirements?

If, in addition to not being able to enforce the constraints
immediately, it is proposed not to enforce any *one* of them at all,
that should be stated equally explicitly in the requirements draft
and signoff should be obtained from others affected as to whether
that is acceptable before proceeding further.

Otherwise LDUP would not be consistent with the fundamental
data model of the LDAP standards as well as being inherently
unable to fully implement the operations model by not being
able to enforce the constraints of that data model immediately.

Certainly there should be no statement, either in the requiements
or the architecture that "any constraint violations that occur are
repaired by a set of update resolution procedures" unless that
statement is true.

One of those constraints, explicitly listed in the architecture
draft, but *not* implemented by URP, is atomicity of modifications
which is needed to support requirements for data integrity
in the fundamental data model. I am not part of any "rough
consensus" about the requirements draft because I do not
see how adopting it can resolve anything when the same people
who endorse it at an IETF meeting also say that URP is
ready for final call at the same meeting. To me, adoption
of a "rough consensus" decision should *resolve* something,
so that we can move on.

If the WG has come to the conclusion that it cannot or should
not enforce that constraint then it should say so, loud and
clear right up front in the requirements draft.

No amount of repetition from John and Chris or anyone
else about the "room consensus" at IETF meetings can ever
substitute for a clear decision by the WG expressed in having
actually endorsed an explicit text.

My own view is that provision for such notifications is essential
in view of the operations model currently expected by clients
being incompatible with that which can be provided by multi-master.
I believe it should be clearly stated as a requirement so that
work on meeting that requirement will begin now, rather than later.

However I have agreed with you that discussion can be deferred
until after the requirements draft has gone through as there
is very clearly no consensus in support of it and the need for
it can emerge in discussion of concrete measures to implement what
appears to be agreed, about notifications to system administrators.

As long as it is *possible* to notify system administrators, then
a decision to implement other notifications later would not
require fundamental redesign but merely adding something, so the
requirement as currently stated is sufficient to avoid being
trapped in a wrong architecture later.

That is also why I have, at John's request, documented yet again
that the current architecture and the URP design does not meet that
stated requirement to be able to repair constraint requirement
violations, let alone the stronger language in the architecture
draft - that constraint violations are actually repaired.

As for how to do add notifications. I do not think it is necessary
to discuss that during this "last call" on requirements as there is no
requirement either to add them or not to do so.

However I have already put forward suggestions (not concrete proposals)
in MDCR. The only concrete proposal was that only the originator DSA
should be responsible for revocation or confirmation notices to the
DUA that invoked the original change at that DSA. This is consistent
with having separate conformance levels for implementations that do
not provide notifications (although I am not convinced that would
be desirable). I just referred generally to:

   Sending notifications would presumably depend on controls the DUAs
   used in their operations, attributes in the directory entry, perhaps
   in some other NC, for the DUAs DN (modifiersName) etc. Details
   should be considered in connection with other work on notifications
   and transactions as the complete history maintained by these
   procedures are likely to be relevant to both.

My own view is that the "other" (LCUP) work on notifications would meet the
harder requirements of the few applications that really need confirmations
as soon as possible and that revocation notices by email to the DUA's
email address would be adequate for most applications that just
need to be told what went wrong before something else dependent
on it results in calls to a help desk. After all, multi-master
is inherently unsuitable for applications with a high rate of
concurrent changes to the same entry anyway. Indeed the directory
service itself is designed for relatively static data with a high ratio
of reads to writes. So simply firing off an email when something
undesirable happens is not a huge burden. Manually dealing with
help desk calls from users puzzled about unexpected and unexplained
events that were not happening before would be far worse.

BTW I believe such notices are needed for create and rename
conflicts as well. URP simply renames both entries for double the work.

My understanding is that the argument for that is based on the possibility
of confusion if somebody applies changes to some other entry thinking it
is the entry they have just created or renamed. I believe there is no way
around the fact that the name of an entry uniquely specifies *the* entry
as far as the whole X.500/LDAP data model and all applications based on
it is concerned, and that notifications are a better solution. Again
however, that need not be a requirements issue at present as URP clearly
*does* preserve the information necessary to correct the problem,
so a decision to reduce the sysadmin and helpdesk workload via notifications
to applications and their users can be taken later without needing a
fundamental redesign.

In fact the more I think about it, the more I see advantages in your
minimalist approach of just requiring now that the necessary information
be propagated and made available to system administrators. That approach
is consistent with the architectural principle in RFC 1958:

   3.7 In many cases it is better to adopt an almost complete solution
   now, rather than to wait until a perfect solution can be found.

It is also consistent with my referring to details to be considered
later, in MDCR and with my not having included notifications among the 3
"key points"
in my "Summary of Objections to Requirements Draft" which eventually led
to the review by you and Rick:

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

BTW I have not raised the third key issue, "modifiersName" as a requirements
issue as I gather the non-normative text reflects a likely WG consensus that
it
should be supported anyway. In giving the example concerning deletion of X
by user
A and Z by user B, with responsibility for both changes arbitrarily assigned
to
one of them, I should perhaps have explicitly mentioned that this violates
the
semantics and frustrates the purpose of modifiersName rather than just
referring to it as loss of directory information. If for example A is
arbitrarily
listed there is no way to tell that it was actually B who deleted Z and
solve the mystery as to "who done it" when inspection of the application
used
by A shows it appears to work safely. With the required semantics you can
always be sure that whoever is listed used an application which resulted
in a corrupted entry, so fixing that application to ensure "what you changed
is what you saw" will solve the problem. With URP all you get is a mystery,
further confused by a misleading "modifiersName".

[Ryan]

[Albert]
*Many* applications may not need it. There is some evidence in support
of that from the deployment of two non-interoperable multi-master
implementations that do not provide it. Presumably they
would have fixed the problem if it made things unviable in a closed
environment where applications are using vendor APIs rather than
LDAP APIs for applications that require data integrity.

For example Active Directory uses a single valued attribute for
access controls which can only be modified easily through specific
proprietary COM APIs and has an elaborate rigmarole for other COM
APIs to use "consistency guids" and "child counts" to maintain data
integrity. They also provide 3 different kinds of trigger/notifications
services for use through COM APIs.

Attempting to achieve standards for interoperability among clients
and servers using a common protocol with *different* clients in
an open environment *does* require that everything necessary for
that be fully standardized. Otherwise the directory administrator
has to select a single proprietary implementation for all DSAs
in a multi-master replication network, simply because *some*
applications *do* require data integrity. That negates the point
of interoperability - especially considering that one of those
applications is access control.

BTW It should be emphasized that there can only be one directory
administration in a multi-master replication network, since
each DSA is equally authoritative. It certainly can't be a matter
of each individual DSA deciding what it needs to use.

In the event that requirements indicate there is scope for local
DSAs that never have DUAs using applications that need data
integrity, then a separate conformance level could be defined,
without notifications. But unless whatever is required for
full interoperability is actually defined by some standard,
then it simply cannot be achieved by a directory administration
wishing for it.

[Ryan]

[Albert]
Yes I chose the example to fit precisely with the requirements concerning
information loss and illustrate the consequences for access controls.

You have certainly demonstrated a better understanding than mine of
what "some folks" are inclined to assume and how to get things across
to the WG, so by all means feel free to add more suitable examples.

Frankly, after nearly a year, I have run out of patience myself.

In my view it ought to be sufficient to have merely pointed out that
the LDAP data model requires atomicity and URP does not support it,
as was done repeatedly by many people before I joined the WG.

It should not have been necessary to write a draft explaining that:

   For the same reasons, URP must inevitably break the semantics of
   other relationships between attributes values understood only by
   applications. Among those applications are the management of
   prescriptive access controls and other policy information, and hence
   the viability of multi-master replication itself.

Nor should it have been necessary to provide a positive solution,
showing how the problem can be fixed, as I did nearly a year ago.

People competent to take decisions about these matters should be
expected to understand that if you break the data model, then
applications dependent on that model will break and realize the need
for a different approach without tutorials.

It should not have been necessary to spell it out in detail, with an
example of loss of directory information, as I did more than 6 months ago:

***
The problem I was referring to is that URP merges the addition or deletion
of different attribute values of a single entry made concurrently by DUA
operations at different replicas.

That means the set of ACI attribute values which each of two users thought
they were establishing, will differ from the set of ACI attribute values
that
actually result from their concurrent actions. The example below from
Alison's
document shows the 9 states that could result from concurrent updates to two
attributes at one replica with eventual convergence to one of those changes.

Exactly the same applies to concurrent changes to two values of a single
attribute such as ldapACI. In addition, the eventual convergence can be to
a mixture of both changes with some attributes or attribute values changed
by one concurrent operation and others changed by the other. If two users
delete an attribute value from an attribute with 2 values it ends up empty,
and possibly a schema violation, although each thought they were setting it
to the single value the other thought they were deleting.
***

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

Since John actually *asked* for an elaboration, even though it was mixed
in with the usual hallucinations about everything being settled, I have
provided it.

Here's the pseudo code you would have to deal with to confirm that
URP does not detect the loss of directory information and report
a schema violation when 2 values are concurrently deleted from
a mandatory attribute:

   5.3.7 Processing Remove Attribute Value Primitive

   This section details the algorithm for processing the p-remove-
   attribute-value (P.uid, P.type, P.value, P.csn) primitive, which
   describes the removal of a single attribute value.  If P.type is the
   entryUUID attribute type then the primitive MUST be rejected.

      IF no value deletion record (uid, type, value, csn) exists
            where (uid = P.uid AND type = P.type AND
               value = P.value AND csn >= P.csn)
         AND
            no attribute deletion record (uid, type, csn) exists
               where (uid = P.uid AND type = P.type AND csn >= P.csn)
         AND
            no entry deletion record (uid, csn) exists
               where (uid = P.uid AND csn >= P.csn)
         IF entry, E, with uid = P.uid exists
            {
            IF P.csn > E.csn
               IF attribute value, V, of P.type
                  where V = P.value, exists in E
                  {
                  IF P.csn > V.csn
                     IF V is distinguished
                        IF ProtectDistinguished()
                           V.csn := GenerateNextCSN(P.csn)
                        ELSE
                           {
                           R := E.rdn
                           remove value V
                           CheckUniqueness(E, E.superior, R)
                           StoreValueDeletion (P.uid, P.type, P.value,
P.csn)
                           }
                     ELSE
                        {
                        remove value V
                        StoreValueDeletion (P.uid, P.type, P.value, P.csn)
                        }
                  }
               ELSE
                  StoreValueDeletion (P.uid, P.type, P.value, P.csn)
            }
         ELSE
            StoreValueDeletion (P.uid, P.type, P.value, P.csn)

Want some documentation? Sorry folks, those 38 lines *are* the
documentation.

If you can tell that the above means that URP loses directory
information and does not detect schema conflicts, then you have solved
the URP puzzle. Although I claim the honour of having done it long ago.

On joining the WG I read through the archives and noted that it had become
bogged down playing puzzle games in which somebody would suggest something
that URP breaks and Steve would either demonstrate that it doesn't or
propose
another fix. The central point that a protocol design has to be verifiable
and
comprehensible so that you *know* what will happen when you deploy it, was
completely lost. There are good reasons for the IETF requirement of at least
2 interoperable implementations based on a published specification.

It just went on and on, even after someone had remarked that aspects were:

"...preposterously complex. You seem to be tying yourselves in knots with
this..."

That was from an X.500 expert - unlikely to be unusually intolerant of
preposterously
complex specifications.

If LDUP WG members enjoy such puzzles, as I do, attached is a slightly
shorter one.

What is the next number? 1 11 21 1211 111221

Answers by email will be acknowledged. Please do not answer in the list.

But note that it *is* a puzzle. Knowing how something works for a few
examples does not immediately tell you the principle behind it or how it
will work with other examples. For that you need to know the algorithm.

But that can be puzzle too, as in the attached python code, slightly shorter
than the above URP pseudo code, which likewise doesn't tell you much
about what it actually does, although it reproduces that sequence exactly.

It is generally understood that *one* example is sufficient to
demonstrate that a protocol is broken. There should be no need to
provide others. It is up to the proponents to show correctness.

But iff you believe further examples would be useful, by all means
provide them.

Meanwhile I've got to get back to repeating myself on all the other
issues that John asked me to elaborate on.

In my view a quick glance at URP ought to have been sufficient to
reject the idea of an interoperable standard being based on obscure
pseudocode.

There ought to be requirement that the protocol specifications
be be predictable and make some kind of sense to users - as
suggested long ago. So that (plus moving the text from the
architecture draft) makes two more requirements issues.

---

From: "Ryan Moats" <[email-masked]>
Date: Sun, 25 Feb 2001 09:24:17 -0600

See <rm2>...</rm2> below... Ryan

P.S. I'm extracting some stuff to shorten the message
with [snip...]

-----Original Message-----
From: Albert Langer [mailto:[email-masked]]
URP proposals - part A - Fatal Show Stoppers

[snip...]

[Albert]

[snip]

<rm2>That was my intent, and I thought it was clear</rm2>

The way I see it LDAP standards specify what can be written to the
directory so as to determine what can be read from it and thus enable
globally deployable directory applications to work with any conformant
server and any conformant client using a standardized client server
protocol. As part of that they specify *both* what must be the outcome
of an update write invoked by a client and what response and error
messages must be returned to the client immediately.

There is no provision for subsequent notifications to clients in the base
standards because the response returned immediately is entirely sufficient
in a single server or a single master environment.

<rm2>Ah, that's where we differ.  I feel that once the initial notice
is made, "loose consisitency" is being maintained.</rm2>

***

<rm2>That's a reasonable proposal and we (the authors) will
discuss it. I'm not promising we'll put it in, but we WILL discuss
it on our next call :-)

I admit to still disgesting the rest of the mail and so
If I have comments, I'll make them later.</rm2>

[snip]

---

From: "Albert Langer" <[email-masked]>
Date: Mon, 26 Feb 2001 08:46:07 +1100

Continuing from part 1, which defines the categories used:

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

* B) Fixable Show Stopper *

3) Eventual Convergence

G1.  LDAP Replication MUST support models 2 (Eventual Consistency) and
3 (Limited Effort Eventual Consistency) above.

M3.  A value shared between replicas in a replica ring must eventually
converge to the same value on all of its constituent replicas.

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

Each of these requires "eventual convergence" (the wording and redundancy
could be improved - as is true of other items, without further comment
below).

Achieving that necessarily requires three things.

a) All servers that are to converge must have a common view of which servers
are within the Replication Set of servers from which updates must be applied
and which are excluded from it. Otherwise some servers would be applying
updates
that others are not, and therefore they cannot converge.

b) All servers that are to converge must apply a common update processing
algorithm to the updates they receive, that is guaranteed to produce the
same results at all of them when no further changes are occurring, provided
all of them receive the necessary updates.

c) All servers must receive all the update information they need in order
for the specified update processing algorithm to converge, regardless of
which server generated the original change.

The mechanisms specified in the architecture and URP for this look extremely
brittle in a world where clocks are not necessarily even monotonic,
network connectivity can fluctuate rapidly and servers crash and get
restored from backups (not always the right backups).

As the intention appears to be to meet the requirement and any
actual problems are fixable using a properly layered report propagation
protocol, detailed analysis is unecessary at this time.

4) Entry identification

SC9.  An entry MUST be uniquely identifiable throughout its lifetime.

As a consequence of non-atomicity, URP can delete each of 2
components of an RDN due to rename operations at different
replicas, leaving the entry without a name. This may in fact be fatal
but there are so many bizarre kludge fixes in there I cannot rule out
the possibility that one might be feasible for this.

* C) Fixable Noncompliance *

5) Schema Replication

Fatal aspects have been referred to elsewhere. There is no
provision for replicating schema definitions (which require
synchronization etc). That may also be fatal but I have not
studied the matter, so have listed it as fixable.

6) System and Network Performance

G3.  LDAP replication SHOULD have minimal impact on both the system and
network performance.

MM1.  The replication protocol SHOULD NOT saturate the network with
redundant or unnecessary entry replication.

The main performance impact to be minimized is replication spikes
due to full instead of incremental replication. The design maximizes
the occasions on which that will be necessary. This may be partly due
to MM7 and SM2 discussed in section E. Strict in order transmission
of updates between neighbours in a better report propagation
protocol to meet eventual convergence requirements robustly would
also fix this problem.

7) Missing

P1.  The replication protocol MUST provide for recovery and
rescheduling of a replication session due to replication initiation
conflicts (e.g. consumer busy replicating with other servers) and or
loss of connection (e.g. supplier cannot reach a replica).

P3.  The LDAP replication protocol MUST allow for full update to
facilitate replica initialization and reset loading utilizing a
standardized format such as LDIF [RFC2849] format.

AM2.  Each copy of a replica MUST maintain audit history information of
which servers it has replicated with and which servers have replicated
with it.

AM5. A mechanism to fix differences between replicas without triggering
new replica cycles SHOULD be provided.

No mechanisms appear to have been specified. It is unclear what
document they should be specified in, but they all involve some interaction
with URP. This appears to be an oversight that would not require
any special fix beyond just doing it somewhere. Other requirements that
do not not appear to have been implemented anywhere may also be relevant
to URP, but I haven't checked carefully enough to be sure.

* D) Fatal Noncompliance *

8) Single Master Support

M2.  The replication model MUST support both master-slave and multi-
master relationships.

SM1.  A Single Master system SHOULD provide a fast method of promoting
a slave replica to become the master replica.

SM2.  The master replica in a Single Master system SHOULD send all
changes to read-only replicas in the order in which the master applied
them.

The architecture and URP are designed to compel
complete implementation of multi-master protocols rather than
providing a migration path for existing implementations. No work
whatever has been done on specifically Single Master aspects.

9) Schema Enforcement

M10. While different directory implementations can support
different/extended schema, schema mismatches between two replicating
servers MUST be handled.  One way of handling such mismatches might be
to raise an error condition.

P8.  The protocol MUST support a mechanism to report schema mismatches
between replicas discovered during a replication session.

No means of detecting schema mismatches is provided by URP. It cannot
even detect schema violations. (Some aspects may arguably be fixable).

* E) Requirements Problem

10) Bizarre Requirement for Non-interoperability

"(2) replication among directory servers with different application trigger
semantics may compromise directory data integrity."

Although not listed in the Requirements section, this clause in
section 3 is clearly intended to constrain the protocol standards to
*not* require interoperability from implementations with "active" data.

URP does not meet this "requirement" as it specifies a perfectly sensible
means by which such implementations can interoperate and requires them
to implement it:

U5.1 "A directory server implementation may also perform implicit updates
   in response to user update requests, e.g. to maintain the referential
   integrity of distinguished names.  Appropriate CSNs and deletion
   records for these changes MUST also be generated.

   A detailed description of the replication processing for these other
   types of update is beyond the scope of this document."

11) Design constraint on orderinig

MM7.  Multi-master conflict resolution MUST NOT depend on the in-order
arrival of changes at a replica to assure eventual convergence.

SM2.  The master replica in a Single Master system SHOULD send all
changes to read-only replicas in the order in which the master applied
them.

(Appendix B.2 explains that requirement SM2 is intentionally not a
MUST and does not apply to multi-master at all)

URP does not meet SM2 for Single Master but does meet MM7, at the expense
of conflicting requirements G3 and MM1. Appendix B.2 does justify SM2,
although the justification points to MUST and the explanation does
not justify not adopting the same for multi-master and
simply dropping MM7.

Decisions about ordering are a design issue, not requirements.
Design constraints should not be included in requirements without
a clear reference to corresponding actual requirements.

12) Design constraint on update tracking

P2.  The supplier MUST track updates sent to the consumer and not
resend already acknowledged ones, even in the event of recovery from a
failed replica cycle.

This is another unecessary design constraint. It is not satisfied by
URP and there does not appear to be anything unsound about the URP approach
of
having the consumer track updates received rather than the supplier
tracking updates sent.

13) Transactional Consistency

G2.  LDAP Replication SHOULD NOT preclude support for model 1
(Transactional Consistency) in the future.

P7.  The protocol SHOULD NOT preclude support of Transactional
Consistency (model 1).

Model 1: Transactional Consistency -- Environments that exhibit all
four of the ACID properties (Atomicity, Concurrency, Independence,
Durability) [ACID].

No multi-master replication system can avoid precluding support
for ACID transactions. That is inherent in the definition. Nor
does the C stand for Concurrency. Nor does the I usually stand
for Independence.

http://www.scism.sbu.ac.uk/georgeub/sharenotes/Wk10_Transaction_Concurrency/
tsld003.htm

ACID transactions are also impractical in a global distributed
directory service even using single master - eg it is unscalable
to maintain referential integrity between different servers.
That is why they are excluded from the X.500 data model.

The whole discussion of models is simply confusing and confused.
It should be dropped as adding nothing to either requirements
or understanding as demonstrated by the inaccurate definitions
and references.

Instead definitions of concepts that are not already defined or well
understood should be provided - eg granularity of operations, granularity of
replication, concurrency, consistency, isolation, durability,
serialization, convergence. In particular there is ongoing confusion about
the
whole concept of "loose consistency" and the fundamental distinction between
the data model permitting different servers to have different versions
of data with only "eventual" convergence, and changes inconsistent with
the constraints of the data model.

A meaningful replacement for G2 could then be something like this:

"The protocols SHOULD NOT hinder standardization of extending the
granularity
of LDAP operations beyond a single entry."

URP would not meet such a more reasonable requirement since it does
not respect the granularity of operations being even at the
attribute level, let alone the entry level.

Other similar requirements would also be appropriate, eg:

"The protocols SHOULD NOT hinder standardization of signed operations"

URP would not meet such a requirement because it does not replicate
operations at all.

In general a review of existing and proposed LDAP extensions should
be undertaken as part of requirements analysis to determine what
avoidable problems could result from multi-master deployment so
that the architecture and design will take those into account
and try to minimize their impact. This could best be done by
publishing an explanation of the sort of issues likely to arise
in an initial requirements document and actively soliciting feedback.

14) Limited Effort Consistency

G1.  LDAP Replication MUST support models 2 (Eventual Consistency) and
3 (Limited Effort Eventual Consistency) above.

URP makes no attempt to support model 3 (any failure in its attempt to
support model 2 does not constitute supporting model 3, which is
aimed at entirely different design goals completely irrelevant
to LDAP directory replication).

Discussion of this requirement can be found at:

According to WG co-chair Chris:

***
It would not be listed as a MUST at
this stage of revising the requirements document if the authors (some of the
top LDAP experts in the world) and many other members of the working group
didn't know of a good reason for it being stated as that strong of a
requirement.
***

That does not constitute a good reason, for anything other
than not bothering to argue with Chris. That may also be relevant to
John's recent complaint about WG members not having raised issues about
the draft earlier.

While other statements have not been irrational and anti-rational, none
have provided any plausible reason why this WG should undertake such work.
Chris evidently does not know of one and I have seen nothing to indicate
that anyone else does either.

Incidentally the reference given for Xerox Clearinghouse in the description
of model 3 is in fact a reference to Bayou - an entirely different system.
(If anyone is seriously interested in pursuing model 3, I believe Ed was
involved in Xerox Clearinghouse and could provide some background as to
its relevance or irrelevance to the work here as well as a more accurate
and online reference).

Requirements should not amend the WG charter.

---

From: "Steven Legg" <[email-masked]>
Date: Mon, 26 Feb 2001 18:10:15 +1100

Albert,

Albert Langer wrote:
> (BTW one
> perhaps due to the "Fatal" problems.

Multimaster replication was dropped as a work item in the X.500 working
group because no one was attending the meetings to progress it. It wasn't
a decision based on technical merit. I note however, that LDUP is within
the scope of the X.500 group's new work item on LDAP/X.500 alignment.

With regard to the references to DAP and DSP in the URP draft, I consider
this to be entirely proper. It seems the majority of LDAP server
implementations are also X.500 implementations, so when talking about
multimaster replication between LDAP directories it is appropriate to
consider how X.500 access protocols interact with LDUP. It also provides
a model and examples for how other non-LDAP access protocols can be
accommodated by LDUP.

We're not telling X.500 how to do multimaster replication, we're telling
LDAP servers that also implement X.500 access protocols how to do LDAP
replication.

> for Z.

Wrong! - on several counts.

According to URP the change from user A will generate a
p-remove-attribute-value for each of X, Y and Z, and a p-add-attribute-value
for both Y and Z. Additionally, a p-remove-attribute will be generated
for the modifiersName attribute, and a p-add-attribute-value for the
modifiersName value "A". All primitives generated from this operation
are given a CSN with the same time, change count and replica identifier,
such that it is greater than any existing CSN on X, Y, Z and modifiersName,
among other constraints described in URP. The CSN isn't necessarily
larger than any existing CSN for X at any replica.

The change from user B will generate a p-remove-attribute-value for each
of X, Y and Z, and a p-add-attribute-value for both X and Y. Additionally,
a p-remove-attribute will be generated for the modifiersName attribute,
and a p-add-attribute-value for the modifiersName value "B". All primitives
generated from this operation are given a CSN in the manner described for
the update by user A.

> So both will eventually be deleted at all replicas (with

The eventual result will depend on which operation was given the higher CSN.
If user A's operation has the higher CSN, Y and Z will be present, X will
be absent, and the modifiersName will be given as "A". If user B's operation
has the higher CSN, X and Y will be present, Z will be absent, and the
modifiersName will be given as "B".

It will look like either A or B's operation has been performed but not a
mixture of both.

> part - ie so that it will cease to be atomic.

Given that the consensus of the working group is to merge changes in
conflict
rather than later rejecting one of them and posting a recind notification,
what would you propose we do instead to merge changes ?

> of directory information.

You keep making this allusion to URP being the replication protocol. It's
not
a protocol, so it doesn't propagate anything. It's a collection of
procedures
for breaking down updates into simple primitives and for applying
said primitives delivered by the replication protocol. If the replication
protocol wants to deliver other information, to other replication
sub-systems,
for other purposes, that need not be a concern for URP.

> modify operation.

No, the fact that attemping to delete a non-existent value or add an
existing value will produce an error result is what guarantees that
the operation will fail if that value had been removed by some other
DUA since the entry was read by the DUA. The point of having more than
one modification is to combine multiple actions into an atomic operation.
The point of having an ordered sequence of modifications is to have a
deterministic result. We carefully number the sequence of modifications
in LDUP so that we get a deterministic result and eventual convergence.

> If the components of the modify were applied in the

> Result, intended by neither, is that the madhatter is allowed

If URP is applied correctly, the result is either X or Z is removed, but
not both. Exactly what you want.

Regards,
Steven

---

From: "Albert Langer" <[email-masked]>
Date: Mon, 26 Feb 2001 20:01:35 +1100

[Steve]
[...]

[Albert]
If that is the case it *completely* refutes my example.

I will study your detailed explanation carefully (and defer responding to
other matters such as X.500 DAP and DSP until I have done so).

Either way, your comment clearly establishes that URP is intended
to meet the stated requirement and therefore that requirement can be used
in evaluating whether it actually does so, without confusion or
misunderstanding.

At this stage it appears to me that either I have been under a fundamental
misconception about URP all along, or have just chosen a bad example.

I might be under a similar misconception about the consequences of the
transient inconsistent states described in Alison's consistency
discussion and will be reviewing that too. Anything you would like
to draw to my attention to about my earlier comments concerning that,
either here or via direct email will be welcome.

Likewise I might be under a misconception that URP does not respect
atomicity when more than one attribute is being changed. Any comments
on that would also be welcome.

[Steve]

[Albert]
My preference would be to not merge changes because I do not believe
most applications actually do take sufficient precautions to ensure
"what you changed is what you saw" as that rarely causes real problems
in a single master environment, so they would be taken by surprise
when it no longer works with multi-master (despite adequate warnings
in standards and documentation). Whereas the failure of such merged
changes would not be significantly different from behaviour they
are alredy designed to deal with - that some other change can
subsequently obliterate theirs, especially if that results in a
notification.

However I certainly agree that is an issue on which the WG is
perfectly entitled to adopt an opposite view and does not involve
any kind of "fundamental technical mistake" that would require
review elsewhere.

If URP is in fact capable of conforming to the LDAP modify operations
atomic semantics, I will withdraw my objection.

> of directory information.

[Steve]

[Albert]
If URP does not drop the atomicity information and thereby prevent it from
being propagated to other servers I am not concerned about terminology. My
point
was entirely based on a belief that it does drop the information, which
I will now review.

[...]
[Steve]

[...]
[Albert]
If the result is both deterministic (which I have always accepted) and
also consistent with ldap modification semantics as you are saying,
then you have proved your case and I will withdraw mine.

[Steve]

[Albert]
Agreed - if that is what it does, also in other related cases, it is
exactly what I want. (Which leaves me somewhat perplexed by the repeated
statements that what I want is "unreasonable", inappropriate for
multi-master etc etc. But I guess at this point you must be equally
perplexed as to what I have been objecting about ;-)

Will get back to you shortly.

---

From: "Albert Langer" <[email-masked]>
Date: Tue, 27 Feb 2001 01:51:59 +1100

[Albert]
Ok, here's my attempt to work through your explanation. Please point
out precisely where I have misunderstood.

[...]

[Steve]

for both Y and Z. [...]

[Albert]
I'm stopping right there. I don't understand this.
Here's the text from draft-ietf-ldup-urp-03.txt.

   4.3 Replication Primitives

   Each update operation performed on an entry in a part of the DIT
   subject to one or more replication agreements MUST be subsequently
   reported as replication primitives to the replication partner
   directory servers of those agreements.  The collection of primitives
   sent by a directory server to a replication partner will reflect both
   the results of locally processed user update requests and also of
   replicated updates received from other directory servers.  A single
   update operation will decompose into one or more primitives.

   Common to all update primitives is an entry identifier argument, uid,
   containing the Unique Identifier of the target entry of the change,
   and a CSN argument, csn, to indicate the time of the change.  In the
   case of adding a new entry, the Unique Identifier for the entry is
   allocated by the directory server in the course of processing the
   operation.  Additional arguments are present depending on the type of
   replication primitive.

[...]

[...]

   These primitives reflect the intended final state of an update
   operation rather than the specific changes required to achieve that
   state.

I cannot see any possibility of an implementor not reading the final
sentence as a *completely* unambiguous statement that the
implementation must *not* do what you say:

"the change from user A will generate a p-remove-attribute-value for
each of X, Y and Z, and a p-add-attribute-value for both Y and Z."

Doing that would be reflecting the "specific changes required to
achieve that state" - which is precisely what you have told them
*not* to do.

Even without the final sentence, one could hardly read the
previous two quoted sentences as though they said:

   The p-add-attribute-value(uid, csn, type, value) primitive is used to
   describe the addition of a single attribute value to an entry, even
   if the attribute value was already present.[...]

   The p-remove-attribute-value(uid, csn, type, value) primitive is used
   to describe the removal of a single attribute value from an entry,
   even if the attribute value was not removed.[...]

In order to implement your specification the implementor would
"reflect the intended final state" by generating a single
p-remove-attribute-value for X. The intended final state of
the modification was to remove X while leaving all other
values of the attribute unchanged. The operation either
failed - in which case no changes were made and no primitives
were generated, or it succeeded - in which case it succeeded
in removing X and the single primitive reflecting that would
be generated.

There is no ambiguity whatsoever.

So I am not continuing with my review of what I might have
misunderstood past this point, while awaiting your explanation.

It seems to me that:

a) You have accepted the current requirements P6 and MM5 and the
definitions of "Atomic Operation" (with reference to what "the LDAP
standards guarantee") and "Atomicity Information", by not objecting
in a "last call" where "silence means consent".

b) You have demonstrated a clear understanding of what is required
by the "LDAP standards guarantee of atomicity" by saying that URP
is intended and designed to resolve conflicts between modify
operations with the result that:

"It will look like either A or B's operation has been performed but not a
mixture of both."

If you will confirm my understanding above, I will be quite happy to
join in a WG consensus on the requirements draft, as my concern that
it won't actually resolve anything is eliminated.

If it turns out that the non-atomicity in URP is fixable, that's
fine by me. All I want is for the behaviour expected by LDAP
applications as a result of what the LDAP standards guarantee,
to be provided. Contrary to John's persistent sniping, the only
reason I wrote MDCR was to show that an alternative was possible,
and I would be just as happy for my objections to not providing
what the LDAP standards guarantee to be resolved by URP as by
MDCR.