Trading Off Consistency and Availability in Tiered Heterogeneous Distributed Systems

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

Citation
Edward A. Lee, Soroush Bateni, Shaokai Lin, Marten Lohstroh, and Christian Menard. "Trading Off Consistency and Availability in Tiered Heterogeneous Distributed Systems". Intelligent Computing, 2(0013), February 2023.

Abstract
Tiered distributed computing systems, where components run in Internet-of-things devices, in edge computers, and in the cloud, introduce unique difficulties in maintaining consistency of shared data while ensuring availability. A major source of difficulty is the highly variable network latencies that applications must deal with. It is well known in distributed computing that when network latencies rise sufficiently, one or both of consistency and availability must be sacrificed. This paper quantifies consistency and availability and gives an algebraic relationship between these quantities and network latencies. The algebraic relation is linear in a max-plus algebra and supports heterogeneous networks, where the communication latency between 2 components may differ from the latency between another 2 components. We show how to make use this algebraic relation to guide design, enabling software designers to specify consistency and availability requirements, and to derive from those the requirements on network latencies. We show how to design systems to fail in predictable ways when the network latency requirements are violated, by choosing to sacrifice either consistency or availability.

Electronic Downloads

• https://doi.org/10.34133/icomputing.0013

---

Citation Formats

• HTML
  

                  
  Edward A. Lee, Soroush Bateni, Shaokai Lin, Marten Lohstroh, and Christian Menard.
  "<a href="https://www.icyphy.org/publications/2023_LeeEtAl_CAL_IC/">Trading Off Consistency and Availability in Tiered Heterogeneous Distributed Systems</a>".
  <i>Intelligent Computing</i>, 2(0013), February 2023.
                  
                  

• Plain Text
  

                  
  Edward A. Lee, Soroush Bateni, Shaokai Lin, Marten Lohstroh, and Christian Menard.
  "Trading Off Consistency and Availability in Tiered Heterogeneous Distributed Systems".
  Intelligent Computing, 2(0013), February 2023.
                  
                  

• BibTeX
  

                      
  @article{LeeEtAl:23:CAL_IC,
  	author = {Edward A. Lee, Soroush Bateni, Shaokai Lin, Marten Lohstroh, and Christian Menard},
  	title = {Trading Off Consistency and Availability in Tiered Heterogeneous Distributed Systems},
  	journal = {Intelligent Computing},
  	volume = {2},
  	number = {0013},
  	month = {February},
  	year = {2023},
  	doi = {10.34133/icomputing.0013},
  	abstract = {Tiered distributed computing systems, where components run in Internet-of-things devices, in edge computers, and in the cloud, introduce unique difficulties in maintaining consistency of shared data while ensuring availability. A major source of difficulty is the highly variable network latencies that applications must deal with. It is well known in distributed computing that when network latencies rise sufficiently, one or both of consistency and availability must be sacrificed. This paper quantifies consistency and availability and gives an algebraic relationship between these quantities and network latencies. The algebraic relation is linear in a max-plus algebra and supports heterogeneous networks, where the communication latency between 2 components may differ from the latency between another 2 components. We show how to make use this algebraic relation to guide design, enabling software designers to specify consistency and availability requirements, and to derive from those the requirements on network latencies. We show how to design systems to fail in predictable ways when the network latency requirements are violated, by choosing to sacrifice either consistency or availability.},
  	URL = {https://www.icyphy.org/publications/2023_LeeEtAl_CAL_IC/}
  }