ACID, BASE and CALM

Most developers will be familiar with the acronym ACID, which stands for Atomicity, Consistency, Isolation & Durability regarding database transactions. ACID is well known and applicable for single database instances, but cannot be uphold for distributed transactions. Regarding the CAP theorem, it chooses Consistency and Partition tolerance. Building an application with ACID capabilities mostly requires just wrapping critical paths under transactions and properly configuring the isolation level of the database system.


With the NoSQL movement appeared another acronym, BASE: Basically Available, Soft state, Eventual consistency. It provides the Availability and Partition Tolerance from CAP, but eventual consistency requires deeper architectural and even product changes in any system (e.g. your clients can see stale or transitional data, or fail to see recently created data units).


Today while reading about distributed systems and consistency I came across a third acronym, CALM. Apart from the obvious jokes around "keep CALM and ...", while far from easy as the article "Keeping CALM: When Distributed Consistency Is Easy" implies, it is interesting regarding two key points:

  • It proposes that "A problem has a consistent, coordination-free distributed implementation if and only if it is monotonic". By reasoning about program outcomes, rather than mutations to storage, and avoiding linearity and ordering, theoretically we can build software that doesn't needs to coordinate at all (with the concept of "confluence" to a final correct result).
  • It observes that "Coordination-freeness is equivalent to availability under partition", thereby fulfilling all 3 CAP properties for those cases where problems are monotonic.

So, if we found a solution to distributed agreement, why is not so known? Where's the catch? Well, non-linearity and confluent operations are very hard to implement with imperative languages, they are more apt for functional programming. Up to the point that the theorem authors created the Bloom programming language, with the purpose of build distributed systems software. So here the cost of implementation is as huge as probably requiring a full rewrite of parts of the system (and of course in a functional paradigm).


I left on purpose well-known consensus protocols like 2PC, Two-Phase Commit, and the Paxos family, because they bet strongly on agreement mechanics to achieve CAP, while BASE and CALM propose and/or provide approaches that that "skip" or workaround consensus.

But I wanted to mention CALM also because the ACM article represents an interesting journey on traditional distributed systems problems, with examples using familiar scenarios like a distributed shopping cart. I'd like to keep at hand a list of terms and a few notes about the topic, so this small post does the job.

by Kartones @ 2020-11-02

Comments? Share via Twitter Share via Linkedin Share via Mastodon