What
Strong consistency, allows different outcomes.
Define correctness for how a service behaves in the face of concurrent client requests.
Roughly speaking, it specifies that the service should appear as if it executes requests one at a time as they arrive.
We can say that a service is linearizable if every history it can generate is linearizable.
A history is linearizable if you can assign a “linearization point” (a time) to each operation, where each operation’s point lies between the times the client sent the request and received the response, and the history’s response values are the same as you’d get if you executed the requests one at a time in point order. If no assignment of linearization points satisfies these two requirements, the history is not linearizable.
An important consequence of linearizability is that the service has freedom in the order in which it executes concurrent (overlapping-in-time) operations. In particular, if requests from client C1 and C2 are concurrent, the server could execute C2’s request first even if C1 sends its request message before C2. On the other hand, if C1 received a response before C2 sent its request, linearizability requires the service to act as if it executed C1’s request before C2’s (i.e. C2’s operation is required to observe the effects of C1’s operation, if any).
In general, different models differ in how intuitive they are for application programmers, and how much performance you can get with them. For example, eventual consistency allows many anomalous results (e.g. even if a write has completed, subsequent reads might not see it), but in a distributed/replicated setting can be implemented with higher performance than linearizability.
Linearizability is also called strong consistency model
- All functions appear to occur instantly at their linearization
point, behaving as specified by the sequential definition.
Fault Tolerant
- duplicate requests from retransmissions must be suppressed!
History
- a history is linearizable if
- you can find a point in time for each operation between its invocation and response, and
- the history’s result values are the same as serial execution in that point order.
- Result: reads must return fresh data: stale values aren’t linearizable