2019/01/07 by Joseph M. Hellerstein, Peter Alvaro, Hellerstein, Joseph M. +1 · 6 voices · 1 citation
Computer Science · #Distributed and Parallel Computing Systems #Distributed systems and fault tolerance #Parallel Computing and Optimization Techniques #cs.DB #cs.DC #cs.PL #cs.SE
paper · pdf · doi:10.48550/arxiv.1901.01930
openalex publication_date 2019/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.