{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T19:16:51Z","timestamp":1783538211369,"version":"3.55.0"},"reference-count":43,"publisher":"American Association for the Advancement of Science (AAAS)","content-domain":{"domain":["spj.science.org"],"crossmark-restriction":true},"short-container-title":["Intell Comput"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p>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 of 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.<\/jats:p>","DOI":"10.34133\/icomputing.0013","type":"journal-article","created":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T14:37:55Z","timestamp":1674225475000},"update-policy":"https:\/\/doi.org\/10.34133\/aaas_crossmark_01","source":"Crossref","is-referenced-by-count":7,"title":["Trading Off Consistency and Availability in Tiered Heterogeneous Distributed Systems"],"prefix":"10.34133","volume":"2","author":[{"given":"Edward A.","family":"Lee","sequence":"first","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Soroush","family":"Bateni","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaokai","family":"Lin","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marten","family":"Lohstroh","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Menard","sequence":"additional","affiliation":[{"name":"TU Dresden, Dresden, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"221","published-online":{"date-parts":[[2023,2,15]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"crossref","unstructured":"Brewer E. Towards robust distributed system. Paper presented at: Symposium on Principles of Distributed Computing (PODC) Keynote talk; 2000 Jul 19; Portland OR.","DOI":"10.1145\/343477.343502"},{"issue":"2","key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1109\/MC.2012.37","article-title":"CAP twelve years later: How the \"rules\" have changed","volume":"45","author":"Brewer E","unstructured":"Brewer E. CAP twelve years later: How the \"rules\" have changed. IEEE Computer. 45(2):23\u201329.","journal-title":"IEEE Computer"},{"key":"e_1_3_3_4_2","unstructured":"Brewer E. Spanner TrueTime & the CAP theorem. Google Report. 14 Feb 2017. [accessed 20 Sep 2022] https:\/\/storage.googleapis.com\/pub-tools-public-publication-data\/pdf\/45855.pdf"},{"key":"e_1_3_3_5_2","unstructured":"Lee EA Bateni S Lin S Lohstroh M Menard C. Quantifying and generalizing the CAP theorem. arXiv. 2021. https:\/\/arxiv.org\/abs\/2109.07771."},{"issue":"6","key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1109\/JPROC.2019.2905334","article-title":"A perspective on IEEE time-sensitive networking for industrial communication and automation systems","volume":"107","author":"Lo Bello L","year":"2019","unstructured":"Lo Bello L, Steiner W. A perspective on IEEE time-sensitive networking for industrial communication and automation systems. Proc IEEE. 2019;107(6):1094\u20131120.","journal-title":"Proc IEEE"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","unstructured":"Zhang B Jin X Ratnasamy S Wawrzynek J Lee EA. AWStream: Adaptive wide-area streaming analytics. Paper presented at: Proceedings of SIGCOMM ACM; 2018 Aug 20; Budapest Hungary.","DOI":"10.1145\/3230543.3230554"},{"issue":"4","key":"e_1_3_3_8_2","doi-asserted-by":"crossref","DOI":"10.1145\/3448128","article-title":"Toward a lingua franca for deterministic concurrent systems","volume":"20","author":"Lohstroh M","year":"2021","unstructured":"Lohstroh M, Menard C, Bateni S, Lee EA. Toward a lingua franca for deterministic concurrent systems. ACM Trans Embed Comput Syst. 2021;20(4):Article 36.","journal-title":"ACM Trans Embed Comput Syst"},{"key":"e_1_3_3_9_2","unstructured":"Kuhn R. Reactive design patterns . Shelter Island (NY): Manning Publications Co.; 2017."},{"issue":"2","key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/564585.564601","article-title":"Brewer\u2019s conjecture and the feasibility of consistent, available, partition-tolerant web services","volume":"33","author":"Gilbert S","year":"2002","unstructured":"Gilbert S, Lynch N. Brewer\u2019s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News. 2002;33(2):51\u201359.","journal-title":"ACM SIGACT News"},{"key":"e_1_3_3_11_2","unstructured":"Lynch NA. Distributed algorithms . San Francisco (CA):Morgan Kaufmann; 1996."},{"issue":"2","key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1109\/MC.2012.33","article-title":"Consistency tradeoffs in modern distributed database system design: CAP is only part of the story","volume":"45","author":"Abadi D","year":"2012","unstructured":"Abadi D. Consistency tradeoffs in modern distributed database system design: CAP is only part of the story. Computer. 2012;45(2):37\u201342.","journal-title":"Computer"},{"issue":"24","key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/1124153.1124156","article-title":"The costs and limits of availability for replicated services","volume":"2","author":"Yu H","year":"2006","unstructured":"Yu H, Vahdat A. The costs and limits of availability for replicated services. ACM Trans Comput Syst. 2006;2(24):70\u2013113.","journal-title":"ACM Trans Comput Syst"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","unstructured":"Maler O Manna Z Pnueli A. From timed to hybrid systems. In: de Bakker JW Huizing C de Roever WP Rozenberg G editors. Real-time: Theory and practice REX Workshop . Berlin Heidelberg (Germany): Springer-Verlag; 1992. p. 447\u2013484.","DOI":"10.1007\/BFb0032003"},{"key":"e_1_3_3_15_2","unstructured":"Cataldo A Lee EA Liu X Matsikoudis E Zheng H. A constructive fixed-point theorem and the feedback semantics of timed systems. Paper presented at: Workshop on Discrete Event Systems (WODES); 2006 July 10\u201312; Ann Arbor Michigan."},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","first-page":"1655","DOI":"10.1007\/s10270-017-0633-6","article-title":"Hybrid co-simulation: It\u2019s about time","volume":"18","author":"Cremona F","year":"2017","unstructured":"Cremona F, Lohstroh M, Broman D, Lee EA, Masin M, Tripakis S. Hybrid co-simulation: It\u2019s about time. Softw Syst Model. 2017;18:1655\u20131679.","journal-title":"Softw Syst Model"},{"issue":"12","key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1109\/43.736561","article-title":"A framework for comparing models of computation","volume":"17","author":"Lee EA","year":"1998","unstructured":"Lee EA, Sangiovanni-Vincentelli A. A framework for comparing models of computation. IEEE Trans Comput Aided Des Circuits Syst. 1998;17(12):1217\u20131229.","journal-title":"IEEE Trans Comput Aided Des Circuits Syst"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF02277859","article-title":"Detecting causal relationships in distributed computations: In search of the holy grail","volume":"7","author":"Schwarz R","year":"1994","unstructured":"Schwarz R, Mattern F. Detecting causal relationships in distributed computations: In search of the holy grail. Distrib Comput. 1994;7:149\u2013174.","journal-title":"Distrib Comput"},{"key":"e_1_3_3_19_2","unstructured":"Kleppmann M. A critique of the CAP theorem. arXiv. 2015. https:\/\/arxiv.org\/abs\/1509.05393."},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","unstructured":"Lee EA. The coevolution: The entwined futures of humans and machines . Cambridge (MA): MIT Press; 2020.","DOI":"10.7551\/mitpress\/12307.001.0001"},{"issue":"7","key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/359545.359563","article-title":"Time, clocks, and the ordering of events in a distributed system","volume":"21","author":"Lamport L","year":"1978","unstructured":"Lamport L, Shostak R, Pease M. Time, clocks, and the ordering of events in a distributed system. Commun ACM. 1978;21(7):558\u2013565.","journal-title":"Commun ACM"},{"key":"e_1_3_3_22_2","unstructured":"Mattern F. Virtual time and global states of distributed systems. In: Cosnard M Quinton P Raynal M Robert Y editors. Parallel and distributed algorithms . Amsterdam (Netherlands): North-Holland; 1988. p. 215\u2013226."},{"key":"e_1_3_3_23_2","unstructured":"Baccelli F Cohen G Olster GJ Quadrat JP. Synchronization and linearity an algebra for discrete event systems . New York (NY): Wiley; 1992."},{"issue":"2","key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/956981.956983","article-title":"A brief history of NTP time: Memoirs of an internet timekeeper","volume":"33","author":"Mills DL","year":"2003","unstructured":"Mills DL. A brief history of NTP time: Memoirs of an internet timekeeper. ACM Comput Commun Rev. 2003;33(2):9\u201321.","journal-title":"ACM Comput Commun Rev"},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","unstructured":"Mills DL Mills DL. Computer network time synchronization \u2014 The network time protocol . Boca Raton (FL): CRC Press; 2006.","DOI":"10.1201\/9781420006155"},{"key":"e_1_3_3_26_2","unstructured":"Eidson JC. Measurement control and communication using IEEE 1588 . New York (NY): Springer; 2006."},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","unstructured":"Eidson JC Stanton KB. Timing in cyber-physical systems: The last inch problem. Paper presented at: IEEE International Symposium on Precision Clock Synchronization for Measurement Control and Communication (ISPCS) IEEE; 2015 Oct 11\u201316; Beijing China. p. 19\u201324.","DOI":"10.1109\/ISPCS.2015.7324674"},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","unstructured":"Lohstroh M Romeo \u00cd\u00cd Goens A Derler P Castrillon J Lee EA Sangiovanni-Vincentelli A 8th international workshop on model-based design of cyber physical systems (CyPhy\u201919) Springer-Verlag; 2019. Reactors: A deterministic model for composable reactive systems; in press:vol. LNCS 11971.","DOI":"10.1007\/978-3-030-41131-2_4"},{"key":"e_1_3_3_29_2","unstructured":"Lohstroh M. Reactors: A deterministic model of concurrent computation for reactive systems [dissertation]. [Berkeley (CA)]: University of California Berkeley; 2020."},{"key":"e_1_3_3_30_2","unstructured":"Schneider C Sp\u00f6nemann M von Hanxleden R. Just model! \u2013 Putting automatic synthesis of node-link-diagrams into practice. Paper presented at: Proceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing (VL\/HCC \u201913); 2013 Sep 15\u201319; San Jose CA. p. 75\u201382."},{"key":"e_1_3_3_31_2","unstructured":"Bateni S Lohstroh M Wong HS Tabish R Kim H Lin S Menard C Liu C Lee EA. Xronos: Predictable coordination for safety-critical distributed embedded systems. arXiv. 2022. https:\/\/arxiv.org\/abs\/2207.09555."},{"key":"e_1_3_3_32_2","unstructured":"Geng Y Liu S Yin Z Naik A Prabhakar B Rosenblum M Vahdat A. Exploiting a natural network effect for scalable fine-grained clock synchronization. Paper presented at: USENIX Symposium on Networked Systems Design and Implementation (NSDI) 2018 Apr 9\u201311; Renton WA."},{"key":"e_1_3_3_33_2","unstructured":"Alvaro P Conway N Hellerstein JM Marczak WR. Consistency analysis in Bloom: A CALM and collected approach. 5th Biennial Conference on Innovative Data Systems Research (CIDR ); Jan 2011."},{"issue":"5","key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1145\/2447976.2447992","article-title":"Eventual consistency today: Limitations, extensions, and beyond","volume":"56","author":"Bailis P","year":"2013","unstructured":"Bailis P, Ghodsi A. Eventual consistency today: Limitations, extensions, and beyond. Commun ACM. 2013;56(5):55\u201363.","journal-title":"Commun ACM"},{"key":"e_1_3_3_35_2","unstructured":"Helland P Campbell D. Building on quicksand. Conference on innovative data systems research (CIDR) . ACM; Jan. 2009. [Online]. Available: https:\/\/arxiv.org\/abs\/0909.1788."},{"key":"e_1_3_3_36_2","unstructured":"Kuhl F Weatherly R Dahmann J. Creating computer simulation systems: An introduction to the high level architecture . Upper Saddle River (NJ): Prentice Hall PTR; 1999."},{"key":"e_1_3_3_37_2","unstructured":"Fujimoto R. Parallel and distributed simulation systems . Hoboken (NJ): John Wiley and Sons; 2000."},{"key":"e_1_3_3_38_2","unstructured":"Zeigler BP Praehofer H Kim TG. Theory of modeling and simulation . 2nd. Academic Press; 2000 Discrete event systems (DEVS)."},{"key":"e_1_3_3_39_2","doi-asserted-by":"crossref","unstructured":"Liskov BH Ladin R. Highly available distributed services and fault-tolerant distributed garbage collection. Paper presented at: Symposium on Principles of distributed computing (PODC) ACM; 1986 Nov. p. 29\u201339.","DOI":"10.21236\/ADA229264"},{"issue":"5","key":"e_1_3_3_40_2","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1109\/TSE.1979.230182","article-title":"Distributed simulation: A case study in design and verification of distributed programs","volume":"5","author":"Chandy KM","year":"1979","unstructured":"Chandy KM, Misra J. Distributed simulation: A case study in design and verification of distributed programs. IEEE Trans on Softw Eng. 1979;5(5):440\u2013452.","journal-title":"IEEE Trans on Softw Eng"},{"issue":"2","key":"e_1_3_3_41_2","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1145\/2993.2994","article-title":"Using time instead of timeout for fault-tolerant distributed systems","volume":"6","author":"Lamport L","year":"1984","unstructured":"Lamport L. Using time instead of timeout for fault-tolerant distributed systems. ACM Trans Program Lang Syst. 1984;6(2):254\u2013280.","journal-title":"ACM Trans Program Lang Syst"},{"key":"e_1_3_3_42_2","doi-asserted-by":"crossref","unstructured":"Zhao Y Lee EA Liu J. A programming model for time-synchronized distributed real-time systems. Paper presented at: Real-Time and Embedded Technology and Applications Symposium (RTAS) IEEE; 2007 Apr 3\u20136; Bellevue WA.","DOI":"10.1109\/RTAS.2007.5"},{"issue":"3","key":"e_1_3_3_43_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2491245","article-title":"Spanner: Google\u2019s globally distributed database","volume":"31","author":"Corbett JC","year":"2012","unstructured":"Corbett JC, Dean J, Epstein M, Fikes A, Frost C, Furman JJ, Ghemawat S, Gubarev A, Heiser C, Hochschild P, et al. Spanner: Google\u2019s globally distributed database. ACM Trans Comput Syst. 2012;31(3):1\u201322.","journal-title":"ACM Trans Comput Syst"},{"key":"e_1_3_3_44_2","doi-asserted-by":"crossref","unstructured":"Pearl J. Causality . Cambridge University Press; 2009.","DOI":"10.1017\/CBO9780511803161"}],"container-title":["Intelligent Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/spj.science.org\/doi\/pdf\/10.34133\/icomputing.0013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T14:15:26Z","timestamp":1704809726000},"score":1,"resource":{"primary":{"URL":"https:\/\/spj.science.org\/doi\/10.34133\/icomputing.0013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":43,"alternative-id":["10.34133\/icomputing.0013"],"URL":"https:\/\/doi.org\/10.34133\/icomputing.0013","relation":{},"ISSN":["2771-5892"],"issn-type":[{"value":"2771-5892","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"2022-11-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"0013"}}