{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T20:55:23Z","timestamp":1768078523815,"version":"3.49.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:00:00Z","timestamp":1694217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["#CNS-1836601, #CNS-2233769"],"award-info":[{"award-number":["#CNS-1836601, #CNS-2233769"]}]},{"name":"German Federal Ministry of Education and Research"},{"name":"Software Campus program","award":["01IS12051"],"award-info":[{"award-number":["01IS12051"]}]},{"name":"Souver\u00e4n. Digital. Vernetzt","award":["16KISK001K"],"award-info":[{"award-number":["16KISK001K"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            In distributed applications, Brewer\u2019s 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\n            <jats:sc>Lingua Franca<\/jats:sc>\n            coordination language to provide system designers with concrete analysis and design tools to make the required tradeoffs in deployable embedded software.\n          <\/jats:p>","DOI":"10.1145\/3609119","type":"journal-article","created":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T13:33:18Z","timestamp":1694266398000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Consistency vs. Availability in Distributed Cyber-Physical Systems"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5663-0584","authenticated-orcid":false,"given":"Edward A.","family":"Lee","sequence":"first","affiliation":[{"name":"University of California, Berkeley, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-4211-3593","authenticated-orcid":false,"given":"Ravi","family":"Akella","sequence":"additional","affiliation":[{"name":"DENSO International America, Inc., USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5448-3664","authenticated-orcid":false,"given":"Soroush","family":"Bateni","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6885-5572","authenticated-orcid":false,"given":"Shaokai","family":"Lin","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8833-4117","authenticated-orcid":false,"given":"Marten","family":"Lohstroh","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7134-8384","authenticated-orcid":false,"given":"Christian","family":"Menard","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dresden, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,9,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.33"},{"key":"e_1_3_2_3_2","volume-title":"Formal Methods for Open Object-based Distributed Systems, IFIP Transactions","author":"Agha Gul A.","year":"1997","unstructured":"Gul A. Agha. 1997. Abstracting interaction patterns: A programming paradigm for open distributed systems. In Formal Methods for Open Object-based Distributed Systems, IFIP Transactions, E. Najm Stefani and J.-B. (Eds.). Chapman and Hall."},{"key":"e_1_3_2_4_2","volume-title":"Synchronization and Linearity, An Algebra for Discrete Event Systems","author":"Baccelli F.","year":"1992","unstructured":"F. Baccelli, G. Cohen, G. J. Olster, and J. P. Quadrat. 1992. Synchronization and Linearity, An Algebra for Discrete Event Systems. Wiley, New York."},{"key":"e_1_3_2_5_2","article-title":"Xronos: Predictable coordination for safety-critical distributed embedded systems","author":"Bateni Soroush","year":"2022","unstructured":"Soroush Bateni, Marten Lohstroh, Hou Seng Wong, Rohan Tabish, Hokeun Kim, Shaokai Lin, Christian Menard, Cong Liu, and Edward A. Lee. 2022. Xronos: Predictable coordination for safety-critical distributed embedded systems. arXiv:2207.09555 [cs.DC] (July 2022). https:\/\/arxiv.org\/abs\/2207.09555","journal-title":"arXiv:2207.09555 [cs.DC]"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.97297"},{"key":"e_1_3_2_7_2","volume-title":"Symposium on Principles of Distributed Computing (PODC)","author":"Brewer Eric","year":"2000","unstructured":"Eric Brewer. 2000. Towards robust distributed system. In Symposium on Principles of Distributed Computing (PODC). Keynote talk."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2012.37"},{"key":"e_1_3_2_9_2","volume-title":"Workshop on Discrete Event Systems (WODES)","author":"Cataldo Adam","year":"2006","unstructured":"Adam Cataldo, Edward A. Lee, Xiaojun Liu, Eleftherios Matsikoudis, and Haiyang Zheng. 2006. A constructive fixed-point theorem and the feedback semantics of timed systems. In Workshop on Discrete Event Systems (WODES)."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1979.230182"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10270-017-0633-6"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/268437.268465"},{"key":"e_1_3_2_14_2","volume-title":"Forum on Specification and Design Languages (FDL)","author":"Edwards Stephen A.","year":"2020","unstructured":"Stephen A. Edwards and John Hui. 2020. The sparse synchronous model. In Forum on Specification and Design Languages (FDL)."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/564585.564601"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3475965.3480470"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2002.805825"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24349-3 5"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24349-3_5"},{"key":"e_1_3_2_20_2","unstructured":"Martin Kleppmann. 2015. A Critique of the CAP Theorem. (2015). https:\/\/arxiv.org\/abs\/1509.05393arXiv:1509.05393 [cs.DC]."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2993.2994"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/12307.001.0001"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453652"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.34133\/ icomputing.0013"},{"key":"e_1_3_2_26_2","volume-title":"System Design, Modeling, and Simulation using Ptolemy II","author":"Lee Edward A.","year":"2014","unstructured":"Edward A. Lee, Jie Liu, Lukito Muliadi, and Haiyang Zheng. 2014. Discrete-event models. In System Design, Modeling, and Simulation using Ptolemy II, Claudius Ptolemaeus (Ed.). Ptolemy.org."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.736561"},{"key":"e_1_3_2_28_2","volume-title":"Design Automation Conference","author":"Liao Stan","year":"1997","unstructured":"Stan Liao, Steve Tjiang, and Rajesh Gupta. 1997. An efficient implementation of reactivity for modeling hardware in the scenic design environment. In Design Automation Conference. ACM, Inc."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2019.2905334"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/AAI28263682"},{"key":"e_1_3_2_31_2","volume-title":"8th International Workshop on Model-Based Design of Cyber Physical Systems (CyPhy\u201919)","author":"Lohstroh Marten","year":"2019","unstructured":"Marten Lohstroh, \u00cd\u00f1igo \u00cdncer Romeo, Andr\u00e9s Goens, Patricia Derler, Jeronimo Castrillon, Edward A. Lee, and Alberto Sangiovanni-Vincentelli. 2019. Reactors: A deterministic model for composable reactive systems. In 8th International Workshop on Model-Based Design of Cyber Physical Systems (CyPhy\u201919), Vol. LNCS 11971. Springer-Verlag. in press."},{"key":"e_1_3_2_32_2","volume-title":"Workshop on Time-Centric Reactive Software (TCRS)","author":"Lohstroh Marten","year":"2023","unstructured":"Marten Lohstroh, Edward A. Lee, Stephen A. Edwards, and David Broman. 2023. Logical time for reactive software. In Workshop on Time-Centric Reactive Software (TCRS). ACM."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448128"},{"key":"e_1_3_2_34_2","volume-title":"Distributed Algorithms","author":"Lynch N. A.","year":"1996","unstructured":"N. A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/BFb0032003","volume-title":"Real-Time: Theory and Practice, REX Workshop","author":"Maler Oded","year":"1992","unstructured":"Oded Maler, Zohar Manna, and Amir Pnueli. 1992. From timed to hybrid systems. In Real-Time: Theory and Practice, REX Workshop. Springer-Verlag, 447\u2013484."},{"key":"e_1_3_2_36_2","first-page":"215","volume-title":"Parallel and Distributed Algorithms","author":"Mattern Friedemann","year":"1988","unstructured":"Friedemann Mattern. 1988. Virtual time and global states of distributed systems. In Parallel and Distributed Algorithms, Michel Cosnard, Patrice Quinton, Michel Raynal, and Yves Robert (Eds.). North-Holland, 215\u2013226."},{"key":"e_1_3_2_37_2","article-title":"High-performance deterministic concurrency using lingua franca","author":"Menard Christian","year":"2023","unstructured":"Christian Menard, Marten Lohstroh, Soroush Bateni, Matthew Chorlian, Arthur Deng, Peter Donovan, Cl\u00e9ment Fournier, Shaokai Lin, Felix Suchert, Tassilo Tanneberger, Hokeun Kim, Jeronimo Castrillon, and Edward A. Lee. 2023. High-performance deterministic concurrency using lingua franca. arXiv:2301.02444 [cs.PL] (01\/09\/2023 2023). https:\/\/arxiv.org\/abs\/2301.02444","journal-title":"arXiv:2301.02444 [cs.PL]"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/6462.6485"},{"key":"e_1_3_2_39_2","volume-title":"Now \u2014 The Physics of Time","author":"Muller Richard A.","year":"2016","unstructured":"Richard A. Muller. 2016. Now \u2014 The Physics of Time. W. W. Norton and Company."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2018.00031"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2997654"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/0968-090X(94)90019-1"},{"key":"e_1_3_2_43_2","volume-title":"The Order of Time","author":"Rovelli Carlo","year":"2018","unstructured":"Carlo Rovelli. 2018. The Order of Time. Riverhead Books, New York."},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/VLHCC.2013.6645246","volume-title":"Proceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing (VL\/HCC\u201913)","author":"Schneider Christian","year":"2013","unstructured":"Christian Schneider, Miro Sp\u00f6nemann, and Reinhard von Hanxleden. 2013. Just model! \u2013 putting automatic synthesis of node-link-diagrams into practice. In Proceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing (VL\/HCC\u201913). San Jose, CA, USA, 75\u201382."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02277859"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2022.3144112"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1124153.1124156"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/99.615432"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230554"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3230543.3230554"},{"key":"e_1_3_2_52_2","first-page":"259","volume-title":"Real-Time and Embedded Technology and Applications Symposium (RTAS)","author":"Zhao Yang","year":"2007","unstructured":"Yang Zhao, Edward A. Lee, and Jie Liu. 2007. A programming model for time-synchronized distributed real-time systems. In Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 259\u2013268."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3609119","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3609119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:58Z","timestamp":1750182538000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3609119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,9]]},"references-count":51,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3609119"],"URL":"https:\/\/doi.org\/10.1145\/3609119","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,9]]},"assertion":[{"value":"2023-03-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-13","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}