A Preliminary Model of Coordination-free Consistency

Author(s): Shulu Li and Edward A. Lee

Abstract
Building consistent distributed systems has largely depended on complex coordination strategies that are not only tricky to implement, but also take a toll on performance as they require nodes to wait for coordination messages. In this paper, we explore the conditions under which no coordination is required to guarantee consistency. We present a simple and succinct theoretical model for distributed computation that separates coordination from computation. The main contribution of this work is mathematically defining concepts in distributed computing such as strong eventual consistency, consistency, consistent under partition, confluence, coordination-free, and monotonicity. Based on these definitions, we prove necessary and sufficient conditions for strong eventual consistency and give a proof of the CALM theorem from a distributed computation perspective.

Electronic Downloads

• https://arxiv.org/abs/2504.01141

---

Citation Formats

• APA
  

                  
  Shulu Li and Edward A. Lee. (2025). A Preliminary Model of Coordination-free Consistency. In arXiv:2412.01799v1 [cs.RO]                      
                  
                  

• MLA
  

                  
  Shulu Li and Edward A. Lee. "A Preliminary Model of Coordination-free Consistency." 2025. arXiv:2412.01799v1 [cs.RO],                       
                  
                  

• Chicago
  

                  
  Shulu Li and Edward A. Lee. "A Preliminary Model of Coordination-free Consistency." 2025. In arXiv:2412.01799v1 [cs.RO]                      
                  
                  

• BibTeX
  

                      
  @article{LiLee:25:CALMx,
  	author = {Shulu Li and Edward A. Lee},
  	title = {A Preliminary Model of Coordination-free Consistency},
  	journal = {arXiv:2412.01799v1 [cs.RO]},
  	month = {Apr},
  	year = {2025},
  	abstract = {Building consistent distributed systems has largely depended on complex coordination strategies that are not only tricky to implement, but also take a toll on performance as they require nodes to wait for coordination messages. In this paper, we explore the conditions under which no coordination is required to guarantee consistency. We present a simple and succinct theoretical model for distributed computation that separates coordination from computation. The main contribution of this work is mathematically defining concepts in distributed computing such as strong eventual consistency, consistency, consistent under partition, confluence, coordination-free, and monotonicity. Based on these definitions, we prove necessary and sufficient conditions for strong eventual consistency and give a proof of the CALM theorem from a distributed computation perspective.},
  	URL = {https://arxiv.org/abs/2504.01141}}