Optimistic Replication - Algorithms

Algorithms

An optimistic replication algorithm consists of five elements:

1. Operation submission: Users submit operations at independent sites.
2. Propagation: Each site shares the operations it knows about with the rest of the system.
3. Scheduling: Each site decides on an order for the operations it knows about.
4. Conflict resolution: If there are any conflicts among the operations a site has scheduled, it must modify them in some way.
5. Commitment: The sites agree on a final schedule and conflict resolution result, and the operations are made permanent.

There are two strategies for propagation: state transfer, where sites propagate a representation of the current state, and operation transfer, where sites propagate the operations that were performed (essentially, a list of instructions on how to reach the new state).

Scheduling and conflict resolution can either be syntactic or semantic. Syntactic systems rely on general information, such as when or where an operation was submitted. Semantic systems are able to make use of application-specific information to make smarter decisions. Note that state transfer systems generally have no information about the semantics of the data being transferred, and so they have to use syntactic scheduling and conflict resolution.