A key concern in modern distributed systems is to avoid the cost of coordination while maintaining consistent semantics. Until recently, there was no answer to the question of when coordination is actually required. In this paper we present an informal introduction to the CALM Theorem, which answers this question precisely by moving up from traditional storage consistency to consider properties of programs. CALM is an acronym for "consistency as logical monotonicity". The CALM Theorem shows that the programs that have consistent, coordination-free distributed implementations are exactly the programs that can be expressed in monotonic logic. This theoretical result has practical implications for developers of distributed applications. We show how CALM provides a constructive application-level counterpart to conventional "systems" wisdom, such as the apparently negative results of the CAP Theorem. We also discuss ways that monotonic thinking can influence distributed systems design, and how new programming language designs and tools can help developers write consistent, coordination-free code.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
> How do you build a system around a database where values can no longer be valid at any time?
This is a difficult problem, and there aren't nice general solutions. If you read the original Amazon Dynamo paper, for example, there's a good discussion of why eventual consistency is OK for their applications (https://www.allthingsdistributed.com/files/amazon-dynamo-sos...), and more in Werner Vogel's CACM article from two years later (https://dl.acm.org/doi/10.1145/1435417.1435432).
There are conceptual frameworks (like CALM https://arxiv.org/pdf/1901.01930.pdf) that provide a way to reason through the behavior of systems under eventual consistency (and provide a path to…
Read the full comment
data structures with behavior that's easier to reason about than last-writer-wins).
> My script abandons the C(onsistency) of CAP and maintains (A)vailability and (P)artition tolerance.
I'd recommend you check out "Rethinking Eventual Consistency" (https://www.microsoft.com/en-us/research/publication/rethink...). PACELC is a better tool than CAP for thinking about this stuff, but Figure 1 in that paper is even better. Specifically, there is no need to abandon either availability or consistency in the majority partition.
The confusion here comes from CAP's unhelpful use of "total availability", which isn't a system property that most datacenter applications care about. Mobile, IoT, and other frequently-disconnected applications do care about it.
Interesting that neither the article nor the comments mention the CALM theorem [0], which gives a framework to explain when coordination-free consistency is possible, and is arguably the big idea behind SEC.
[0] https://arxiv.org/abs/1901.01930
> Perhaps others have made this connection before…it does feel like some sort of universal law of physics.
This has been on my mind too, and I can’t help but think the fundamental concept underpinning it all is causality.
Reading about “consistency as logical monotonicity” — CALM [0], after diving into Spanner, there’s definitely something to databases beyond CAP.
I’m yet to find a simple and clear law or theorem that captures what you’re hinting to, but it feels like we must be getting close. This has been bouncing around my head for a few years since I first wrote a toy CRDT DB.
It seems to show up anywhere we have more than one system with independent memory (a place…
Read the full comment
where state can be held), needs to maintain a shared representation or fact about something.
Within one memory (akin to a reference frame in quantum physics), we can do anything we want. We can mutate state without any interaction or interference from the outside world. This also sounds like a pure function. By itself, this is academic, theoretical—it does not, it does not exist. If a tree falls in the woods.
So if we want to interact with any other systems, we then need to coordinate, and the question is how.
The issue and pattern seems to rhyme everywhere. CPUs, HDD, SSD, file systems, networks, UIs, people, teams, etc. The best possible collaboration seems to be that which requires the least coordination. Money is a good example here, someone can string together a series of products from companies who know nothing about each other, by coordinating with money - as a means of exchange. Not to mention being able to buy complex technology with no idea the supply chain behind it. I don’t have to coordinate with a mine to use a computer, which contains something from said mine.
It sort of looks like distributed databases build a virtual memory on top of many smaller memories, which need to share some parts with each other to protect the system as a whole.
New information may need a few writes before it can be considered a new fact. I think this is an implementation detail, in that it’s irrelevant to the observer (who has no control over it).
This isn’t eventual consistency, which is perhaps the cruder form of this where the implementation detail above is wide open for all to see. Instead new information is available immediately, just your definition of immediately is different to the databases.
It follows then, that as an observer of the system you cannot violate causality in any way by learning information from the future, while they are still in the past.
My understanding from Spanner is that when you ask for a read, you provide or are issued a timestamp which provides the causal information to determine what you are allowed to know.
The system can then maintain both a true and correct representation of what it knows, and an incomplete working memory of what it is trying to know next (the writes which need to be committed into multiple memories).
Memory being anything from ram, ssd, carrier pigeon, lines in sand, etc.
I think where this breaks most of our brains is that it’s a universe simulation.
And both time and causality are fundamental invariants of the stability of the system, but are leaky abstractions that we need to deal with.
In CALM this is abstracted into what is effectively entropy. If your program never moves backward in time/loses entropy it’s CALM (I think). In earlier works I think Lamport and vector clocks were used, in Spanner it’s based on very precise measurements of our own time, where the maximum speed of information (ie speed of light) is the greater of the smallest unit of time we can measure (the precision of the GPS clock) and the time it takes for new data to become available in the system.
The other part where this differs from the read world is that the speed of information, the latency of a request, is different for reads and writes. Not true in the quantum world where an everything is a wrote (I think). Then, consider that in our own reference frame we can do a huge amount of work while waiting for a db read/write, something that would violate the speed of light if not in our virtualised world.
We cannot break causality in the world we live and breathe in, but we do it all the time in our simulated ones.
[0] https://arxiv.org/abs/1901.01930
don't forget about calm. its a shame that that isn't the default we reach for, and only struggle when we really need stronger latency.
https://arxiv.org/abs/1901.01930
The article should really mention CALM (Consistency as Logical Monotonicity)[1], it's much easier to understand and a more fundamental result than CAP. It is also much more applicable and enables people with little experience to build extremely robust distributed systems.
Idempotence, CRDTs, WALs, Raft, they are all special cases of the CALM principle.
[1]: https://arxiv.org/pdf/1901.01930
You might be thinking of this [1] paper? The core idea being if your problem space lends itself to monotonicity (see the paper for a more precise definition than I can give), then you can build a globally consistent database (around a CRDT) where the end-user doesn't need to concern themselves with inconsistent states while consistency is reached.
[1] https://arxiv.org/pdf/1901.01930.pdf
> That function can do whatever it wants, including any number of reads, writes, and arbitrary logic based on the reads. But critically, it can't talk back to the calling client, except for to send the final result.
If that function can still do everything the client did and the client still has to wait for a transaction - you are only eliminating interactive communications overhead, not actually improving or simplifying anything fundamentally. There is still consensus, coordination happening during that waiting and all of this is still fundamentally incompatible with computers spread across the globe communicating over unreliable links.
What would actually be a big…
Read the full comment
improvement is eliminating waiting for coordination, but would require some change in programming model [1].
> The Calvin way is so much easier, it seems like there must be some very good reason that it's not what CockroachDB does.
It's just not "so much easier", that's the reason.
[1] https://arxiv.org/pdf/1901.01930.pdf
There is something based on Bloom IIRC, but the whole concept should be well-described and discoverable from the Keeping CALM paper: https://arxiv.org/abs/1901.01930
> Distributed algorithms require more coordination.
Sometimes! There's a whole body of research about when distributed algorithms require coordination. One example is the CALM theorem (https://arxiv.org/abs/1901.01930), and another is the ways that scalable database systems avoid read coordination (https://brooker.co.za/blog/2025/02/04/versioning.html).
> Distribution also means you have fewer natural correctness guarantees, so you need more administrative overhead to avoid race conditions.
I don't believe this is true.
> If we know the exact sequence of computations, we can aim to minimize cache misses.
Sure, but it's not clear why this is possible in a local context and…
Read the full comment
not a distributed one (and, in fact, in may be easier in the distributed context). One example of how it's easier in the distributed context is snapshotting in MemoryDB (https://brooker.co.za/blog/2024/04/25/memorydb.html).
> But then you lose the assumption "recently inserted rows are close together in the index", which I've read can lead to significant slowdowns.
Or significant speed ups because you avoid false sharing!
> Maybe there's also a cultural element to this conflict. What if the engineers interested in "efficiency" are different from the engineers interested in "horizontal scaling"?
This is, of course, a false dichotomy. Distributed systems don't only (or even primarily, in most cases) exist for scaling, but availability, resilience, durability, business continuity, and other concerns.
To make this purely about scalability is naive.
> I'm not sure where this fits in but scaling a volume of tasks conflicts less than scaling individual tasks
Indeed. Coordination avoidance is the fundamental mechanism of scaling. This is visible in CALM, in Amdahl's law, and in many of the other frameworks for thinking through this space.
> If you have 1,000 machines and need to crunch one big graph, you probably want the most scalable algorithm. If you instead have 50,000 small graphs, you probably want the most efficient algorithm, which you then run on all 1,000 machines
False dichotomy again. Algorithms can be both efficient and scalable, and the true shape of the trade-off between them is both super interesting and an ongoing research area.
I normally enjoy Hillel's writing and thoughtfulness, but this post seems like a big miss.
*Between two distributed systems that don't share the same transactionality domain or are not logically monotone.
It's easy to see that moving data from one row to another is doable in a clustered database, and could be interpreted as a message being delivered.
The point is that you can get exactly once delivery, if your whole system is either idempotent, or you can treat the distributed system as one single unit that can be rolled back together (i.e. side effect free wrt. some other system outside the domain).
Both are cases of some form of logical monotonicity, idempotence is easier to see, but transactionality is also based on monotonicity through the used WALs and algorithms like Raft.
The article should really mention CALM (Consistency as logical monotnicity), it's much easier to understand and a more fundamental result than CAP. https://arxiv.org/pdf/1901.01930
There is a theorem called CALM[1] (Consistency as Logical Monotonicity) that shows that systems are eventually consistent iff they are monotonic.
I find that reasoning about consistency is much easier from that perspective, for example it immediately gives you an intuition on why individual CRDTs work.
1: https://arxiv.org/abs/1901.01930
Completely agree. In-region (e.g. at the scale of a US state), CP seems like a clear winner. For more geo-distributed latency becomes challenging, and in environments like IoT and mobile unreliable connectivity becomes challenging. If you're there, you need a principled way of approaching AP (e.g. CRDTs or CALM https://arxiv.org/pdf/1901.01930.pdf).
It's absolutely bonkers that TLA+ struggles with this, given that a system is eventually consistent IFF it is logically monotonic (CALM) [1].
This also doesn't make intuitive sense to me. Model checking should be easier for monotonic models, because because the total model check can be viewed as a consistent sum of all partial checks. I've collaborated on a monotonic parser once, which was essentially a monotonic logic programming language. One of the key insights was that you can replace backtracking search of the state space with solving a set covering problem where you attempt to find the union of all sub-parses that cover the sentence fully. So for monotonic systems you should be able to dynamically program / divide and conquer the heck out of it.
1. https://arxiv.org/abs/1901.01930
yeah, that was really brief. I was actually hoping for someone to bring up https://arxiv.org/abs/1901.01930 (keeping CALM) for an interesting alternative
Are you familiar with Joe Hellerstein and Peter Alvaro's work in this space? CALM provides something of a unifying theory of mergeable operations, of which CRDTs are an "object orientated" special case: https://arxiv.org/pdf/1901.01930.pdf
In practice, designers choose coordination-heavy protocols like consensus for a number of reasons. One is because writes don't or can't be merged. Operations as basic as simple assignment (x = 1;) can't be merged, so that's very real. Another is because readers can't tolerate weak consistency, because their business logic needs to make decisions at a particular point in time.
You're right that the thinking behind CRDTs (and CALM) is useful in reasoning through determinism in this context. The determinism problem, though, is easier than the general monotonicity problem, because only determinism is required and not associativity or commutativity.
In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.