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?

  • $\begingroup$ This is a great question, and I wish Eric would have elaborated a bit here. Is it linearizable or not? :) $\endgroup$
    – BMiner
    Commented Jul 16, 2020 at 2:43

5 Answers 5


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$.

  • $\begingroup$ The more I think about it, this sounds a whole awful lot like linearizability to me because all transactions are ordered. Sadly, sometimes these terms are subtle... Anyone disagree? I mean, the transactions are serializable, and they are totally ordered based on commit time. Perhaps the subtlety lies in how 2PC is implemented in Spanner? $\endgroup$
    – BMiner
    Commented Jul 16, 2020 at 2:39
  • $\begingroup$ @Bminer Linearizability is a consistency models that only applies to single objects, where transactions can involve multiple objects. $\endgroup$ Commented Jul 16, 2020 at 3:32
  • 2
    $\begingroup$ @LorinHochstein - Ha! That smells like mincing words. The whole point of the terminology is to help real people conceptualize what guarantees they get, especially with regard to transactions. Linearizability + serializability is the strongest guarantee, and I think that's what the Spanner docs are referring to with the term "external consistency." But, it begs the question: does anyone really know what "external consistency" means? :) $\endgroup$
    – BMiner
    Commented Oct 12, 2020 at 14:10
  • $\begingroup$ @BMiner We really need concrete examples, which tells those subtle differences among linearizability, serializability and external consistency. $\endgroup$
    – Lewis Chan
    Commented Aug 25, 2022 at 8:22
  • $\begingroup$ @LewisChan - I agree; that's my point. Definitions for linearizability and serializability are well-known; whereas, "external consistency" is a made-up term with an elusive definition. $\endgroup$
    – BMiner
    Commented Nov 7, 2022 at 18:33

There is a distinction between external consistency and strict serializability. I wrote a comment on it here https://stackoverflow.com/questions/60365103/differences-between-strict-serializable-and-external-consistency/65853495#65853495.

The difference is that strict serializability imposes no order on concurrent transactions, whereas external consistency does (the order in which they commit).


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.


When mentioning "external consistency", Brewer references B. Liskov. Practical Uses of Synchronized Clocks in Distributed Systems. ACM Principles of Distributed Computing (PODC). Montreal, Canada, August 1991.

Liskov, in term, references Gifford D.K. Information Storage in a Decentralized Computer System. Technical Report CSL-81-8, Xerox Corporation, March, 1983

Here's how Gifford defines external consistency:

External consistency guarantees that a transaction will always receive current information. Using the concepts we have just introduced, we can provide a formal definition of external consistency. The actual time order in which transactions complete defines a unique serial schedule. This serial schedule is called the external schedule. A system is said to provide external consistency if it guarantees that the schedule it will use to process a set of transactions is equivalent to its external schedule.

As @Oleg mentions, this sounds like strict serializability.

  • $\begingroup$ Is it just me or does that definition of external consistency make very little sense? It's saying "A system is said to provide external consistency if it guarantees that the schedule it will use to process a set of transactions is equivalent to the actual time order in which transactions complete." $\endgroup$ Commented Aug 8, 2021 at 10:32

To my limited understanding there is not much differency bw external consistency and linearizability:

Definition of linearizability [1] is

  1. The extended list can be re-expressed as a sequential history (is serializable).
  2. That sequential history is a subset of the original unextended list.

And 2. means:

If an operation op1 completes (gets a response) before op2 begins (invokes), then op1 precedes op2 in history.

And that is what exactly Google calls external consistency [2]:

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

Replace op with tx, response with commit and here we are. They seem to be essentially the same.

[1] https://en.wikipedia.org/wiki/Linearizability
[2] https://storage.googleapis.com/pub-tools-public-publication-data/pdf/45855.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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