I. Introduction

1. Operations

An operation is a transition from one state to another state.

2. Invocation & Completion Times

In distributed systems, an operation might mean sending a request to a server, and receiving a response.

To model this, we say that each operation has an invocation time and, should it complete, a strictly greater completion time, both given by an imaginary, perfectly synchronised, globally accessible clock. We refer to these clocks as providing a real-time order

3. Concurrency

Two operations might overlap in time. For instance, given two operations A and B, A could begin, B could begin, A could complete, and then B could complete.

We say that two operations A and B are concurrent if there is some time during which A and B are both executing.

II. Consistency Model:

A consistency model is a set of guarantees made by the distributed system in terms of the ordering of operations.

It is a contract between a distributed system and the applications that run on it

There are performance and simplicity tradeoff:

• Stronger consistency models:

  • Easier to write applications
  • More guarantees for the system to ensure

• Weaker consistency models:

  • Harder to write applications
  • Fewer guarantees for the system to ensure

III. Strict Consistency:

All replicas execute transactions in some total order

That total order preserves the real-time ordering between transactions

• If transaction A completes before B begins, then A is ordered before B in real-time
• If neither A nor B completes before the other begins, then there is no realtime order. But there must be some total order.

Strict consistency is a transactional model: It guarantees that transactions take place atomically, a transaction’s sub-operations do not appear to interleave with sub-operations from other transactions.

IV. Linearisability:

All replicas execute operations in some total order

That total order preserves the real-time ordering between operations

• If operation A completes before B begins, then A is ordered before B in real-time
• If neither A nor B completes before the other begins, then there is no realtime order. But there must be some total order.

Linearisability is a single-object model, but the scope of “an object” varies. Some systems provide linearisability on individual keys in a key-value store; others might provide linearisable operations on multiple keys in a table.

V. Sequential Consistency:

All replicas execute operations in some total order

That total order preserves the process ordering between operations

• If process P issues operation A before operation B, then A is ordered before B by the process order (i.e., preserves local ordering)
• If operations A and B are done by different processes then there is no process order between them. But there must be some total order.

VI. Causal Consistency:

Writes that are causally related must be seen by all processes in same order.

Concurrent writes may be seen in a different order on different processes.

Causal consistency captures the notion that causally-related operations should appear in the same order on all processes—though processes may disagree about the order of causally independent operations.

VII. Eventual Consistency:

All replicas eventually converge to the same state.