Data Exchange

Terminology

• deviceId: The primary key for a client, encoded as an array with a single integer-valued element, shared across platforms. When a device creates or joins a "Sync Chain", it assigns itself the deviceId.

• Browser object: Browser-specific representation of a syncable object (differs between platforms).

• Sync object: Platform-independent representation of a syncable object (cf., Data formats), encoded as JSON.

• SyncRecord: An action (create, update, or delete), a deviceId, and an associated sync object.

• objectId: The primary key for an object, encoded as a UUID, shared across platforms. Prior to uploading a created object, the client library assigns the objectId.

Processing

Note that, at present, the iOS platform does not implement the retry algorithm (or retry store) described in these procedures.

Initial Sychronization

1. The user creates (or joins) a "Sync Chain", which causes the browser to generate (or import) a symmetric key seed.

   The browser may allow the user to choose which collections to sync; however, as of this writing, there is only one supported collection "BookMarks".

2. The browser determines its own deviceId (see below)

3. The browser uploads new SyncRecords, with the client library assigning each an objectId.

4. The Browser retrieves all existing SyncRecords.

Sending SyncRecords

1. The browser periodically checks whether any browser objects have been created, modified or deleted after the corresponding sync object was retrieved.

   However, the iOS platform does uploads "on demand", instead of maintain a send queue.

2. For each such browser object, a coresponding SyncRecord is created.

3. Each SyncRecord is uploaded.

4. The browser records a time-to-retry timestamp and SyncRecord in a retry store.

5. If the client library is capable of reporting the result of the underlying S3 POST operation, then if the POST operation subsequently succeeds, the associated SyncRecords are removed from the retry store.

   (At present, no client library implementations offer this functionality.)

Retry Algorithm

1. The browser periodically checks to see id the retry store is empty.

2. If so, or if none of the SyncRecords in the retry store have an expired time-to-retry timestamp in the past, processing completes; otherwise:

3. The browser uploads exactly those SyncRecords, and updates the time-to-retry timestamp for associated entries in the retry store.

   The retry algorithm is at the browser's discretion, e.g., linear (every 2 minutes) or exponential, etc.

4. If the client library is capable of reporting the result of the underlying S3 POST operation, then if the POST operation subsequently succeeds, the associated SyncRecords are removed from the retry store.

Retrieving SyncRecords

1. The browser periodically requests any SyncRecords created since the last receiveed timestamp.

   On initial synchronization, an epoch value for timestamp is used.

   Optionally, the browser may also specify the maximum number of records to return. (On mobile platforms, no more than 300 records are retrieved at a time.)

n2. If no records are returned, processing completes; otherwise:

3. The browser identifies and preserves the most recent timestamp in the record set.

4. The browser examines each SyncRecord, and if the deviceId matches the browser's identity, removes the corresponding entry (if any) from the retry store.

5. The browser presents the record set to the synchronization library, along with the browser object store.

   Tohe synchronization library must process all SyncRecords in the record set, including those with the browser's deviceId (cf., Conflict Resolution)

6. The synchronization library harmonizes the SyncRecords based on the browser object store. resolves any conflicts, e.g.,

   • converting an update record for a non-existent browser object to a creation record;
   • combining multiple update records to a single update record for a browser object; or,
   • removal of deletion records for a non-existent browser object.

7. The browser than applies the resulting SyncRecords to its browser object store.

8. The browser repeats this procedure using the timestamp value identified in Step 3.

Conflict Resolution

Processing of SyncRecords occurs asynchronously with respect to other browser activities. For example:

1. Device 1 changes a bookmark resulting in a update SyncRecord (eventually) being uploaded.

2. Device 2 receives the SyncRecord and executes Step 5 of the retrieval procedure.

3. Prior to Step 7 of the retrieval procedure completing, device 2 changes the same bookmark, and an update SyncRecord is generated.

4. When Step 7 of the retrieval procedure completes, the bookmark on device 2 is overwritten with the the SyncRecord from device 1 -- the bookmark no longer reflects the change made by device 2 moments earlier.

5. Device 2 (eventually) receives the SyncRecord that it generated, and upon completion of its Step 7 of the retrieval procedure, the bookmark reflects the change made by device 2.

Device Initialization

NB: This procedure contains a race-condition. A new procedure is being developed, along with a recovery algorithm.

1. If the client is creating the "Sync Chain", it assigns itself a deviceId of 0 and no processing completes; otherwise:

2. The Browser retrieves all existing SyncRecords, and examines each that contains a creation of a Device object.

3. For each SyncRecord, it finds the largest deviceId present.

4. It assigns itself a deviceId equal to the sum of the largest value observed and one.