7.3 Eventual consistency

Summary of Main Ideas

The lecture contrasts linearizability and eventual consistency as consistency models for distributed systems. Linearizability provides a strong guarantee by making a system behave as if it had a single copy of the data but comes with trade-offs in performance, scalability, and availability. Eventual consistency offers a more flexible model by relaxing consistency requirements, enabling faster, more reliable operations at the cost of weaker guarantees. The lecture introduces strong eventual consistency as a refinement of eventual consistency and discusses key algorithms and trade-offs in consistency models.

---

Bullet Points Summarizing General Themes

Linearizability:

• Definition and Benefits:

  • Makes a system behave as if it had a single atomic copy of the data.
  • Simplifies programming by abstracting away distributed complexity.

• Drawbacks:

  • Expensive to implement due to multiple message exchanges and round trips.
  • Scalability is limited by bottlenecks like leader nodes in consensus algorithms.
  • Availability issues: operations fail when a quorum of nodes cannot be contacted.

Eventual Consistency:

• Definition:

  • Guarantees that all replicas will converge to the same state eventually.
  • Suitable for systems that prioritize availability and speed over strong consistency.

• Examples:

  • Calendar applications where updates propagate asynchronously across devices.

• Challenges:

  • Conflicts arise from concurrent updates, requiring resolution strategies like “last writer wins” or merge algorithms.

• Strong Eventual Consistency:

  • Adds guarantees that all updates propagate to all replicas and replicas with the same updates converge to the same state.

Comparison of Models:

• CAP Theorem:

  • Distributed systems must trade off between consistency, availability, and partition tolerance during network partitions.

• Weaker Assumptions:

  • Eventual consistency requires minimal communication, allowing operations to proceed locally without waiting for network responses.
  • Strong eventual consistency maintains convergence while allowing asynchronous operation.

• Linearizable Get and Set:

  • Can be implemented with weaker assumptions than linearizable compare-and-swap (CAS).

Algorithms and Protocols:

• Two-Phase Commit and Consensus:

  • Require communication with a quorum and partial synchrony for progress.

• Read Repair:

  • Used in quorum reads to update stale replicas during a read operation.

• Broadcast Protocols:

  • Protocols like causal or reliable broadcast help disseminate updates in eventual consistency.

---

Key Excerpts with Clickable Timestamps

1. Introduction to Linearizability
   0:71: “Linearizability makes a replicated system look as if it were not replicated, with all operations appearing atomic.”

2. Limitations of Linearizability
   40:39: “Linearizability has limitations like high implementation costs, scalability bottlenecks, and availability issues.”

3. Introduction to Eventual Consistency
   126:79: “Eventual consistency guarantees that replicas converge to the same state after updates stop propagating.”

4. Calendar Example
   200:32: “In a calendar app, disconnected devices show how eventual consistency works and can lead to conflicts.”

5. CAP Theorem Explained
   306:24: “Systems must trade off between consistency, availability, and partition tolerance during network partitions.”

6. Conflict Resolution in Eventual Consistency
   618:399: “Concurrent updates in eventual consistency require conflict resolution strategies like ‘last writer wins.‘”

7. Strong Eventual Consistency
   478:879: “Strong eventual consistency ensures all updates propagate and replicas with the same updates converge to the same state.”

8. Comparison of Algorithms
   675:68: “Algorithms like atomic commit, consensus, and quorum-based reads and writes have varying trade-offs in communication and timing assumptions.”