paper

Optimistic replication

  • Authors:
Read the paper

📜 Abstract

Data replication is a key technology in distributed data sharing systems, enabling higher availability and performance. This paper surveys optimistic replication algorithms that allow replica contents to diverge in the short term, in order to support concurrent work practices and to tolerate failures in low-quality communication links. The importance of such techniques is increasing as collaboration through wide-area and mobile networks becomes popular. Optimistic replication techniques are different from traditional “pessimistic” ones. Instead of synchronous replica coordination, an optimistic algorithm propagates changes in the background, discovers conflicts after they happen and reaches agreement on the final contents incrementally. We explore the solution space for optimistic replication algorithms. This paper identifies key challenges facing optimistic replication systems — ordering operations, detecting and resolving conflicts, propagating changes efficiently, and bounding replica divergence — and provides a comprehensive survey of techniques developed for addressing these challenges.

✨ Summary

The paper provides a systematic survey and taxonomy of optimistic replication, organizing the design space around master placement, state versus operation transfer, scheduling, conflict management, propagation, and consistency guarantees. Its treatment of happens-before relations, vector clocks, epidemic propagation, session guarantees, and replica-divergence bounds became a useful conceptual reference for later work on weakly consistent replicated systems.

Subsequent research on replicated data types and CRDTs cites the paper as background when describing optimistic replication, convergence, commutativity, and conflict management. Later CRDT surveys and foundational papers connect these ideas to convergent and commutative replicated data types, extending the paper’s emphasis on semantic operations and eventual convergence. (repositorio.inesctec.pt)

The paper also remains used as a foundational teaching reference for large-scale distributed systems and replication, including curricula covering logical clocks, consistency models, causal dissemination, and CRDTs. (mei.di.uminho.pt)

The publication metadata is independently listed as March 2005 in ACM Computing Surveys, volume 37, issue 1, pages 42–81. (cir.nii.ac.jp)