FeedSync Samples

0 Introduction

We created the “FeedSync for Atom and RSS” specification to enable a mesh computing experience for end users. From the end user point of view, the idealized mesh computing experience means that:

1.  
   • You can think of your data as existing in the computing mesh, as opposed to one particular device
   • You have access to your data both in the cloud and on all of your devices
   • Reliable synchronization means that you can view and edit your data on any device, and all other devices are updated
   • Multi-master synchronization means that you can take advantage of asymmetric computer and network resources at the edge, or at the center

FeedSync provides the reliable multi-master sync that is a key enabler for the mesh computing experience. FeedSync is currently defined in terms of Atom and RSS feeds, but at its core what FeedSync strictly requires is:

1.  
   • A flat collection of items to be synchronized
   • A set of per-item sync metadata that is maintained at all endpoints
   • A set of algorithms followed by all endpoints to create, update, merge, and conflict resolve all items

Because FeedSync will often be used as a way to pass data between endpoints running different software (what we often call a “heterogeneous” mesh of endpoints), feeds are a particularly useful format for containing FeedSync data. However, there are other cases when you control all of the endpoints (a “homogeneous” mesh), and in those cases you may want a different data format, while maintaining full FeedSync compatibility.

This specification describes the core requirements for implementing FeedSync with any data format.

1 Overview

The scope of FeedSync for Collections is to define the minimum extensions necessary to enable loosely-cooperating applications to use any container format as the basis for item sharing – that is, the bi-directional, asynchronous synchronization of new and changed items amongst two or more cross-subscribed endpoints.

One of the guiding principles of FeedSync is to reinvent as little as possible. This spec shares the same core metadata, algorithms and principles as the FeedSync for Atom and RSS specification, but does not require feeds as a container format.

Examples are given using “plain old XML” (POX) and JavaScript object notation (JSON).

1.1 Namespaces and Version

When FeedSync data is stored in any XML format, the XML namespace URI for FeedSync elements is:

http://feedsync.org/2007/feedsync

In this spec, the prefix "sx:" is used for the namespace URI identified above.

For simplicity, this specification will refer to “elements” and “attributes”, even though the same information may be stored in formats other than XML.

1.2 Notational Conventions

1. In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as described in RFC 2119.
2. The term item denotes a typed data entity and the basic unit of sharing and synchronization.
3. The term endpoint denotes an entity that participates in the synchronization of shared items with other endpoints. An endpoint can act as a publisher, a subscriber or both. The entity represented by an endpoint could be a user or group, or something more precise such as a specific user on a specific device.
4. An endpoint's item set is a complete set of related items as determined by the endpoint.
5. A collection is a group of items in an endpoint's item set represented in some well-known container format. The collection can be partial (only the items that have changed within a given time window) or complete (all of the items in the endpoint's item set are contained in the collection as of its publishing).
6. A subscription is a unidirectional relationship between two endpoints where one endpoint acting as a subscriber pulls collections from the other endpoint, which acts as a publisher.
7. The term updated is used to include items created, changed or deleted.
8. The term incorporate denotes the act of creating or updating a local collection item reflecting those updates made to the item in a remotely subscribed collection.

1.3 Usage Model

Consider two loosely coupled endpoints, A and B, that wish to share and co-edit a set of independent items. The two endpoints can use FeedSync to synchronize the set. The process would look like this:

1. Endpoint A maintains an item set. Endpoint A publishes the set as a collection conforming to the FeedSync format. Let's call this collection-A.
2. Endpoint B also maintains an item set. Endpoint B subscribes to collection-A and incorporates the items into its own set.
3. Endpoint B publishes its own set (including items it got from A) as a collection conforming to the FeedSync format. Let's call this collection-B.
4. Endpoint A subscribes to collection-B and incorporates items from endpoint B into its own set. In effect, endpoints A and B mutually publish/subscribe to each other's collections.
5. When endpoint A adds or updates an item, that update is reflected in collection-A and endpoint B receives the change when it reads the collection.
6. Similarly, when endpoint B adds or updates an item, the update is published in collection-B and endpoint A receives the change.

The extensions described in the FeedSync specification enable collection consumers and publishers to generate and process incoming item changes in a manner that enables consistency to be achieved. In order to accomplish this, FeedSync introduces concepts such as per-item change history (to manage item versions and update conflicts) and tombstones (to propagate deletions, and un-deletions).

Note that FeedSync is useful for one-way synchronization as well. For example, Endpoint A might only publish items through collection-A, but not accept updates. Endpoint B can use FeedSync as an efficient way to track published changes from Endpoint A.

1.4 Example Collections

These feeds demonstrate a series of updates to single item.

1.4.0 POX collection

<?xml version="1.0" encoding="utf-8"?> 
<collection xmlns:sx="http://feedsync.org/2007/feedsync">   
 <sx:sharing since="2005-02-13T18:30:02Z" until="2005-05-23T18:30:02Z" >   
 <sx:related link="http://example.com/all.xml" type="complete" />    
 <sx:related link="http://example.com/B.xml" type="aggregated" 

   title="To Do List (Jacks Copy)" />    
 </sx:sharing>    
 <item>    
 <sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="3">    
 <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>    
 <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
 <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
 </sx:sync>    
 <subject>Item #0<subject>    
 <body>Get milk, eggs, butter and bread<body>
 </item>
</collection>

1.4.1 RSS Feed (for comparison purposes only)

<?xml version="1.0" encoding="utf-8"?>    
<rss version="2.0" xmlns:sx="http://feedsync.org/2007/feedsync">    
<channel>    
 <title>To Do List</title>    
 <description>A list of items to do</description>    
 <link> http://example.com/partial.xml </link>    
 <sx:sharing since="2005-02-13T18:30:02Z"    
 until="2005-05-23T18:30:02Z" >    
 <sx:related link="http://example.com/all.xml" type="complete" />    
 <sx:related link="http://example.com/B.xml" type="aggregated"
 title="To Do List (Jacks Copy)" />    
 </sx:sharing>    
 <item>    
 <title>Buy groceries</title>    
 <description>Get milk, eggs, butter and bread</description>    
 <sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="3">    
 <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>    
 <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
 <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
 </sx:sync>    
 </item>    
</channel>    
</rss>

2 Extensions

2.1 Common requirements

The following requirements apply to all parts of this specification.

1. All endpoint identifiers MUST conform to the syntax for Namespace Specific Strings (the NSS portion of a URN) in RFC 2141. Endpoint identifiers MUST be chosen so that they always uniquely identify an endpoint, even when additional endpoints are added to the mesh over time. See the definition of the by attribute in section 2.5 for more information on endpoint identifiers.
2. Unless otherwise specified, if an xml element attribute value is set, it MUST be set to a non-empty string value.
3. Unless otherwise specified, string attributes are unbounded. An implementation MAY prevent incorporation of an item if one or more string attributes exceed bounds imposed by that implementation.
4. Unless otherwise specified, the comparison of string attributes MUST be done using the Unicode code point values of each character, and this comparison MUST be culture insensitive. A string starting with Unicode code point X sorts before a string starting with Unicode code point Y, if X is less than Y. This collation is not for presentation purposes, and is intentionally not the same as the algorithm described by the “Unicode Collation Algorithm” (http://www.unicode.org/reports/tr10/).
5. All date-time values MUST conform to the Date and Time specification of RFC 3339, with the following added constraints:
   • Times MUST be expressed in whole seconds only; fractional second values MUST NOT be present.
   • Times MUST be given in the UTC timezone, and end in “Z”, without a timezone offset.
6. It is strongly RECOMMENDED that all attributes that contain human readable strings contain plain text only. This includes the title attribute on sx:related and the by attribute on sx:history, and any other such attributes in this specification whose contents are intended to be human readable. It is NOT RECOMMENDED to include any embedded HTML or XML in those elements, and any such inclusion is ignored by this spec.
7. A collection may contain data such as XML markup or JSON objects which is not defined either by this specification or by the container format specification. (This is similar to the notion of “foreign markup” in section 6.1 of the Atom specification.) This data might include application extensions to FeedSync, or might include future extensions to FeedSync. Any such data SHOULD be preserved and republished by a FeedSync endpoint.

2.2 <sx:sharing> element within top-level container

The sx:sharing element is optional. If it exists, the sx:sharing element MAY contain one or more sx:related elements. Note that since a collection is not required to contain sx:sync elements, a collection containing only the sx:sharing element but no sx:sync elements is a valid FeedSync collection.

The sx:sharing element and all elements contained inside it are intended to be publisher-specific. That is, sx:sharing is used to communicate information from a collection publisher to the specific collection consumer that requested the collection. Endpoints that consume the collection MUST NOT republish the sx:sharing element or any of its sub-elements to other collection consumers.

2.3 <sx:related> element within <sx:sharing>

The sx:related element is optional, but when present contains information about related collections or locations.

2.2.1 Aggregated Collections

In the case where a publisher’s collection has incorporated items from other collections, it can be useful for subscribers to see more detailed information about the other collections. In the case of collection sharing as envisioned by this specification, this feature can also be used to notify subscribing collections of the collections of other participants which they might also wish to subscribe to.

POX Example

<collection>    
<sx:sharing>    
 <sx:related link="http://example.com/all.xml" type="complete" />    
 <sx:related link="http://example.com/B.xml" type="aggregated" 
 title="To Do List (Jacks Copy)" />    
</sx:sharing>    
 ...    
</collection>

2.4 <sx:sync> element within collection item elements

The most important extension described in this specification is the sx:sync element, which contains the information required for synchronization. This element is a direct child of an item element (e.g. <entry> or <item>). This is a REQUIRED element of all items in all collections wishing to participate in FeedSync-based synchronization. Note that since the sx:sharing element is not required, collection consumers MUST consider the presence of sx:sync elements in items as an indication that the collection contains sync data.

Note: is it acceptable for a collection to have some items or entries with sx:sync elements, and some without sx:sync. Only the items and entries that include the sx:sync element participate in FeedSync synchronization.

2.5 <sx:history> element within <sx:sync>

The sx:sync element MUST contain at least one sx:history sub-element. These sub-elements represent information about updates to the item, with the most recent update being first/topmost.
 

2.6 <sx:conflicts> element within <sx:sync>

The sx:sync element might contain an sx:conflicts sub-element. When the sx:conflicts element is present and contains one or more item or entry sub-elements, each item or entry represents a conflicting update. An empty sx:conflicts element in an item or entry MUST be considered equivalent to not having any sx:conflicts element in that item or entry, and indicates that there are no conflicts present. See conflict preservation behavior (section 3.4) for more information.

3 Required Behaviors for Global Consistency

To assure consistency when modifying a local collection, the following behaviors will be defined:

• Creation
• Update/Deletion
• Conflict Resolution

To assure consistency when processing incoming (subscribed) collections, the following behaviors will be defined:

• Merge

Although the precise format of the data is a decision left to each implementer, the algorithms described in this section assume that conceptually the data is stored in some structure that is capable of expressing order and relationships.

Depending on the particular implementation, the data could be stored in nested tables in a database, or in an object graph in memory, or as a series of entries in a flat file. The important thing is that when the sync algorithms are performed, the implementer must preserve parent/child container relationships between the different types of data.

3.1 Creation Behavior

When creating a new item as the result of a local operation, implementations MUST:

1. Create an sx:sync structure as follows:
   1. Set the id value (in conformance with section 2.3)
   2. Set the updates value to 1
   3. Optionally set the noconflicts value
   4. Optionally set the deleted value if the item is tombstoned from birth
2. Create a sx:history structure as follows:
   1. Set the sequence value (in conformance with section 2.5). It is RECOMMENDED that the sequence value be set to 1.
   2. Do one or both of the following:
      1. Set the when value to the current date-time. Note that this value is optional if the by value is set, but it is RECOMMENDED that this value be set whenever possible.
      2. Set the by value to the current endpoint's identifier. Note that this value is optional if the when value is set, but it is RECOMMENDED that this value be set whenever possible.
   3. Add the sx:history structure as the topmost child of the sx:sync structure.
3. Add the sx:sync structure as a child of the item
4. Append the item as a child of the collection.
5. Optionally update the until value for the sx:sharing structure

Here is what an item could look like after being created:

POX Example

<item>   
<subject>Buy groceries</subject>    
<body>Get milk and eggs</body>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="1">   
 <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</item>

JSON Example

{    
 “title” : “Buy groceries”,    
 “description”: “Get milk and eggs”,    
 “sync”: {    
 “id”: “item_1_myapp_2005-05-21T11:43:33Z”,    
 “updates”: “1”,    
 “history”: [    
 {“sequence”: “1”, “when”: “2005-05-21T09:43:33Z”, “by”: “REO1750”}    
 ]    
 }    
}

Atom Example (for comparison purposes only)

<entry>    
<title>Buy groceries</title>    
<content>Get milk and eggs</content>    
<updated>2005-05-21T09:43:33Z </updated>    
<id>urn:uuid:60a76c80-d399-11d9-b93C-0003939e0aa0</id>    
<author>    
 <name>Ray Ozzie</name>    
</author>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="1">    
 <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</entry>

3.2 Update/Deletion Behavior

When updating or deleting an item via a local operation, implementations MUST:

1. Update the sx:sync structure as follows:
   1. Increment the updates value by 1
2. Create a sx:history structure as follows:
   1. Do one or both of the following:
      1. Set the when value to the current date-time. Note that this value is optional if the by value is set, but it is RECOMMENDED that this value be set whenever possible.
      2. Set the by value to the current endpoint's identifier. Note that this value is optional if the when value is set, but it is RECOMMENDED that this value be set whenever possible.
   2. If the by value has not been set in Step 2a, set S₁ to be the same value as the updates value set in Step 1.
   3. If the by value has been set in Step 2a:
      1. Set S₁ to any valid value. It is RECOMMENDED that implementations set S₁ to the same value as the updates value set in Step 1.
      2. Set S₂ to be the greatest sequence value of all sx:history children with the same by value as the value set in Step 2a.  Implementations MAY set S₂ to be the greatest sequence value of all sx:history sub-elements across all items in the feed with the same by attribute value.
      3. If S₁ <= S₂, then set S₁ to any valid value that is greater than S₂. It is RECOMMENDED that implementations set S₁ to (S₂ + 1).
   4. Set the sequence value to S₁.
3. Add the sx:history structure as the topmost child of the sx:sync structure.
4. If the by attribute has been set in step 2a, and the sx:conflicts structure is present and non-empty:
   1. For each child structure X of the sx:conflicts structure:
      1. Set H to be the topmost sx:history child structure of the sx:sync structure for X
      2. If the by attribute of H is set and has the same value as the by attribute set in step 2a, then follow the steps for Merging Conflict Items (see Section 3.4) for item X  
5. If this is a deletion, set the deleted value on the sx:sync structure to true.
6. If this is an un-deletion, set the deleted value on the sx:sync structure to false.

Additionally implementations MAY:

1. Clean up sx:history children with a by attribute value so that only the sx:history child with the highest sequence attribute value for a given by is retained, and all other sx:history children with the same by attribute value are discarded.
2. If this is a deletion, remove the item’s data as long as the item’s sx:sync and topmost sx:history children are preserved. Note that truncation or removal of data might cause unexpected results if a subsequent conflict occurs for the item, or if the item is subsequently undeleted. Also note that publishers SHOULD rely on the since, until, and expires values (if present) of the sx:sharing structure to determine when to stop publishing items.
3. Update the until value for the sx:sharing structure.

Here is what the same item in the above example would look like after having been updated in sequence by the same endpoint:

POX Example #1

<item>    
<subject>Buy groceries</subject>    
<body>Get milk, eggs and butter</body>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="2">    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</item>

RSS Example #1 (for comparison purposes only)

<item>    
<title>Buy groceries</title>    
<description>Get milk, eggs and butter</description>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="2">    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</item>

Here is what the same item in the above example would look like after having been updated in sequence by another endpoint:

POX Example #2

<item>    
<subject>Buy groceries</subject>    
<body>Get milk, eggs, butter and bread</body>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="3">    
  <sx:history sequence="3" when="2005-05-21T09:43:33Z" by="JEO2000"/>    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</item>

RSS Example #2 (for comparison purposes only)

<item>    
<title>Buy groceries</title>    
<description>Get milk, eggs, butter and bread</description>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="3">    
  <sx:history sequence="3" when="2005-05-21T09:43:33Z" by="JEO2000"/>    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</item>

3.3 Merge Behavior

When a subscribing endpoint incorporates items from a publishing endpoint’s collection, these items must be merged with the existing local items. The act of merging items from an incoming collection detects new items, item updates and item conflicts and produces a merged result collection. The merging of two items with the same id value will result in a ‘winning’ item that might have conflict items. In order to merge items, implementations MUST follow this algorithm for the two items:

1. If no local item exists with the same id value as the incoming item, add the incoming item to the merge result collection; we are done processing the incoming item.
2. Create a collection L and populate it with the local item and the local item’s conflicts (if any exist) by using the following steps:
   1. For each item child of the sx:conflicts structure for the local item:
      1. Add the item child to L
   2. If the local item has a sx:conflicts child, remove it
   3. Add the local item to L
   4. Create a collection I and populate it with the incoming item and the incoming item’s conflicts (if any exist) by using the following steps:
3. For each item child of the sx:conflicts structure for the incoming item:
   1. Add the item child to I
      1. If the incoming item has a sx:conflicts child, remove it
   2. Add the incoming item to I
4. Create a collection M that will be used to contain items that will appear in the merged result collection
5. Create a reference W for the current ‘winning’ item and set it to an unassigned value
6. Using L as the outer collection and I as the inner collection, perform the following step
7. For each item X in outer collection:
   1. For each item Y in inner collection:
      1. Determine if X is subsumed¹ by Y – if so then remove X from the outer collection; process the next item in the outer collection
   2. Add X to M
   3. If W has not been assigned a value, set W to X; process the next item in the outer collection
   4. Determine if X should be declared as the new ‘winning’ item³ – if so set W to X.
8. Using I as the outer collection and L as the inner collection, perform step 7 again
9. Add W to the merge result collection
10. If the noconflicts value is set to true, then we are done processing
11. If M contains more than one item:
    1. Create a sx:conflicts structure and add it as a child of the sx:sync structure for W
    2. For each item Z in M:
    3. If Z equals W (i.e. they are the same item), then process the next item in M
    4. Add Z as a child of the sx:conflicts structure created in step 11a.

Note that children of a sx:conflicts structure are always preserved as a flat, unordered list.

¹ Item Subsumption

An item X is subsumed by an item Y when the topmost sx:history child of X is subsumed² by one of the sx:history children of Y, where X and Y are items with the same id value. In order to determine if X is subsumed by Y, implementations MUST perform the following:

1. Set H_X as the topmost sx:history child of X
2. For each sx:history child H_Y of item Y:
3. Compare H_X with H_Y to see if H_X is subsumed² by H_Y – if so then X is subsumed by Y

If no determination has been made as to whether X is or is not subsumed by Y, then X is not subsumed by Y

² History Subsumption

To determine if a sx:history structure H_X is subsumed by a sx:history structure H_Y, implementations MUST perform the following comparisons, in order, for H_X and H_Y:

1. If a by value exists for H_X:
   1. If H_Y has the same by value as H_X, and H_Y has an equal or greater sequence value than H_X, then H_X is subsumed by H_Y
2. If no by value exists for H_X:
   1. If no by value exists for H_Y, and the when and sequence values for H_X respectively matches the when and sequence values for H_Y, then H_X is subsumed by H_Y
3. If no determination has been made as to whether H_X is or is not subsumed by H_Y, then H_X is not subsumed by H_Y

³ Winner Picking

The ‘winning’ item between an item X and an item Y is the item with most recent update , where X and Y are items with the same id value. In order to determine the ‘winning’ item, implementations MUST perform the following comparisons, in order, for X and Y:

1. If X has a greater updates value for the sx:sync child than Y’s, then X is the ‘winning’ item
2. If X has the same updates value for the sx:sync child as Y:
   1. If X has a when value for the topmost sx:history child and Y does not, then X is the ‘winning’ item
   2. If X has a when value for the topmost sx:history child and that is chronologically later than Y’s, then X is the ‘winning’ item
   3. If X has the same when value for the topmost sx:history child as Y:
      1. If X has a by value for the topmost sx:history child and Y does not, then X is the ‘winning’ item
      2. If X has a by value for the topmost sx:history child that is collates greater (see Section 2.1.4 for collation rules) than Y’s, then X is the ‘winning’ item
3. 3. Y is the ‘winning’ item

Here is what the same item in the above example would look like after having been independently updated by two endpoints, causing a conflict:

POX Example

<item>
<subject>Buy groceries - DONE</subject>
<body>Get milk, eggs, butter and bread</body>
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="4">
 <sx:history sequence="4" when="2005-05-21T12:43:33Z" by="GPM7383"/>
 <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>
 <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>
 <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>
 <sx:conflicts>
 <item>
 <subject>Buy groceries</subject>
 <body>Get milk, eggs, butter and rolls</body>
 <sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="4">
 <sx:history sequence="4" when="2005-05-21T12:03:33Z" by="JEO2000"/>
 <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>
 <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>
 <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>
 </sx:sync>
 </item>
 </sx:conflicts>
</sx:sync>
</item>

RSS Example

<item>    
<title>Buy groceries - DONE</title>    
<description>Get milk, eggs, butter and bread</description>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="4">    
  <sx:history sequence="4" when="2005-05-21T12:43:33Z" by="GPM7383"/>    
  <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
  <sx:conflicts>    
  <item>    
  <title>Buy groceries</title>    
  <description>Get milk, eggs, butter and rolls</description>    
  <sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="4">    
  <sx:history sequence="4" when="2005-05-21T12:03:33Z" by="JEO2000"/>    
  <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
  </sx:sync>    
  </item>    
  </sx:conflicts>    
</sx:sync>    
</item>

3.4 Conflict Resolution Behavior

Applications can allow users to "resolve" conflicts for an item, where "resolve" means to perform an update to the item that takes the conflicting item data into account in some meaningful way. For items that have multiple conflicts, implementations MAY selectively resolve conflicts, keeping some conflicts unresolved and intact for subsequent resolution. When a particular conflict is resolved, it is removed from the list of the item’s conflicts and merged into the item’s history. In order to resolve conflicts, the following MUST occur:

1. The user is presented, within some user interface, with the ‘winning’³ item data along with the data for each of the conflicting versions of that same item (i.e. retrieved from the sx:conflicts children of the item). The user will then select one of the following actions:
   1. To keep the most recent data as the “resolved” state (i.e. confirming that the latest state is the desired state)
   2. To select one of the conflicting version’s data as the “resolved” state
   3. To combine or otherwise create new data as the “resolved” state (i.e. creating their own desired state)
2. The appropriate “resolved” state MUST be used to perform an update operation (section Section 3.2) to the item
3. The conflict items the user factored into their decision MUST then be merged⁴ into the item’s history so the user isn’t asked to resolve the same conflict more than once.

Note that while the steps above focus on user based conflict resolution, it does not obviate the possibility of programmatic conflict resolution. Programmatic conflict resolution would require that all endpoints execute the same conflict resolution logic for deterministic results.

⁴ Merging Conflict Items

In order to merge conflict items into the resolved item’s history, implementations MUST:

1. Set Y as a reference the resolved item
2. Set S_y as a reference to the sx:sync child for Y
3. For each item child X of the sx:conflicts structure that has been resolved:
   1. Set S_X as a reference to the sx:sync child for X
   2. Remove X from the sx:conflicts structure.
   3. For each sx:history child H_X of S_X:
      1. For each sx:history sub-element H_y of S_Y:
         1. Compare H_X with H_y to see if H_X can be subsumed² by H_Y – if not then add H_X as a sub-element of S_Y, immediately after the topmost sx:history sub-element of S_Y.

4.  If the sx:conflicts structure contains no children, the sx:conflicts structure SHOULD be removed.

Here is what the same item in the above example would look like after conflict resolution has occurred, where one of the endpoint’s changes are picked as the resolved state:

POX Example

<item>    
<subject>Buy groceries - DONE</subject>    
<body>Get milk, eggs, butter and bread</body>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="5">    
  <sx:history sequence="5" when="2005-05-21T12:53:33Z" by="GPM7383"/>    
  <sx:history sequence="4" when="2005-05-21T12:03:33Z" by="JEO2000"/>    
  <sx:history sequence="4" when="2005-05-21T12:43:33Z" by="GPM7383"/>    
  <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</item>

RSS Example (for comparison purposes only)

<item>    
<title>Buy groceries - DONE</title>    
<description>Get milk, eggs, butter and bread</description>    
<sx:sync id="item_1_myapp_2005-05-21T11:43:33Z" updates="5">    
  <sx:history sequence="5" when="2005-05-21T12:53:33Z" by="GPM7383"/>    
  <sx:history sequence="4" when="2005-05-21T12:03:33Z" by="JEO2000"/>    
  <sx:history sequence="4" when="2005-05-21T12:43:33Z" by="GPM7383"/>    
  <sx:history sequence="3" when="2005-05-21T11:43:33Z" by="JEO2000"/>    
  <sx:history sequence="2" when="2005-05-21T10:43:33Z" by="REO1750"/>    
  <sx:history sequence="1" when="2005-05-21T09:43:33Z" by="REO1750"/>    
</sx:sync>    
</item> 

4 Partial Collections and Complete Collections

Publishers will generally include, in a collection, only the most recent modifications, additions, and deletions within some reasonable time window. These collections are referred to herein as partial collections, whereas collections containing the complete set of items are referred to as complete collections.

In the collection sharing context new subscribers, or existing subscribers failing to subscribe within the published collection window, will need to initially copy a complete set of items from a publisher before being in a position to process incremental updates. As such, this specification provides for the ability for the latter collection to reference the complete collection. By placing the link to this collection in the collection descriptor, only the partial collection URL need to be distributed to potential subscribers.

The guidelines below explain how publishers and subscribers MAY optionally use since and until values for the sx:sharing structure to ensure that all item updates are synchronized, even if the publisher periodically purges items from its collection. Note that these guidelines are only applicable when the subscriber maintains a local store for the collection’s items.
 

4.1 Subscriber guidelines

4.1.1 The following steps SHOULD be followed by the subscriber for initial collection consumption

1. Read the contents of the published collection
2. See if a sx:related child exists for the sx:sharing structure, with a type value of ‘complete’ – then repeat step 1 above with the collection URL specified by the link value
3. Perform a merge operation (see Section 3.3)
4. If the subscribed collection contains the since and until values for the sx:sharing structure:
   1. The subscriber SHOULD cache the value of the until value for the sx:sharing structure for subsequent collection consumption

4.1.2 The following steps SHOULD be followed by the subscriber for subsequent collection consumption

1. Read the contents of the published collection
2. If the collection contains the since and until values for the sx:sharing structure and the subscriber cached the value of the until value from a previous read, then determine if the subscriber is out of sync with the collection:
   1. If the value of the since value for the sx:sharing structure is greater than the cached value of the until value:
      1. If a sx:related child exists for the sx:sharing structure, with a type value value of ‘complete’ – if so then repeat step 1 above with the collection URL specified by the link value
      2. The subscriber is out of sync with collection, so all items that were not created, or most recently updated, by the subscribing endpoint should be discarded from the subscriber’s local store.
      3. Subsequent collection consumption is complete for the out of sync subscriber. Continue with the steps outlined for initial collection consumption in section 5.1.1
   2. The subscriber SHOULD cache the value of the until value for the sx:sharing structure for subsequent collection consumption
3. Perform a merge operation for the collection items in the local store and the collection (see Section 3.3)

4.2 Publisher guidelines

4.2.1 The following steps SHOULD be followed by the publisher when publishing a collection for the first time (for either a complete or partial collection)

1. If items will ever be purged from the collection:
   1. Set the value¹ of the since value of the sx:sharing structure to correspond to the incorporation of least recently updated item in the collection.
   2. Set the value¹ of the until value of the sx:sharing structure to correspond to the incorporation of most recently updated item in the collection.
   3. Optionally set the value of the expires value for the sx:sharing structure to a date-time value before which subscribers SHOULD read the collection in order to avoid missing item updates due to items being purged from collection.

4.2.2 The following steps MAY be followed by the publisher when subsequently publishing a collection

1. If the expires value for the sx:sharing structure exists, update its value to a date-time before which subscribers SHOULD read the collection in order to avoid missing item updates.

4.2.3 The following steps SHOULD be followed by the publisher when incorporating an item update into the collection

1. Increment the value of the until value for the sx:sharing structure by an appropriate amount
2. Associate and store the new value of the until value with the item
3. If the expires value for the sx:sharing structure exists, optionally keep track of the date-time when incorporating the item’s changes. This value MAY be used in relation to the expires value for the sx:sharing structure by the publisher when determining which items to remove from a collection.

4.2.4 The following steps SHOULD be followed by the publisher when removing an item from a collection

1. If the stored value associated with the item from (step 2 in section 5.2.3) is greater than the value for the since value for the sx:sharing structure, set the value for the since value for the sx:sharing structure to the stored value

¹since and until values

These values SHOULD be thought of as ever-increasing values that are represented in a manner that allows string collation by subscribers to yield the appropriate results. For example, if the publisher uses a date-time value to represent an incorporation timestamp for since and until, the value MUST be normalized for string comparison (e.g. “2006-05-02T09:10:33Z” instead of “2 May 2006 09:10:33”).

5 References

RFC 2119: http://www.ietf.org/rfc/rfc2119.txt

RFC 2141: http://www.ietf.org/rfc/rfc2141.txt

RFC 3339: http://www.ietf.org/rfc/rfc3339.txt

RFC 3986: http://www.ietf.org/rfc/rfc3986.txt

RFC 4287: http://www.ietf.org/rfc/rfc4287.txt

6 Licensing Information

Microsoft's copyrights in this specification are licensed under the Creative Commons Attribution-ShareAlike License (version 3.0). To view a copy of this license, please visit http://creativecommons.org/licenses/by-sa/3.0/. As to software implementations, Microsoft is not aware of any patent claims it owns or controls that would be necessarily infringed by a software implementation that conforms to the specification's extensions. If Microsoft later becomes aware of any such necessary patent claims, Microsoft also agrees to offer a royalty-free patent license on reasonable and non-discriminatory terms and conditions to any such patent claims for the purpose of publishing and consuming the extensions set out in the specification.