To measure the relative priority of two versions of an object's content, we need to know where and when each version was modified. We consider each system that independently stores and manipulates object content to be an independent location or "node". We assume that each node maintains a a 32 bit counter value, or "clock", that is "ticked", or incremented, each time the node synchronizes with another node. If we identify each node by a globally unique id, then the pairing of that id with the node's clock counter identifies a unique place and time. Priority is then determined by recording the place and time of each modification to an object's content. This record is called the object's "pedigree".
A pedigree is simply a finite mathematical function, that is, a set of ordered pairs whose first element is unique, that records where and when an object's content was modified. Each time the object is modified at a node, the object's pedigree is updated to indicate the time of the modification. For example, an object that is created on an ALP phone will be assigned an initial pedigree of {(A, n)}, where A is the phone node's GUID and n is its current clock value. If the object is later modified at an ALP desktop, the pedigree would become {(A, n), (D, m)}, where D is the unique GUID for the desktop's node and m is its current clock value.
An object version O1 is said to have an equal or lesser priority that an object version O2, if the pedigree P1 for O1 is less than or equal to the pedigree P2 for O2. A pedigree P1 is less than or equal to a pedigree P2, if for all nodes N, the counter value for N in P1 is less than or equal to the counter value for N in P2. For simplicity, we assume that nodes not explicity represented in a pedigree have a counter value of zero. In the prior example, the pedigree for the phone's version of the object, {(A, n)}, is less than the pedigree for the later desktop modification, {(A, n), (D, m)}. Thus when the ALP phone and desktop next synchronize, the desktop modification will replace the "older" version present on the phone.
It's important to note that the set of all priorities is *not* totally ordered by the less than or equal to relation just defined. That is, for two pedigrees P1 and P2, it's possible that P1 is not less than or equal to P2 and P2 is not less than or equal to P1. Thus the less than or equal relation constitutes a partial ordering over the set of pedigrees. Unordered pedigrees are said to be in "conflict". This exactly models the problem of conflicting edits to an object's content. In the prior example, suppose the object is edited on the phone before the phone and desktop next synchronize. The the object's pedigree on the phone becomes {(A, p}), where p > n. When the phone and desktop next synchronize, neither the phone's pedigree nor the desktop's pedigree is less than the other. Thus the edits made independently on the destop and phone conflict; in this case both versions of the object's content are saved until the conflict is resolved.
NOTE: A conflict is not generated when conflicting edits result in identical content.
Functions | |
| alp_status_t | alp_hs_pedigree_add_clock (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr pPedigree, AlpHsClockIdPtr pNodeId, uint32_t clockVal) |
| Adds a clock to the input transient pedigree. | |
| alp_status_t | alp_hs_pedigree_add_pedigree (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr pSrcPedigree, AlpHsPedigreePtr pTgtPedigree) |
| Adds the target pedigree to the source pedigree. | |
| alp_status_t | alp_hs_pedigree_copy (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr pSrcPedigree, AlpHsPedigreePtr *ppTgtPedigree) |
| Copies the input transient pedigree. | |
| alp_status_t | alp_hs_pedigree_create (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr *ppPedigree) |
| Create a new, initially empty, transient pedigree. | |
| alp_status_t | alp_hs_pedigree_delete (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr pPedigree) |
| Deletes the input pedigree. | |
| alp_status_t | alp_hs_pedigree_get_clock (AlpHsChangeMgrHandle h, AlpHsPedigreePtr pPedigree, uint32_t index, AlpHsClockIdPtr *pNodeId, uint32_t *pClockVal) |
| Provides indexed access to clocks in a transient pedigree. | |
| alp_status_t | alp_hs_pedigree_get_clock_count (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr pPedigree, uint32_t *pCount) |
| Returns the number of clocks in the input pedigree. | |
| alp_status_t | alp_hs_pedigree_get_clock_value (AlpHsChangeMgrHandle h, AlpHsPedigreePtr pPedigree, AlpHsClockIdPtr pNodeId, uint32_t *pClockVal) |
| Retrieves the clock counter value for a node in a transient pedigree. | |
| alp_status_t | alp_hs_pedigree_is_less_or_equal (AlpHsChangeMgrHandle h, AlpHsPedigreePtr pPedigree1, AlpHsPedigreePtr pPedigree2, bool *pResult) |
| Compares two transient pedigrees and returns true if the first is less than or equal to the second. | |
| alp_status_t | alp_hs_pedigree_make_persistent (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr pInPedigree, AlpHsPedigreePtr *ppOutPedigree) |
| Creates a persistent pedigree from a transient pedigree. | |
| alp_status_t | alp_hs_pedigree_make_transient (AlpHsChangeMgrHandle hChgMgr, AlpHsPedigreePtr pInPedigree, AlpHsPedigreePtr *ppOutPedigree) |
| Creates a transient pedigree from a persistent pedigree. | |
|
||||||||||||||||||||
|
Adds a clock to the input transient pedigree. This function is used to add a clock value to the input transient pedigree. The clock value is an ordered pair consisting of a node id and a counter.
|
|
||||||||||||||||
|
Adds the target pedigree to the source pedigree. The sum of two pedigrees, P1 + P2, is defined as the least upper bound of the two pedigrees. That is P1 + P2 is the least pedigree such that, P1 <= P1 + P2, and P2 <= P1 + P2. Conceptually, for each corresponding pair (N, n1) and (N, n2) in P1 and P2, (N, ni) is in P1 + P2, where ni is n1 if n1 >= n2 and n2 otherwise.
|
|
||||||||||||||||
|
Copies the input transient pedigree.
|
|
||||||||||||
|
Create a new, initially empty, transient pedigree. This function is used to create a new transient pedigree. Clocks can then be added to the pedigree by calling alp_hs_pedigree_add_clock(). The pedigrees created by this function are said to be "transient" because they are only valid while the input or "parent" ChangeMgr remains open. A pedigree can be made to persist by calling alp_hs_pedigree_make_persistent().
|
|
||||||||||||
|
Deletes the input pedigree. Deletes the input persistent or transient pedigree.
|
|
||||||||||||||||||||||||
|
Provides indexed access to clocks in a transient pedigree.
|
|
||||||||||||||||
|
Returns the number of clocks in the input pedigree.
|
|
||||||||||||||||||||
|
Retrieves the clock counter value for a node in a transient pedigree.
|
|
||||||||||||||||||||
|
Compares two transient pedigrees and returns true if the first is less than or equal to the second.
|
|
||||||||||||||||
|
Creates a persistent pedigree from a transient pedigree. The pedigrees created by alp_hs_pedigree_create() are said to be transient because they can only be used while the parent ChangeMgr instance remains open. A transient pedigree is made persistent by calling this function. A persistent pedigree can outlive the ChangeMgr that created it; for example, a persistent pedigree can be stored for later use. However, a persistent pedigree must be made transient before it can be manipulated by other pedigree functions.
|
|
||||||||||||||||
|
Creates a transient pedigree from a persistent pedigree.
|
Generated on Wed Jul 30 07:06:41 2008 by Doxygen 1.4.6 for ALP SDK + Hiker Documentation
Copyright © 1999-2008 ACCESS CO., LTD. All rights reserved.