Consistency vs. Availability in Distributed Cyber-Physical 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 extend consistency and availability to refer to cyber-physical properties such as the state of the physical system and delays in actuation. We have further 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 cyber-physical 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 embedded software.

Electronic Downloads

• https://dl.acm.org/doi/10.1145/3609119

---

Citation Formats

• APA
  

                  
  Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard. (2023). Consistency vs. Availability in Distributed Cyber-Physical Systems. In ACM Transactions on Embedded Computing Systems (TECS)                      
                  
                  

• MLA
  

                  
  Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard. "Consistency vs. Availability in Distributed Cyber-Physical Systems." 2023. ACM Transactions on Embedded Computing Systems (TECS),                       
                  
                  

• Chicago
  

                  
  Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard. "Consistency vs. Availability in Distributed Cyber-Physical Systems." 2023. In ACM Transactions on Embedded Computing Systems (TECS)                      
                  
                  

• BibTeX
  

                      
  @article{LeeEtAl:23:CAL_CPS,
  	author = {Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard},
  	title = {Consistency vs. Availability in Distributed Cyber-Physical Systems},
  	journal = {ACM Transactions on Embedded Computing Systems (TECS)},
  	month = {September},
  	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 extend consistency and availability to refer to cyber-physical properties such as the state of the physical system and delays in actuation. We have further 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 cyber-physical 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 embedded software.},
  	URL = {https://dl.acm.org/doi/10.1145/3609119}}