INTERNET-DRAFT S. Legg draft-ietf-ldup-urp-07.txt Adacel Technologies A. Payne Telstra February 25, 2003 LDUP Update Reconciliation Procedures Copyright (C) The Internet Society (2003). All Rights Reserved. Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This draft is published by the IETF LDUP Working Group. Distribution of this document is unlimited. Comments should be sent to the LDUP Replication mailing list or to the authors. This Internet-Draft expires on 25 August 2003. 1. Abstract This document describes the procedures used by Lightweight Directory Access Protocol (LDAP) directory servers or X.500 directory servers to reconcile updates performed by autonomously operating directory servers in a distributed, replicated directory service, using the LDAP Duplication/Replication/Update protocols. Legg & Payne Expires 25 August 2003 [Page 1] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 2. Table of Contents 1. Abstract ....................................................... 1 2. Table of Contents .............................................. 2 3. Introduction ................................................... 2 4. Conventions .................................................... 3 5. Model Extensions ............................................... 3 5.1 Unique Identifier ......................................... 3 5.2 Timestamps & Existence .................................... 4 5.3 Replication Primitives .................................... 4 5.4 Lost & Found .............................................. 6 6. Replication Procedures ......................................... 6 6.1 Processing LDAP, DAP or DSP Operations on the DIT ......... 6 6.1.1 Add Entry ............................................ 8 6.1.2 Remove Entry ......................................... 9 6.1.3 Modify Entry ......................................... 9 6.1.4 Modify DN ............................................ 11 6.2 Sending Replication Primitives ............................ 12 6.3 Processing Replication Primitives on the DIT .............. 12 6.3.1 Saving Deletion Records .............................. 13 6.3.2 Glue Entries ......................................... 14 6.3.3 Generating Change Sequence Numbers ................... 14 6.3.4 Comparison of Attribute Descriptions and Values ...... 15 6.3.5 Entry Naming ......................................... 17 6.3.6 Processing Add Attribute Value Primitive ............. 19 6.3.7 Processing Remove Attribute Value Primitive .......... 20 6.3.8 Processing Remove Attribute Primitive ................ 21 6.3.9 Processing Add Entry Primitive ....................... 22 6.3.10 Processing Remove Entry Primitive ................... 23 6.3.11 Processing Move Entry Primitive ..................... 24 6.3.12 Processing Rename Entry Primitive ................... 25 7. Security Considerations ........................................ 26 8. Acknowledgments ................................................ 27 9. Normative References ........................................... 27 10. Informative References ........................................ 28 11. Copyright Notice .............................................. 28 12. Authors' Addresses ............................................ 29 3. Introduction This document describes the procedures used by Lightweight Directory Access Protocol (LDAP) [LDAP] or X.500 [X500] directory servers to reconcile updates performed by autonomously operating directory servers in a distributed, replicated directory service using the LDUP protocol [ARCH]. Each DAP, LDAP or DSP operation successfully performed by a directory Legg & Payne Expires 25 August 2003 [Page 2] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 server is subsequently reported to other directory servers with which it has an LDUP [ARCH] 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. A directory server will receive replication primitives from its various agreement partners according to the agreement schedules [ARCH]. Those primitives MUST be reconciled with the current directory server contents. In broad outline, received replication primitives are compared to the timestamp information associated with the directory data item being operated on. If the primitive has a more recent timestamp a change in the directory contents is made (which may involve only the revision of the timestamp). If the directory server has other replication agreements then the primitive is retained for forwarding during replication sessions for those other agreements. If the primitive has an older timestamp it is no longer relevant and is simply ignored. The Update Reconciliation Procedures (URP) are designed to produce a consistent outcome at all participating directory servers regardless of the order in which the primitives are received and processed. The primitives can also be safely replayed in the event that an exchange of replication information with another directory server is interrupted. This greatly simplifies the recovery mechanisms required in the replication protocol. 4. Conventions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. 5. Model Extensions This section describes the extensions to the data model required to support multi-master replication. 5.1 Unique Identifier A Unique Identifier is associated with each entry in the global DIT. This Unique Identifier MUST be globally unique for all time in the Directory. This can be achieved by defining a unique prefix for each directory server and then ensuring that the suffix of the Unique Identifier is locally unique. Legg & Payne Expires 25 August 2003 [Page 3] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 The Unique Identifier for an entry is held in the entryUUID [LCUP] operational attribute. 5.2 Timestamps & Existence The timestamp for a replication primitive or directory data item is in the form of a Change Sequence Number (CSN) [ARCH]. The components of the CSN are, from most significant to least significant, a time in seconds, a change count, a Replica Identifier and a modification number. Notionally a CSN is associated with an entry's Relative Distinguished Name (the Name CSN), the reference to its superior entry (the Parent CSN) and each of its attribute values (including the distinguished values and operational attribute values), to record the time of the most recent action on that part of the entry. The entry itself has a CSN (the Entry CSN) asserting the most recent time at which the entry was added. An entry is permitted to be removed and then re-added at one or more directory servers. In this context re-adding an entry means reusing the Unique Identifier of a removed entry and does not refer to the case of reusing the RDN of a removed entry. The reuse of a Unique Identifier can arise by the explicit action of a directory administrator to restore an entry that was mistakenly removed. The mechanism by which an administrator adds an entry with a reused Unique Identifier is outside the scope of the X.500 and LDAP standards since the Unique Identifier of an entry is not a user modifiable attribute. Note that from the perspective of a consumer directory server of a partial area of replication, an entry may appear to be removed and added several times because modifications to the entry change whether the entry satisfies the replication agreement specification for the area of replication. Additionally, a deletion record is kept for each of the recently deleted entries (entry deletion records), attributes (attribute deletion records), or attribute values (value deletion records). A deletion record contains a CSN and asserts that the associated directory object no longer existed at the particular time. 5.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. A single update operation will decompose into one or more primitives. Each directory server maintains a replication log, in which are Legg & Payne Expires 25 August 2003 [Page 4] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 stored the replication primitives resulting from user updates performed locally and the replication primitives received from other directory servers during replication sessions. 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. 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. The p-add-entry(uid, csn, superior, rdn) primitive is used to describe the addition of a new entry with minimal contents. The superior argument contains the Unique Identifier of the immediate superior entry of the added entry. The rdn argument contains the Relative Distinguished Name of the added entry. The p-move-entry(uid, csn, superior) primitive is used to describe the moving of an entry to a new immediate superior in the DIT. The superior argument contains the Unique Identifier of the new superior entry. The p-rename-entry(uid, csn, rdn) primitive is used to describe a change to the Relative Distinguished Name of an entry. The rdn argument contains the new RDN for the entry. The p-remove-entry(uid, csn) primitive is used to describe the removal of an entry. The p-add-attribute-value(uid, csn, desc, value) primitive is used to describe the addition of a single attribute value to an entry. The desc argument is an AttributeDescription containing the attribute type of the value and zero, one or more attribute options, and the value argument contains the attribute value. The p-remove-attribute-value(uid, csn, desc, value) primitive is used to describe the removal of a single attribute value from an entry. The desc argument is an AttributeDescription containing the attribute type of the value and zero, one or more attribute options, and the value argument contains the attribute value. The p-remove-attribute(uid, csn, desc) primitive is used to describe the removal of all values of an attribute with specific attribute options from an entry. The desc argument is an AttributeDescription Legg & Payne Expires 25 August 2003 [Page 5] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 containing the attribute type of the removed attribute with zero, one or more attribute options. These primitives reflect the intended final state of an update operation rather than the specific changes required to achieve that state. 5.4 Lost & Found As a result of conflicting updates at two or more master directory servers, an entry may be left with a reference to a non-existent superior entry. Such an entry is called an orphaned entry. When this situation arises, the directory server creates a glue entry for the missing superior entry. This glue entry is made a subordinate of the specially nominated Lost & Found entry and the orphaned entry becomes a subordinate of the glue superior entry (see Section 6.3.2). Entries that exist in the Lost & Found subtree can still be modified by actions of the replication protocol since entries are identified by Unique Identifiers in the protocol, independent of their position in the global DIT. Entries will also be explicitly moved to become immediate subordinates of the Lost & Found entry to prevent the formation of a loop in the superior-subordinate relationships in the DIT. This situation can only arise through conflicting move entry operations at two or more master directory servers. Entries that exist under the Lost & Found entry are able to be returned to a suitable position in the DIT by an administrator or user with appropriate access rights. 6. Replication Procedures The procedures defined in this section ensure the consistent and correct application of the results of DAP, LDAP or DSP operations across all replicating directory servers. 6.1 Processing LDAP, DAP or DSP Operations on the DIT A successful DAP, LDAP or DSP operation applied to a part of the DIT subject to a replication agreement will create or replace one or more CSNs on an entry or its contents, create zero, one or more deletion records referencing the entry or its contents, and put one or more replication primitives into the replication log in preparation for sending during subsequent replication sessions. The CSNs, deletion Legg & Payne Expires 25 August 2003 [Page 6] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 records and replication primitives generated from an operation MUST be atomic with that operation. That is, either the operation succeeds, CSNs are revised, deletion records are stored and replication primitives are added to the replication log, or the operation fails, no CSNs are revised, no deletion records are stored and no replication primitives are added to the replication log. In all cases, all current error conditions (i.e. reasons for rejecting an LDAP, DAP or DSP update operation) remain. All the CSNs generated from a single update operation MUST use the same time, change count and Replica Identifier. The modification number is permitted to vary but MUST be assigned such that when the CSNs resulting from the operation, including those in the deletion records, are compared to the CSNs resulting from any other operation they are all strictly greater than or all strictly less than those other CSNs (i.e. in a global CSN ordering of the primitives resulting from all operations the primitives of each operation MUST be contiguous in that ordering). In order for the update to be consistently applied when replicated to other directory servers the CSNs generated during that update must generally be greater than any pre-existing CSNs on the updated entry's contents. It is expected that directory servers will normally use the current time according to their system clocks in generating the CSNs for an operation. However in an environment where directory server clocks are not necessarily synchronized the current time may be older than existing CSNs on entry contents. The constraints the new CSNs MUST satisfy with respect to pre-existing CSNs on entry data are covered in the sections on each type of update operation. The Update Reconciliation Procedures allow a directory server to generate CSNs in advance of its current time to satisfy the constraints and proceed with the update. The LDUP Update Vector mechanism imposes the additional constraint that the CSN generated for an update operation MUST also be greater than the highest CSN generated by the directory server that has already been seen by any other directory server. An implementation that generates successively greater CSNs for each operation will satisfy this constraint. The following sections describe the additional actions carried out in processing each standard type of update operation in order to support replication. If a directory server implementation supports other non-standard update operations or alternative non-directory update protocols then, in so far as these operations alter replicated directory data, the implementation MUST generate and apply CSNs, deletion records and replication primitives that accurately reflect any change. Legg & Payne Expires 25 August 2003 [Page 7] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 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, deletion records and replication primitives 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. 6.1.1 Add Entry The LDAP Add operation [LDAPOP] or DAP addEntry operation [X511] is used to add a leaf entry to the DIT. A successful request will generate a CSN for the added entry. The CSN on the entry's RDN, the CSN on the entry's superior reference, and the CSN on each distinguished and non-distinguished value of the added entry are set to this same value. A successful request will also generate and add to the replication log, a p-add-entry primitive, and a p-add-attribute-value primitive for each of the non-distinguished attribute values of the added entry. There are no separate p-add-attribute-value primitives generated for the distinguished values of the entry. The generated primitives use the CSN of the added entry. The applicable values include any operational attribute values automatically generated by the directory server, e.g. for creatorsName and createTimestamp. Note that the value of the createTimestamp attribute does not necessarily correspond to the time component of the CSN associated with that value. The superior argument of the p-add-entry primitive contains the Unique Identifier of the immediate superior entry of the added entry. The rdn argument of the p-add-entry primitive contains the Relative Distinguished Name of the created entry except that the value of the entryUUID attribute, if distinguished, is omitted from the rdn argument. The Unique Identifier generated for an entry created by a user request is required to be globally unique for all time, so there ought not be a pre-existing entry deletion record for the same Unique Identifier. However it is recognized that, in practice, directory administrators may need to restore a deleted entry using its original Unique Identifier (the mechanism used to achieve this is undefined and outside the scope of this specification). In this case the CSN for the entry MUST be generated such that it is greater than or equal to the CSN of any existing entry, attribute or value deletion records, and greater than any of the CSNs contained in an existing glue entry, for the same Unique Identifier. Legg & Payne Expires 25 August 2003 [Page 8] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 6.1.2 Remove Entry The LDAP Delete operation [LDAPOP] or DAP removeEntry operation [X511] is used to remove a leaf entry from the DIT. If the request succeeds then an entry deletion record containing the Unique Identifier of the removed entry is stored and a p-remove-entry primitive is generated and added to the replication log. The primitive uses the same arguments as the entry deletion record. The CSN for the entry deletion record MUST be generated such that it is greater than the entry CSN of the removed entry. 6.1.3 Modify Entry The LDAP Modify operation (ModifyRequest) [LDAPOP] or DAP modifyEntry operation [X511] is used to perform a series of one or more modifications to an entry. If the request succeeds then zero, one or more new values with CSNs are added to the entry contents, zero, one or more value or attribute deletion records are stored, and zero, one or more p-add-attribute-value, p-remove-attribute-value or p-remove-attribute primitives are generated and added to the replication log. As the sequence of modifications in the modify operation are applied in order, the primitives they generate are assigned CSNs with strictly increasing modification numbers. The modification numbers need not be consecutive. The modifications described by the modification argument of the LDAP ModifyRequest generate replication primitives as follows: 1) The add alternative generates a p-add-attribute-value primitive, including any attribute options, for each of the added attribute values 2) The delete alternative with no listed values generates a p-remove-attribute primitive for the removed attribute type, including any attribute options. 3) The delete alternative with listed values generates a p-remove-attribute-value primitive, including any attribute options, for each of the removed values. 4) The replace alternative first generates a p-remove-attribute primitive for the removed attribute type, including any attribute options. A p-add-attribute-value primitive is then generated, including any attribute options, for each of the added values. Legg & Payne Expires 25 August 2003 [Page 9] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 The replace alternative with no attribute values generates only the p-remove-attribute primitive. For cases 2) and 4), it is not necessary to generate a p-remove-attribute-value primitive for each of the values actually removed because the p-remove-attribute primitive implicitly includes the effects of any such p-remove-attribute-value primitives (it applies to all possible values). The modifications described by the changes argument of the X.500 modifyEntry operation generate replication primitives as follows: 5) The addAttribute and addValues alternatives generate a p-add-attribute-value primitive for each of the added attribute values. These two alternatives are equivalent from the point of view of URP since there is no CSN associated specifically with the attribute type. 6) The removeAttribute alternative generates a p-remove-attribute primitive for the removed attribute type. It is not necessary to generate a p-remove-attribute-value primitive for each of the values actually removed because the p-remove-attribute primitive implicitly includes the effects of any such p-remove-attribute-value primitives (it applies to all possible values). 7) The removeValues alternative generates a p-remove-attribute-value primitive for each of the removed values. 8) The alterValues alternative first generates a p-remove-attribute-value primitive for each of the old values. Secondly, a p-add-attribute-value primitive is generated for each of the new values. 9) The resetValues alternative generates a p-remove-attribute-value primitive for each value actually removed. The following additional actions apply to each of the cases 1) to 9) above. a) Each generated primitive is added to the replication log. b) Each time a p-remove-attribute-value primitive is generated a value deletion record with the same arguments is stored. c) Each time a p-remove-attribute primitive is generated an attribute deletion record with the same arguments is stored. Legg & Payne Expires 25 August 2003 [Page 10] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 d) Each time a p-add-attribute-value primitive is generated the CSN from the primitive is associated with the corresponding value added to the entry. A successful ModifyRequest or modifyEntry operation will also result in changes to operational attributes of the entry. Like the explicit modifications to user attributes, CSNs are given to new operational attribute values, deletion records are stored for operational attribute values that are removed, and in both cases appropriate replication primitives are generated and added to the replication log. The processing in each case depends on the semantics of the particular operational attribute type and can be deduced by considering an equivalent explicit modification request. In particular, the revision of the modifyTimestamp and modifiersName attributes is treated like the ModifyRequest replace alternative. Note that the value of the modifyTimestamp attribute does not necessarily correspond to the time component of the CSN associated with that value. The entryUUID operational attribute SHALL NOT be modified. Consequently, attribute and value deletion records, and p-remove-attribute and p-remove-attribute-value primitives are never generated for the entryUUID attribute type. The CSNs generated by a modify operation MUST be greater than the CSN of any pre-existing attribute value that is removed, greater than or equal to the CSN of any pre-existing attribute deletion record or value deletion record applying to an added attribute value, and greater than or equal to the CSN of the entry. Whenever a new value is added to the entry contents any value deletion record for the same entry, AttributeDescription and attribute value MAY be discarded. 6.1.4 Modify DN The LDAP Modify DN operation [LDAPOP] and DAP modifyDN operation [X511] are used to change the Relative Distinguished Name of an entry and/or to move an entry to a new superior in the DIT. If the entry is successfully moved to a new superior in the DIT then the CSN on the entry's superior reference is replaced and a p-move-entry primitive is generated and added to the replication log. The CSN for this primitive is the new CSN on the entry's superior reference and the superior argument contains the Unique Identifier of the new immediate superior entry. If the entry's RDN is successfully changed then the CSN on the entry's RDN is replaced and a p-rename-entry primitive is generated Legg & Payne Expires 25 August 2003 [Page 11] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 and added to the replication log. The CSN for this primitive is the new CSN on the entry's RDN and the rdn argument contains the new RDN of the entry. A p-remove-attribute-value primitive is generated and added to the replication log, and a value deletion record with the same arguments is stored, for each of the formally distinguished attribute values removed from the entry as a consequence of the deleteOldRDN parameter (modifyDN) or deleteoldrdn parameter (ModifyDNRequest) being set to true. An entryUUID attribute value that is made non-distinguished SHALL NOT be removed from the entry regardless of the deleteOldRDN or deleteoldrdn flag and SHALL NOT have a corresponding value deletion record or a p-remove-attribute-value primitive. If the CSN on the entry's superior reference is revised then the new value MUST be greater than the previous value. If the CSN on the entry's RDN is revised then the new value MUST be greater than the previous value of the CSN on the RDN. The CSNs for any p-remove-attribute-value primitives MUST be greater than the CSNs on the attribute values removed. 6.2 Sending Replication Primitives Each time a replication session is invoked, the supplier directory server sends replication primitives for updates known to the supplier but not yet known to the consumer directory server. The supplier uses the Update Vector of the consumer to determine what to send. Conceptually, the supplier scans the replication log and sends those primitives that are within the scope of the replication agreement with the consumer, and which have a CSN that is greater than the CSN for the corresponding identified replica in the consumer's Update Vector. Replication primitives that apply to entries or entry contents which are outside the scope of the replication agreement MUST NOT be sent. The consumer's Update Vector has a CSN for each replica in the replica group. Each CSN held by the supplier contains a Replica Identifier. When a CSN from a replication primitive held by the supplier is compared to the consumer's Update Vector it is compared to the single CSN in the consumer's Update Vector that has the same Replica Identifier as the CSN from the replication primitive. 6.3 Processing Replication Primitives on the DIT Each replication primitive received from another directory server during a replication session that is within the scope of the replication agreement is processed against the DIT. Replication Legg & Payne Expires 25 August 2003 [Page 12] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 primitives outside the scope of the replication agreement are rejected. This section defines some commonly used sub-procedures and the algorithms for processing each of the primitives. These algorithms are not intended to be implemented verbatim but instead describe the behaviour an LDUP implementation MUST exhibit externally. Alternative equivalent processing logic is permitted. Components of primitives, entries, attributes and values are referenced with the `.' operator. In particular the notation X.csn refers to the CSN of the directory object X. The operators, < and > when applied to CSNs, use the convention of CSNs becoming greater with the progression of time, so older CSNs are less than younger CSNs. In the case where the CSN for object X has been discarded through the purging mechanism, X.csn is assumed to have the least possible CSN value. In some of the procedures a CSN will be explicitly purged. An implementation MAY instead keep the CSN but set it to some value that is old enough for it to be eligible for purging (e.g. the least possible CSN value) without affecting the correctness of the procedures. For an entry, E, the notation E.rdn refers to the entry's Relative Distinguished Name, E.dn refers to the entry's Distinguished Name, and E.superior refers to the Unique Identifier of the entry's immediate superior in the DIT. 6.3.1 Saving Deletion Records It is necessary for a directory server to store deletion records to remember that some entry, attribute or attribute value has been deleted, for a period after the processing of the update operation or replication primitive causing the deletion. Value deletion records have the same parameters as the p-remove-attribute-value primitive. The StoreValueDeletion procedure creates a value deletion record from the actual arguments and stores it for later access by the various primitive processing procedures. When an attribute value is added to an entry, a value deletion record for the same entry, AttributeDescription and value, and with an older CSN, MAY be discarded. Attribute deletion records have the same parameters as the p-remove-attribute primitive. The StoreAttributeDeletion procedure creates an attribute deletion record from the actual arguments and stores it for later access. When an attribute deletion record is stored, any value deletion records for the same entry and Legg & Payne Expires 25 August 2003 [Page 13] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 AttributeDescription, and with equal or older CSNs, MAY be discarded. Entry deletion records have the same parameters as the p-remove-entry primitive. The StoreEntryDeletion procedure creates an entry deletion record from the actual arguments and stores it for later access. When an entry deletion record is stored any value deletion records and attribute deletion records for the same entry, and with equal or older CSNs, MAY be discarded. Since the deletion records have the same components as their associated remove primitives an implementation MAY choose to use the same internal structures for both. 6.3.2 Glue Entries Entries are permitted to be re-added and this can lead to situations where applicable primitives are received in the period after an entry is removed but before the arrival of the notification of it being re-added. In these cases a glue entry is created for the Unique Identifier to preserve relevant updates in the event that a p-add-entry primitive with an older CSN is later received for the same entry. A glue entry is upgraded to a normal entry by a subsequent p-add-entry primitive. A glue entry with no subordinate entries and containing only CSNs (on itself or its component parts) that are eligible to be purged MAY be removed. The CreateGlueEntry function is called when required to create a glue entry as a subordinate of Lost & Found. CreateGlueEntry takes a single parameter which is the Unique Identifier for the glue entry. The Unique Identifier, in the form of the entryUUID attribute, also becomes the RDN for the glue entry. No CSNs are associated with the entry, the entry's superior reference, or the entry's name (or equivalently they are set to the least possible CSN value). 6.3.3 Generating Change Sequence Numbers There are circumstances where conflicts arise in the processing of a replication primitive. It is necessary in these cases for the directory server processing the primitive to make corrective changes and emit additional primitives to ensure that all other directory servers reach the same consistent state. The GenerateNextCSN function is used to obtain a CSN for a corrective change. The AddToLog procedure is used to add a replication primitive for the corrective change to the replication log. Legg & Payne Expires 25 August 2003 [Page 14] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 As is the case for CSNs generated from DAP, DSP or LDAP operations, the CSN for the corrective change is typically generated from the current clock time of the directory server. The conditions imposed for the correct operation of the LDUP Update Vector MUST also be satisfied. GenerateNextCSN takes a single CSN parameter. In addition to all other conditions, the CSN generated by the function MUST be greater than this parameter. Since the CSN parameter passed to GenerateNextCSN is always an actual CSN from some directory object stored in the local directory server, an implementation MAY choose to allocate CSNs from an incrementing internal CSN register that is reset after each replication session to a value greater than the largest CSN seen so far, and thereby be safely able to disregard the parameter to GenerateNextCSN. The AddToLog procedure adds the replication primitive described by its argument to the replication log. 6.3.4 Comparison of Attribute Descriptions and Values Two AttributeDescription arguments are equal if they have the same attribute type and the same set of subtyping attribute options. Attribute options that specify a transfer encoding (e.g. ";binary") are ignored in the comparison of AttributeDescription arguments. An attribute type that is a subtype of another attribute type in an attribute hierarchy as defined in [X501] is treated as an unrelated and distinct type by the procedures in this document. For example, "cn" and "cn;binary" are equal, "cn" and "cn;lang-en" are not equal, and "cn" and "name" are not equal. In some procedures an AttributeDescription from a replication primitive or deletion record is compared to the attribute type from an AttributeTypeAndValue. In these cases, the two arguments are equal if and only if the attribute types are the same and the AttributeDescription contains no subtyping attribute options. Values in primitives, in deletion records or in entries are compared using the equality matching rule for the associated attribute type where that type is permitted to be multi-valued. This means that two values that are considered equal may nonetheless have minor differences. For example, two commonName values may be equal, but use different letter case and have different numbers of leading or trailing spaces. Whenever a CSN for some stored value is refreshed, the stored value itself is also refreshed using the value from the primitive, if the stored value and primitive value are not identical. Legg & Payne Expires 25 August 2003 [Page 15] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 For the purposes of the procedures described in this document, two values are considered identical if they compare TRUE according to the allComponentsMatch matching rule defined in [CMR]. The purpose of refreshing stored values is so that all directory servers converge to the exact same abstract value. Each server is, of course, free to represent the value using any transfer encoding defined for the attribute's syntax. Compared values for a single-valued attribute type are all considered to be equal even though they may be significantly different according to that attribute type's equality matching rule. In effect, the equality operator, `=', in the following procedures is unconditionally true when used to compare values of a single-valued attribute type. Whenever a CSN for the value of a single-valued attribute is refreshed the value is also refreshed using the value from the primitive. One significant consequence is that an entry whose RDN contains a value of a single-valued attribute type is effectively renamed by a p-add-attribute-value primitive with a more recent value for the attribute type. A stored value that is replaced by the value from a primitive retains its distinguished or non-distinguished status. This includes replaced values of single-valued attribute types. Compared values for an attribute type that does not have an equality matching rule are all considered to be not equal. In effect, the equality operator is unconditionally false when used to compare values of an attribute type without an equality matching rule. This means that stored values and values in a primitive are never considered equal for such an attribute type, so duplicate values with different CSNs could accumulate in the attribute and the p-remove-attribute-value primitive will be ineffectual. However, the only permitted changes to an attribute without an equality matching rule are to add, remove or replace the entire attribute. Therefore, except when values are first added to an attribute, there will be a p-remove-attribute primitive immediately prior to the p-add-attribute-value primitives for the added values, and only the values of the latest (by CSN) add or replace will appear in the attribute. It is possible that values could be simultaneously initially added to the previously non-existent attribute at two separate replicas. If the clients choose to add the attribute using the add alternative of the modification argument of the LDAP ModifyRequest then both sets of values (potentially including duplicates) will eventually appear in the attribute. If the clients choose to add the attribute using the replace alternative of the modification argument then only the values from the client update with the latest CSN will eventually appear in the attribute. Legg & Payne Expires 25 August 2003 [Page 16] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 Note that values of an attribute type without an equality matching rule cannot be distinguished. 6.3.5 Entry Naming Independent changes at two or more directory servers can lead to the situation of two distinct entries having the same name. The procedure, CheckUniqueness(E, S, R), takes an entry and determines whether it is uniquely named. If not, it disambiguates the names of the entries by adding each conflicting entry's Unique Identifier to its RDN (i.e. making the value of its entryUUID attribute distinguished). The procedure CheckUniqueness is called in each circumstance where the Relative Distinguished Name of an entry might conflict with another entry, either because the entry has been renamed or because it has been moved to a new superior. An entry can be renamed directly by a p-rename-entry primitive, or as a side-effect of other primitives causing changes to distinguished values. While each move or rename of an entry potentially causes a conflict with some other entry already having the new Distinguished Name, it also potentially removes a previous conflict on the old Distinguished Name. To enable the CheckUniqueness function to remove the Unique Identifier from an entry's RDN when it is no longer needed, the old name for an entry is passed through the second and third parameters. The parameter, S, is the Unique Identifier of the old superior entry of E, and the parameter, R, is the old RDN of E. CheckUniqueness ignores distinguished entryUUID values when comparing entry RDNs. The function BaseRDN(rdn) returns its argument minus any distinguished entryUUID values, to support these comparisons. CheckUniqueness(E, S, R) { make E.uid non-distinguished IF there exists exactly one subordinate entry, C, of S where BaseRDN(C.rdn) = BaseRDN(R) make C.uid non-distinguished IF E.rdn is empty make E.uid distinguished ELSE IF there exists a subordinate entry, C, of E.superior where E <> C AND BaseRDN(C.rdn) = BaseRDN(E.rdn) { make C.uid distinguished make E.uid distinguished } } Legg & Payne Expires 25 August 2003 [Page 17] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 Because updates are performed in isolation at multiple directory servers in a multimaster configuration it is possible to encounter a situation where there is a request to delete a distinguished value in an entry. The recommended practice in these circumstances is to remove the distinguished value and call CheckUniqueness to correct any resulting name conflicts. An implementation MAY instead reassert the existence of the distinguished value with a more recent CSN to avoid altering the entry's RDN. This option is only available to updateable replicas. Read-only replicas MUST remove the distinguished value. The function ProtectDistinguished() returns true for an updateable part of the DIT in a directory server that implements this option, and false otherwise. Directory servers exercising this option MUST generate a p-rename-entry primitive (as shown in the procedures) so that other directory servers are guaranteed to also reassert the distinguished value. Directory servers that implement the option will correctly interwork with servers that do not. The primitives p-add-entry and p-rename-entry contain common elements that are applied to the Relative Distinguished Name of an entry in the same way. This common processing is described in the RenameEntry procedure. The parameters to this procedure are the entry, E, and P, the p-add-entry or p-rename-entry primitive specifying the new RDN. The procedure assumes that the entry does not currently contain any distinguished values. It is the responsibility of the calling procedure to first reset any pre-existing distinguished values to non-distinguished. The procedure then resets the CSNs and sets the distinguished flags for existing values and adds distinguished values if necessary. The CSN for the entry's RDN, as distinct from the CSNs on each of the distinguished values making up the RDN, is also set. RenameEntry(E, P) { IF ProtectDistinguished() C := P.csn FOREACH AttributeTypeAndValue, N, in P.rdn IF there exists an attribute value, V, in E of type N.type where V = N.value { IF P.csn > V.csn { replace V with N.value if they are not identical V.csn := P.csn } make V distinguished } ELSE IF no attribute deletion record (uid, csn, desc) exists where (uid = P.uid AND desc = N.type AND csn > P.csn) Legg & Payne Expires 25 August 2003 [Page 18] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 AND no value deletion record (uid, csn, desc, value) exists where (uid = P.uid AND desc = N.type AND value = N.value AND csn > P.csn) { V := N.value add V to E as a distinguished value V.csn := P.csn } ELSE IF ProtectDistinguished() { FOREACH attribute deletion record (uid, csn, desc) where (uid = P.uid AND desc = N.type) IF csn > C C := csn FOREACH value deletion record (uid, csn, desc, value) where (uid = P.uid AND desc = N.type AND value = N.value) IF csn > C C := csn } E.rdn.csn := P.csn IF ProtectDistinguished() AND C > P.csn { csn := GenerateNextCSN(C) AddToLog(p-rename-entry(P.uid, csn, P.rdn)) RenameEntry(E, p-rename-entry(P.uid, csn, P.rdn)) } } 6.3.6 Processing Add Attribute Value Primitive This section details the algorithm for processing the p-add-attribute-value (P.uid, P.csn, P.desc, P.value) primitive, which describes the addition of a single attribute value. If the attribute type of P.desc is the entryUUID attribute type then the primitive MUST be rejected. IF no value deletion record (uid, csn, desc, value) exists where (uid = P.uid AND desc = P.desc AND value = P.value AND csn > P.csn) AND no attribute deletion record (uid, csn, desc) exists where (uid = P.uid and desc = P.desc 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 does not exist E := CreateGlueEntry(P.uid) Legg & Payne Expires 25 August 2003 [Page 19] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 IF P.csn >= E.csn IF attribute value, V, of attribute P.desc where V = P.value exists in E { IF P.csn > V.csn { V.csn := P.csn R := E.rdn replace V with P.value if they are not identical IF V is distinguished AND P.desc is a single-valued attribute CheckUniqueness(E, E.superior, R) } } ELSE { V := P.value Add V to E as a non-distinguished attribute value V.csn := P.csn } } 6.3.7 Processing Remove Attribute Value Primitive This section details the algorithm for processing the p-remove-attribute-value (P.uid, P.csn, P.desc, P.value) primitive, which describes the removal of a single attribute value. If the attribute type of P.desc is the entryUUID attribute type then the primitive MUST be rejected. IF no value deletion record (uid, csn, desc, value) exists where (uid = P.uid AND desc = P.desc AND value = P.value AND csn >= P.csn) AND no attribute deletion record (uid, csn, desc) exists where (uid = P.uid AND desc = P.desc 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 attribute P.desc where V = P.value, exists in E { IF P.csn > V.csn IF V is distinguished Legg & Payne Expires 25 August 2003 [Page 20] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 IF ProtectDistinguished() { csn := GenerateNextCSN(P.csn) AddToLog(p-rename-entry(P.uid, csn, E.rdn)) RenameEntry(E, p-rename-entry(P.uid, csn, E.rdn)) } ELSE { R := E.rdn remove value V CheckUniqueness(E, E.superior, R) StoreValueDeletion (P.uid, P.desc, P.value, P.csn) } ELSE { remove value V StoreValueDeletion (P.uid, P.desc, P.value, P.csn) } } ELSE StoreValueDeletion (P.uid, P.desc, P.value, P.csn) } ELSE StoreValueDeletion (P.uid, P.desc, P.value, P.csn) The presence of a younger deletion record for the entry, attribute or value provides a convenient test for whether the p-remove-attribute-value primitive needs to be processed at all. If the value exists to be removed then there cannot be a deletion record affecting it that has a younger CSN. If there is a younger deletion record than the primitive then there cannot be an older value to remove. 6.3.8 Processing Remove Attribute Primitive This section details the algorithm for processing the p-remove-attribute (P.uid, P.csn, P.desc) primitive, which describes the removal of all attribute values of attribute P.desc. If the attribute type of P.desc is the entryUUID attribute type then the primitive MUST be rejected. IF no attribute deletion record (uid, csn, desc) exists where (uid = P.uid AND desc = P.desc AND csn >= P.csn) AND no entry deletion record (uid, csn) exists where Legg & Payne Expires 25 August 2003 [Page 21] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 (uid = P.uid AND csn >= P.csn) IF entry, E, with uid = P.uid exists { IF P.csn > E.csn { FOREACH attribute value, V, of attribute P.desc in E (if any) IF P.csn > V.csn IF V is distinguished IF ProtectDistinguished() { csn := GenerateNextCSN(P.csn) AddToLog(p-rename-entry(P.uid, csn, E.rdn)) RenameEntry(E, p-rename-entry(P.uid, csn, E.rdn)) } ELSE { R := E.rdn remove value V CheckUniqueness(E, E.superior, R) } ELSE remove value V StoreAttributeDeletion (P.uid, P.desc, P.csn) } } ELSE StoreAttributeDeletion (P.uid, P.desc, P.csn) 6.3.9 Processing Add Entry Primitive This section details the algorithm for processing the p-add-entry (P.uid, P.csn, P.superior, P.rdn) primitive, which describes the addition of an entry. The CSN on an entry records the time of the latest p-add-entry primitive for the Unique Identifier. In normal circumstances there will only ever be one p-add-entry primitive associated with an entry. The entry CSN MAY be discarded when it becomes eligible to be purged according to the Purge Vector. IF 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 { R := E.rdn Legg & Payne Expires 25 August 2003 [Page 22] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 S := E.superior E.csn := P.csn FOREACH attribute, A, in E, except entryUUID FOREACH attribute value, V, of A IF V.csn < P.csn remove value V CheckUniqueness(E, S, R) process P according to p-rename-entry(P.uid, P.csn, P.rdn) process P according to p-move-entry(P.uid, P.csn, P.superior) } } ELSE { create entry E E.csn := P.csn E.uid := P.uid E.uid.csn := P.csn IF an entry with uid = P.superior does not exist CreateGlueEntry(P.superior) E.superior = P.superior E.superior.csn := P.csn RenameEntry(E, P) CheckUniqueness(E, E.superior, E.rdn) } 6.3.10 Processing Remove Entry Primitive This section details the algorithm for processing the p-remove-entry (P.uid, P.csn) primitive, which describes the removal of an entry. If the target entry has attribute values with CSNs greater than the primitive's CSN, a superior reference with a greater CSN, or if it has any subordinate entries, it becomes a glue entry instead of being removed. It is also moved to Lost & Found, unless it has a CSN for its superior reference that is greater than the CSN of the p-remove-entry. IF 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 E.superior.csn >= P.csn OR any value, V, with csn >= P.csn exists OR E has subordinates Legg & Payne Expires 25 August 2003 [Page 23] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 { R := E.rdn S := E.superior make E a glue entry purge E.csn IF E.superior.csn < P.csn { E.superior := LOST_AND_FOUND purge E.superior.csn } IF E.rdn.csn < P.csn purge E.rdn.csn FOREACH attribute, A, in E, except entryUUID FOREACH attribute value, V, of A IF V.csn < P.csn remove value V CheckUniqueness(E, S, R) } ELSE remove entry E StoreEntryDeletion (P.uid, P.csn) } } ELSE StoreEntryDeletion (P.uid, P.csn) 6.3.11 Processing Move Entry Primitive This section details the algorithm for processing the p-move-entry (P.uid, P.csn, P.superior) primitive, which describes the moving of an entry to a new immediate superior in the DIT. If the new superior specified by the primitive does not exist, the entry being moved becomes a subordinate of a glue entry subordinate to Lost & Found. If the new superior specified by the primitive is a direct or indirect subordinate of the entry being moved, the entry is moved to Lost & Found instead. IF no entry deletion record (uid, csn) exists where (uid = P.uid AND csn > P.csn) { IF entry, E, with uid = P.uid does not exist E := CreateGlueEntry(P.uid) IF P.csn > E.superior.csn { R := E.rdn O := E.superior IF entry, S, with uid = P.superior does not exist Legg & Payne Expires 25 August 2003 [Page 24] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 S := CreateGlueEntry(P.superior) IF S is not in the subtree of E { E.superior := P.superior E.superior.csn = P.csn } ELSE { E.superior := LOST_AND_FOUND; E.superior.csn := GenerateNextCSN(P.csn) AddToLog(p-move-entry (P.uid, E.superior.csn, LOST_AND_FOUND)) } CheckUniqueness(E, O, R) } } 6.3.12 Processing Rename Entry Primitive This section details the algorithm for processing the p-rename-entry (P.uid, P.csn, P.rdn) primitive, which describes a change to the Relative Distinguished Name of an entry. A p-rename-entry primitive that is older than current name of an entry is not simply ignored since it may contain attribute values that would have been added to the entry had the primitives arrived in CSN order. These extra values would now be non-distinguished. IF no entry deletion record (uid, csn) exists where (uid = P.uid AND csn >= P.csn) { IF entry, E, with uid = P.uid does not exist E := CreateGlueEntry(P.uid) IF P.csn > E.rdn.csn { R := E.rdn FOREACH distinguished attribute value, V, in entry E make V non-distinguished RenameEntry(E, P) CheckUniqueness(E, E.superior, R) } ELSE FOREACH AttributeTypeAndValue, N, in P.rdn { IF there exists an attribute value, V, in E of type N.type AND V = N.value { IF P.csn > V.csn Legg & Payne Expires 25 August 2003 [Page 25] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 { replace V with N.value if they are not identical V.csn := P.csn } } ELSE { IF no value deletion record (uid, csn, desc, value) exists where (uid = P.uid AND desc = N.type AND value = N.value AND csn > P.csn) AND no attribute deletion record (uid, csn, desc) exists where (uid = P.uid AND desc = N.type AND csn > P.csn) { V := N.value Add V to E V.csn := P.csn } } } } 7. Security Considerations The procedures described in this document are not subject to access controls on the directory data items being modified. Specifically, the update primitives received from a peer replica are applied without regard for access controls. This is necessary so that access control information can also be replicated. An LDUP enabled server entering into a multi-master replication agreement with a peer server is enabling joint authority and responsibility for some part of the directory data. A replica must trust that the other replicas are properly enforcing access controls on user update requests, but this trust extends only as far as described by the replication agreements currently in place. The replication agreement acts as a surrogate for access controls between peer replicas. Replication primitives that are outside the scope of the agreement are rejected. Authentication of peer replica LDUP sessions and the security of the exchange of replication primitives through the LDUP protocol are outside the scope of this document and are described elsewhere. Simultaneous updates at different replicas can result in two entries, corresponding to two different real world entities, having the same distinguished name. The Update Reconciliation Procedures disambiguate these two names by appending the respective Unique Legg & Payne Expires 25 August 2003 [Page 26] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 Identifiers to the entries' RDNs. This action will disable any access controls based on an entry's specific DN or RDN. Disabling such an access control may have the effect of granting a permission that was explicitly denied. Since a Unique Identifier is required to be globally unique for all time, appending a Unique Identifier to the RDN cannot unintentionally enable access controls applying to a different real world entity. It is sufficient when disambiguating entry RDNs to append the UID to only one of a pair of entries ending up with the same name. The Update Reconciliation Procedures require both entries to have their UID appended to minimize the chance that either entry will gain permissions intended for the other. This is based on the assumption that most access controls will grant permissions rather than deny permissions. 8. Acknowledgments The authors would like to thank Suellen Faulks and Tony Robertson from Telstra and Mark Ennis from Adacel Technologies who contributed to the design and verification of the procedures described in this document. The authors would also like to thank the members of the LDUP architecture group for their input into the refinement of the design. 9. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [LDAPOP] M. Wahl, M., Kille, S. and T. Howes, "Lightweight Directory Access Protocol (v3)", RFC 2251, December 1997. [LDAP] Hodges, J. and R. Morgan, "Lightweight Directory Access Protocol (v3): Technical Specification", RFC 3377, September 2002. [ARCH] Merrells, J., Reed, E. and U. Srinivasan, "LDAP Replication Architecture", draft-ietf-ldup-model-xx.txt, a work in progress, March 2001. [LCUP] Megginson, R., Smith, M., Natkovich, O. and J. Parham, "LDAP Client Update Protocol", draft-ietf-ldup-lcup-xx.txt, a work in progress, November 2001. Legg & Payne Expires 25 August 2003 [Page 27] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 [CMR] Legg, S., "LDAP & X.500 Component Matching Rules", draft-legg-ldapext-component-matching-xx.txt, a work in progress, October 2002. [X501] ITU-T Recommendation X.501 (08/97) | ISO/IEC 9594-2:1998, Information technology - Open Systems Interconnection - The Directory: Models [X511] ITU-T Recommendation X.511 (08/97) | ISO/IEC 9594-3:1998, Information technology - Open Systems Interconnection - The Directory: Abstract service definition 10. Informative References [BCP-11] Hovey, R. and S. Bradner, "The Organizations Involved in the IETF Standards Process", BCP 11, RFC 2028, October 1996. [X500] ITU-T Recommendation X.500 (08/97) | ISO/IEC 9594-1:1998, Information technology - Open Systems Interconnection - The Directory: Overview of concepts, models and services 11. Copyright Notice Copyright (C) The Internet Society (2003). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING Legg & Payne Expires 25 August 2003 [Page 28] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 12. Authors' Addresses Steven Legg Adacel Technologies Ltd. 250 Bay Street Brighton, Victoria 3186 AUSTRALIA Phone: +61 3 8530 7710 Fax: +61 3 8530 7888 EMail: steven.legg@adacel.com.au Alison Payne Telstra 21/242 Exhibition Street Melbourne, Victoria 3000 AUSTRALIA Phone: +61 3 9634 7620 EMail: alison.payne@team.telstra.com Appendix A - Changes From Previous Drafts A.1 Changes in Draft 01 Some of the terminology has been changed to better align with the terminology used in the LDUP architecture draft. Descriptions on the usage of CSNs have been revised to account for the extra modification number component. The semantics of re-added entries has been simplified so that only changes after the latest re-add are preserved instead of all those after the earliest re-add. This eliminates the need for Addition CSNs in the entry. It is anticipated that new replication primitives will be introduced to manage entries that come and go from partial replicas instead of using p-add-entry and p-remove-entry. Orphaned entries are no longer moved directly to Lost & Found. Instead a glue entry is created in Lost & Found for the missing superior and the orphaned entry becomes a subordinate of that. This Legg & Payne Expires 25 August 2003 [Page 29] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 change eliminates the need for explicit propagated primitives for moving orphaned entries to Lost & Found. Glue entries have also been used as the mechanism for saving primitives. There are no longer any references to saved primitives though the functionality is still present. The procedures for processing received replication primitives have been rearranged to follow a more consistent pattern where the presence of deletion records is tested first. A.2 Changes in Draft 02 Multimaster replication has been dropped as a work item for the next edition of X.500 so references to the proposed X.500 multimaster replication protocol have been removed. The treatment of distinguished values has been simplified. Previously an attempt to remove a distinguished value caused the value to be tagged distinguished-not-present. Now the distinguished value is removed, and if necessary, the Unique Identifier is made distinguished to avoid an empty RDN. Optionally, the value to be removed can be reasserted by emitting an explicit p-add-attribute-value primitive. The current draft is more implementation neutral. A replication log no longer figures prominently in the specification. The previous descriptions had the user updates generating replication primitives, which in turn were used to determine the CSNs and deletion records. The new descriptions have user updates generating CSNs and deletion records and the primitives are subsequently generated from them. A.3 Changes in Draft 03 The draft has been edited to make use of the key words "MUST", "SHOULD", "MAY", etc. The treatment of server maintained operational attributes has been clarified. An extra CheckUniqueness call has been added to the procedure for processing the p-add-entry primitive (Section 6.3.9) to cover the case where an entry is re-added. A loop through all of the values of an entry in the p-add-entry and p-remove-entry processing has been altered to explicitly skip the entryUUID operational attribute. No other changes have been made to the behaviour of the Update Legg & Payne Expires 25 August 2003 [Page 30] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 Reconciliation Procedures from Draft 02. The list of references has been expanded. The Security Considerations section has been added. A.4 Changes in Draft 04 A minor change made to the authors' details, otherwise only the dates have been revised. A.5 Changes in Draft 05 References to other LDUP drafts have been added. Notes have been added to Section 6.1.3 to explain why value deletion records are not required in those cases where attribute deletion records are also generated. In Section 6.2, how the supplier's CSNs are compared to the consumer's Update Vector has been clarified. In Section 6.3.4, the description on refreshing values whose CSN is revised has been tightened. The allComponentsMatch matching rule has been referenced as the definitive method for testing whether two equal values are also identical. In Section 6.3.4, text to describe the treatment of values whose attribute type does not have an equality matching rule has been added. The attribute type argument in replication primitives and deletion records has been replaced by an AttributeDescription argument. The replication primitive processing procedures have been revised to take account of attribute descriptions. These changes affect Section 5.3 and Section 6.3. RFC 2251 isn't clear about how subtyping attribute options apply to updates. For example, does a request to delete the cn attribute also delete the cn;foobar attribute ? This version of the URP document assumes that the answer is no. A yes answer will require more extensive changes to URP. A.6 Changes in Draft 06 All provisions for state-based implementations of URP have been removed. Replication primitives are now described as being generated Legg & Payne Expires 25 August 2003 [Page 31] INTERNET-DRAFT Update Reconciliation Procedures February 25, 2003 at the time a user update is processed rather than at some later time. Generation of primitives is now atomic with the user operation. Implementations are now required to send all primitives, including those superseded by later updates. Consequently, the rules governing superseding of primitives have been removed. Points in the procedures for processing replication primitives where corrective changes must be performed now have an explicit procedure, AddToLog, to create the primitives to be propagated to other servers. The presented order of the arguments in primitives and deletion records has been made uniform. A flaw in the logic for reasserting distinguished values was discovered and fixed. Reasserting just the value is insufficient to ensure eventual consistency. Some servers can potentially end up with the value being non-distinguished. It is necessary to reassert the entire RDN to avoid this problem. The change does not affect implementations that follow the recommended practice of simply deleting distinguished values when required. The draft has been reformatted to conform to recent and proposed RFC editorial policy. A.7 Changes in Draft 07 RFC 3377 replaces RFC 2251 as the reference for LDAP. Legg & Payne Expires 25 August 2003 [Page 32]