Reconjectures the 'P' in the CAP theorem as *partial progress*: rather than treating a network partition as forcing a binary choice between consistency and total availability, a system can let partitioned replicas keep making non-zero, bounded progress on the requests they can still order, then deterministically reconcile once the partition heals. The paper realizes this with CASSANDRA, a Paxos-style consensus protocol in which each partitioned side independently selects a 'strongest proposal' (ranked first by the number of already-committed transactions, then by log suffix, then by proposer rank) and, on recovery, merges divergent states by replaying the losing side's operations against the winning proposal's committed order. This targets the non-monotonic (non-CALM) applications that coordination-free designs cannot already keep available under asynchrony.
Each application developer desires to provide its users with consistent results and an always-available system despite failures. Boldly, the CALM theorem disagrees. It states that it is hard to desig…