Issue #37 - Consistency & Coordination
When Does Consistency Require Coordination?
Another weekend, another weekend read, this time all about the question of When Does Consistency Require Coordination
I am writing a book on Thinking in Distributed Systems. 12 chapters, one chapter per month, full of diagrams, illustrations, and examples, all about distributed systems.
We often believe that stronger consistency requires more coordination thus reducing availability. However, when does consistency actually require coordination?! What exactly is the determining factor?!
Peter Bailis discusses the relationship of consistency and coordination and introduces the notion of invariant confluence, the precise answer to the previous question:
If invariant confluence holds, there exists a coordination-free execution that preserves consistency.
If invariant confluence does not hold, there does not coordination-free execution that preserves consistency.
The intuition behind invariant confluence is straightforward. We capture consistency as invariants, e.g. no user has a negative account balance. If we commit an operation on a local copy, we must make sure that no other operation could violate our invariants upon merge. In that case, no coordination is necessary.
All local commit decisions must be globally invariant-preserving.
If I add money to a user’s account with a positive account balance, the balance cannot possibly dip below zero. I do not have to coordinate with other replicas.
If I subtract money from a user’s account with a positive account balance, the balance may indeed dip below zero. I do have to coordinate with other replicas.
The key is to specify correctness in terms of invariants rather than reads and writes.
Enjoy this insightful Weekend Read!
Happy Reading
When Does Consistency Require Coordination?
Peter Bailis
My coauthors and I recently published a paper answering one of my longest standing research questions: when does consistency require coordination? It’s well known that many “strong” properties like “ACID” serializability and linearizability are not achievable without coordination, or synchronous communication between concurrent operations. But why is it that we can still implement reliable distributed counters and shopping carts that don’t lose writes, build indexes that are “consistent” with base data, and ensure useful properties like read-your-writes—all without coordination? Why do some operations require coordination while others don’t, and what’s the fundamental difference at play?