Consistency vs. Availability in Distributed Real-Time Systems

Author(s): Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard

Abstract
In distributed applications, Brewer's CAP theorem tells us that when networks become partitioned (P), one must give up either consistency (C) or availability (A). Consistency is agreement on the values of shared variables; availability is the ability to respond to reads and writes accessing those shared variables. Availability is a real-time property whereas consistency is a logical property. We have extended the CAP theorem to relate quantitative measures of these two properties to quantitative measures of communication and computation latency (L), obtaining a relation called the CAL theorem that is linear in a max-plus algebra. This paper shows how to use the CAL theorem in various ways to help design real-time systems. We develop a methodology for systematically trading off availability and consistency in application-specific ways and to guide the system designer when putting functionality in end devices, in edge computers, or in the cloud. We build on the Lingua Franca coordination language to provide system designers with concrete analysis and design tools to make the required tradeoffs in deployable software.

Electronic Downloads

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

---

Citation Formats

• APA
  

                  
  Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard. (2023). Consistency vs. Availability in Distributed Real-Time Systems. In arXiv:2301.08906 [cs.DC]                      
                  
                  

• MLA
  

                  
  Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard. "Consistency vs. Availability in Distributed Real-Time Systems." 2023. arXiv:2301.08906 [cs.DC],                       
                  
                  

• Chicago
  

                  
  Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard. "Consistency vs. Availability in Distributed Real-Time Systems." 2023. In arXiv:2301.08906 [cs.DC]                      
                  
                  

• BibTeX
  

                      
  @article{Lee:23:CAL,
  	author = {Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard},
  	title = {Consistency vs. Availability in Distributed Real-Time Systems},
  	journal = {arXiv:2301.08906 [cs.DC]},
  	month = {January},
  	year = {2023},
  	abstract = {In distributed applications, Brewer's CAP theorem tells us that when networks become partitioned (P), one must give up either consistency (C) or availability (A). Consistency is agreement on the values of shared variables; availability is the ability to respond to reads and writes accessing those shared variables. Availability is a real-time property whereas consistency is a logical property. We have extended the CAP theorem to relate quantitative measures of these two properties to quantitative measures of communication and computation latency (L), obtaining a relation called the CAL theorem that is linear in a max-plus algebra. This paper shows how to use the CAL theorem in various ways to help design real-time systems. We develop a methodology for systematically trading off availability and consistency in application-specific ways and to guide the system designer when putting functionality in end devices, in edge computers, or in the cloud. We build on the Lingua Franca coordination language to provide system designers with concrete analysis and design tools to make the required tradeoffs in deployable software.},
  	URL = {https://arxiv.org/abs/2301.08906}}