In Spanner, TrueTime & The CAP Theorem, Eric Brewer writes:

One subtle thing about Spanner is that it gets serializability from locks, but it gets external consistency (similar to linearizability) from TrueTime [emphasis added].

What is the definition of external consistency, and how does it differ from linearizability?


External consistency doesn't have a fixed meaning. In this context, it has the meaning appearing in the very next sentence in the document:

For any two transactions, $T_1$ and $T_2$ (even if on opposite sides of the globe): if $T_2$ starts to commit after $T_1$ finishes committing, then the timestamp for $T_2$ is greater than the timestamp for $T_1$.


You can think about external consistency from transactions (Tx) isolation and order point of view. In Tx isolation speak the external consistency is equivalent to the strict serializable isolation, where 'strict' is the real-time constraint part (as in linearizability).

That again all means that to a system client observable Tx side effects are equivalent to a system, where all Tx take place in isolation without any concurrency and where their real-time ordering, as seen by the client, is preserved. More importantly this same ordering is seen by any other unrelated client.

Read more about the distinction at this blog.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.