1.3.1 Synchronization


This protocol is used to synchronize information among endpoints (3) participating in a shared space. A shared space consists of a set of zero or more tools. Each tool has zero or more engines. Engines define a set of operations, or commands. Changes to the synchronized tool data are made by executing these commands. One or more commands are grouped into a delta, which is the unit of transactional consistency in a shared space. Dynamics guarantees that all of the commands in a delta are executed sequentially. Dynamics synchronizes the shared space by causing all deltas to be executed in the same order on all endpoints.

A typical example would be a shared space with a threaded discussion tool that would allow multiple endpoints to contribute discussion topics and post replies. This tool could be built using the record database (RDB) engine. RDB has a command set for manipulating records, which includes commands for adding and deleting records, and setting fields on existing records. Data consistency across all endpoints is achieved by using this protocol to sequence the execution of the commands.

A shared space can have an arbitrary number of members, but all examples in this document use a space with three members, who are referred to as A, B, and C. In examples, deltas will be designated by a letter indicating the endpoint that created the delta and a number that is the sequence of the delta generated on that endpoint. So A3 would be the third delta created by endpoint A. This is a simplification of the delta sequence numbering scheme which will be described later.

A simple scenario in which dynamics is used starts with the user at endpoint A creating a new discussion topic. This causes the RDB engine to create a command to add a new record. The command includes the title and contents of the discussion topic. A creates delta A1 containing the add record command. Dynamics sends A1 as a delta message to endpoints B and C. When those endpoints receive A1 they execute the commands in the delta, which causes the new record to be added and appear in the tool so that it can be read by the users on those endpoints.

In the event that different endpoints make independent changes, it is impossible to get a completely consistent order of execution of deltas on all endpoints. Dynamics achieves convergence by getting a logically equivalent order of execution on all endpoints. All engines implementing this protocol support the ability to undo all of their commands. In the event that a newly received delta requires that the delta order be changed, the commands in the previously executed deltas that are being reordered will be undone and then executed again in the proper order.

For example, consider what happens when two endpoints, A and B, create new discussion entries at the same time. This results in the creation of deltas A2 and B1. Dynamics will define the ordering of those deltas. This ordering will be consistent on all endpoints. In this case assume that B1 is before A2. When B receives A2, it will have already executed B1. Because A2 comes after B1 this isn’t a problem and it can execute A2. However A will have already executed A2 when B1 is received. To get the correct logical ordering, it will need to undo A2, execute B1 and then execute A2.

Dynamics guarantees causal consistency in the order of execution of deltas. Causal consistency is the property that when an endpoint, A, executes a delta created by a different endpoint, B, A must have previously executed all normal deltas that B had executed when it created the new delta. For any new delta, any deltas that the creator of that delta had executed prior to creating the delta need to be executed on all endpoints before they execute the new delta. So if A has executed B2 and then creates A3, but C receives A3 before receiving B2, C waits to execute A3 until B2 is received and executed.