Subject: Re: URP - Distinguished Not Present - New Option?

From: [email-masked]
Date: Tue, 31 Aug 1999 13:36:22 +0100

Hi John,

     Oops.  The option as described below is similar if not the same in
approach as Option 4 from the original list (thanks, Steve).  The timestamp
on the deletion flag is equivalent to keeping a deletion record for the
remove, but overriding it with the earlier rename operation.  This
introduces the same history issue as with option 4, and which has been
discussed at reasonable length.  Steve's mail from 09 August 99, "Re:
Delete Not Present - Options and Recommendation" describes the reasons
behind the need for history through a number of examples.

Regards,
Alison

Alison Payne
26.08.99 11:43

To:   [email-masked]@internet, [email-masked]@internet
cc:   [email-masked]@internet
Subject:  Re: URP - Distinguished Not Present - New Option?  (Document link
      not converted)

Hi John, Steve,

     Here's a summary (below) of the modification I think you are
proposing.    Is this right?

     I believe the issue Steve raised (also below) is not a problem with
this option.   With this option, we have a time in the "overall ordering"
after which a remove due to the delete not present flag will not take
effect.   The problem Steve is discussing comes up when we rely on the
"real world time" of deciding when a delete not present flag will not take
effect.

     Comments?

Cheers,
Alison

---------------------------------------------------------------------------
---------------------------------------------------------------------------
---------------------------------------------------------------------------
----

Option (2a)  Modification to Deletion-Flag approach

The deletion flag is added as currently specified in the draft
(ietf-legg-ldup-urp-01.txt) BUT
     - i.  is timestamped with the value of the remove operation which
caused it (currently no timestamp)
     - ii.  is discarded when it is clear that no further operations will
be received which are older than the timestamp on the deletion flag
(currently the deletion flag is held until another rename removes the
attribute from the name, and if this occurs, the setting of the flag
determines whether the attribute remains or not)
     - iii.  if a deletion flag exists on an entry, and an older rename
operation occurs which causes the attribute to become non-distinguished,
the flag will be used to determine whether the attribute is removed or
stays (as in the current algorithm, but in more limited circumstances)

Benefits :
The RDN always reflects an administrator choice.
The later remove will be overridden by the rename UNLESS another external
operation occurs between these two which causes the remove to be ok.
All DSAs will eventually have the same consistent state.

Risks :  Same risk of complexity in implementation as in option 2.  Maybe a
little reduced since the flag can now be discarded.   The new risk below
doesn't exist for this option.

Steven Legg <[email-masked]> on 18.08.99 02:05:30

To:   [email-masked], [email-masked]
cc:
Subject:  Re: URP - Distinguished Not Present

John,

>From: [email-masked] (John Merrells)
>To: LDUP <[email-masked]>
>Subject: URP - Distinguished Not Present
>Date: Tue, 17 Aug 1999 14:11:37 -0700

>b) The DNP flag should have it's own CSN, and be purged independently
>    of the value with which it is associated. If the DNP CSN drops below
>    the Purge Vector, then we promote the value to be Present. In this
>    way we've undone the Modify-Delete, which would have been rejected,
>    had the operations been seen in order.

I've looked at ways of purging the DNP flag but haven't found anything that
works. Suppose we have some value V, which is made
distinguished at one DSA at time t1, and deleted at time t2 at
some other DSA. In due course both DSAs will see both updates and
make V distinguished-not-present. Now suppose there is some
operation at time t3 that makes V non-distinguished. What we do
with V depends on whether we have purged the DNP flag (with CSN t2).
Because the information to construct the Purge Vector takes time
to propagate around, different DSAs will purge the DNP flag at different
times. Some will have purged the flag before they see the
update at time t3 and some will still have it. Therefore some DSAs
will keep V and some will remove it. Not good! Having the DNP flag
persist indefinitely avoids this problem.

Regards,
Steven

______________________________________________________
Get Your Private, Free Email at http://www.hotmail.com

---

From: [email-masked] (John Merrells)
Date: Tue, 31 Aug 1999 20:07:06 -0700

> behind the need for history through a number of examples.

I think that our suggestion is slightly different from Option 4, in that
between the purge point and the present time we allow the delete to go
ahead if a rename (before or after) would permit it to do so, after the
purge point we behave as if we ignored the delete.

Going back to the example... where t# is time, u# is update, and the
replicas are {A,B,C}, and the entry E has DN=u and values {u,v,w}

t1, u1, A, rename entry to v
t2, u2, B, delete v
t3, u3, C, rename entry to w

These updates can be seen in six orders...

u1, u2, u3
u1, u3, u2
u2, u1, u3
u2, u3, u1
u3, u1, u2
u3, u2, u1

The behaviour of the updates on the state information stored 
on the values is described in pseudo code below. The updates
are 'delete a value', 'make a value distinguished', and 'make
a value not distinguished'. A rename operation usually makes
some values distinguished and others not.

Some Definitions. 

operation_csn: the csn of the update
present_csn: the csn of a present value
deleted_csn: the csn of a deleted value
dnp_csn: the csn of a distinguished not present value.

Note that a value will may have both a present_csn and
a dnp_csn at the same time.

~~~~ rename operation ~~~~

if entry dn csn is_before operation_csn then
  foreach component of the old rdn
    call rename-make-value-not-distinguished oldrdn_component
  foreach component of the new rdn
    call rename-make-value-distinguished newrdn_component
  entry rdn= new rdn
else
  // The DN doesn't change, but we reassert the existence
  // of the values in the new RDN.
  foreach component of the new rdn
    call rename-make-value-distinguished newrdn_component
end if

~~~~ rename-make-value-distinguished ~~~~ 

if value deleted then
  if value deleted_csn is_before operation_csn then
    add present_csn= operation_csn
    add dnp_csn= deleted_csn
    remove deleted_csn
  end if
else if value present then
  if value distinguished not present then
    change present_csn= operation_csn
  else
    if value present_csn is_before operation_csn then
      change present_csn= operation_csn
    end
  end
end

~~~~ rename-make-value-non-distinguished ~~~~ 

if value present then
  if value distinguished not present then
    if value dnp_csn is_before operation_csn then
      add deleted_cn= dnp_csn
      remove present_csn
      remove dnp_csn
    end if
  end
end

~~~~ delete-value ~~~~ 

if value deleted then
  if value deleted_csn is_before operation_csn then
    change deleted_csn= operation_csn
  end if
else if value present then
  if value distinguished not present then
    if value dnp_csn is_before operation_csn then
      change dnp_csn= operation_csn
    end if
  else
    if value is_distinguished then
        add dnp_csn= operation_csn
    else
      if value present_csn is_before operation_csn then
        add deleted_csn= operation_csn
        remove present_csn
      end
    end
  end
end

~~~~ purge ~~~~

Assume that we purge all csns stored on the value immediatly.
The purge csn is the smallest csn in the update vector.
When a dnp_csn is purged the value stays present.

I'll now apply these rules to our sample entry, which at time zero
is identical at each replica, and is composed of a dn and some values.

E= {dn=u, vals=[u,v,w] }

The csns on the value are of the form "value[;csn]*" where the csn can
be d# for deleted, p# for present, and dnp# for distinguished not present.
There's also a csn on the DN, which I'll denote with dn#

The update vector is a a sequence of csn numbers, uv = [1,2,3], and the
purge point (pp) is the smallest csn of the update vector.

Order 1: u1, u2, u3

u1: dn=v;dn1 vals=[u,v;p1,w] uv=[1,0,0] pp=0
u2: dn=v;dn1 vals=[u,v;p1;dnp2,w] uv=[1,2,0] pp=0
u3: dn=w;dn3 vals=[u,v;d2,w;p3] uv=[1,2,3] pp=1
purge: no change

Order 2: u1, u3, u2

u1: dn=v;dn1 vals=[u,v;p1,w] uv= [1,0,0] pp= 0
u3: dn=w;dn3 vals=[u,v;p1,w;p3] uv= [1,0,3] pp= 0
u2: dn=w;dn3 vals=[u,v;d2,w;p3] uv= [1,2,3] pp= 1
purge: no change

Order 3: u2, u1, u3

u2: dn=u vals=[u,v;d2,w] uv= [0,2,0] pp=0
u1: dn=v;dn1 vals=[u,v;p1;dnp2,w] uv= [1,2,0] pp=0
u3: dn=w;dn3 vals=[u,v;d2,w;p3] uv= [1,2,3] pp=1
purge: no change

Order 4: u2, u3, u1

u2: dn=u vals=[u,v;d2,w] uv= [0,2,0] pp=0
u3: dn=w;dn3 vals=[u,v;d2,w;p3] uv= [0,2,3] pp=0
u1: dn=w;dn3 vals=[u,v;d2,w;p3] uv= [1,2,3] pp=1
purge: no change

Order 5: u3, u1, u2

u3: dn=w;dn3 vals=[u,v,w;p3] uv= [0,0,3] pp= 0
u1: dn=w;dn3 vals=[u,v;p1,w;p3] uv= [1,0,3] pp= 0
u2: dn=w;dn3 vals=[u,v;d2,w;p3] uv= [1,2,3] pp= 1
purge: no change

Order 6: u3, u2, u1

u3: dn=w;dn3 vals=[u,v,w;p3] uv= [0,0,3] pp= 0
u2: dn=w;dn3 vals=[u,v;d2,w;p3] uv= [0,2,3] pp= 0
u1: dn=w;dn3 vals=[u,v;d2,w;p3] uv= [1,2,3] pp= 1
purge: no change

So, that seems to have come out OK. All orderings resulted
in the same final state for the entry.

I may have made a mistake applying the rules, but hopefully
someone will work through the example from first principles
and get the same results.

This message is now over long, but I suppose I should really
consider the other time orderings of the operations... to see
how purgin would affect the results. 

John