Heisenberg and the CAP theorem

For many years I've been working on extended transactions protocols. The CORBA Activity Service, WS-TX and now REST-TX are efforts on that road. There are many similarities between the problems of long running transactions and large scale replication, so the facts that I did my PhD on both gave me some insights to helping resolve both.

One of the early pieces of research I did was on combining replication and transactions to create consistency domains, where a large number of replicas are split into domains and each domain (replica group) has a relationship with the others in terms of their state and level of consistency. Rather than try to maintain strong consistency between all of the replicas, which incurs overhead proportional to the number of replicas as well as their physical locality, we keep the number of replicas per domain small (and hopefully related) and grow the number of domains if necessary. Then each domain has a degrees of inconsistency with others in the environment.

The basic idea behind the model is that of eventual consistency: in a quiescent period all of the domains would have the same state, but during active periods there is no notion of global/strong consistency. The protocol ensures that state changes flow between domains at a predefined rate (using transactions). A client of the inconsistent replica group can enquire of a domain the state at any time, but may not get the global state, since not all updates will have propagated. Alternatively a client can request the global state but may not know the time it will take to be returned.

If you know Heisenbergs Uncertainty Principle then you'll know that it means you cannot determine the momentum and position of a particle at the same time (or other related properties). Thus it was fairly natural for me to use this analogy when describing the above protocol: an observer cannot know the global state of the system and when that will be the steady state at the same moment, i.e., it's one or the other. It's not a perfect analogy, but in a time when others seemed to like to bring physics into computing it seemed appropriate.

Now of course the original work was before the CAP theorem was formalised. So today we see people referring to that whenever they need to talk about relaxing consistency. And of course that is the right thing to do; if I were reviewing a paper today that was about relaxing consistency and the authors didn't reference CAP then I'd either reject it or have a few stern words to say to them. But I still thing Heisenberg is a way cooler analogy to make. However, I do admit to being slightly biased!