Featured Publications
High-performance Deterministic Concurrency Using Lingua Franca
Actor frameworks and similar reactive programming techniques are widely used for building concurrent systems. They promise to be efficient and scale well to a large number of cores or nodes in a distributed system. However, they also expose programmers to nondeterminism, which often makes implementations hard to understand, debug, and test. The recently proposed reactor model is a promising alternative that enables efficient deterministic concurrency. In this paper, we show that determinacy does neither imply a loss in expressivity nor in performance. To show this, we evaluate Lingua Franca (LF), a reactor-oriented coordination language that equips mainstream programming languages with a concurrency model that automatically takes advantage of opportunities to exploit parallelism that do not introduce nondeterminism. Our implementation of the Savina benchmark suite demonstrates that, in terms of execution time, the runtime performance of LF programs even exceeds popular and highly optimized actor frameworks. We compare against Akka and CAF, which LF outperforms by 1.86x and 1.42x, respectively.
Consistency vs. Availability in Distributed Cyber-Physical Systems
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.
Toward a Lingua Franca for Deterministic Concurrent Systems
Many programming languages and programming frameworks focus on parallel and distributed computing. Several frameworks are based on actors, which provide a more disciplined model for concurrency than threads. The interactions between actors, however, if not constrained, admit nondeterminism. As a consequence, actor programs may exhibit unintended behaviors and are less amenable to rigorous testing. We show that nondeterminism can be handled in a number of ways, surveying dataflow dialects, process networks, synchronous-reactive models, and discrete-event models. These existing approaches, however, tend to require centralized control, pose challenges to modular system design, or introduce a single point of failure. We describe “reactors,” a new coordination model that combines ideas from several of these approaches to enable determinism while preserving much of the style of actors. Reactors promote modularity and allow for distributed execution. By using a logical model of time that can be associated with physical time, reactors also provide control over timing. Reactors also expose parallelism that can be exploited on multicore machines and in distributed configurations without compromising determinacy.
All Publications
ESL '24: Francesco Paladino, Erling Jellum, Efsane Soyer, and Edward A. Lee. "Layered Scheduling: Toward Better Real-Time Lingua Franca", IEEE Embedd. Syst. Letters 18(9), September 2024.
ESL '24: Benjamin Asch, Erling Jellum, Marten Lohstroh, and Edward A. Lee. "Software-Defined Watchdog Timers for Cyber-Physical Systems", IEEE Embedd. Syst. Letters 18(9), September 2024.
ESL '24: Chadlia Jerad and Edward A. Lee. "Toward Dynamism in Distributed Lingua Franca Programs", IEEE Embedd. Syst. Letters 18(9), September 2024.
TECS '24: Marten Lohstroh, Soroush Bateni, Christian Menard, Alexander Schulz-Rosengarten, Jeronimo Castrillon, and Edward A. Lee. "Deterministic Coordination across Multiple Timelines", ACM Trans. Embedd. Comput. Syst. 23, 5, Article 77, August 2024.
SPAA '24: Jacky Kwok, Marten Lohstroh, Edward A. Lee. "Efficient Parallel Reinforcement Learning Framework Using the Reactor Model", Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), June 2024.
Doctoral Thesis: Christian Menard, "Deterministic Reactive Programming for Cyber-physical Systems" , TU Dresden, 03 June 2024.
DDE '24: Peter Donovan, Erling Jellum, Byeonggil Jun, Hokeun Kim, Edward A. Lee, Shaokai Lin, Marten Lohstroh, Anirudh Rengarajan. "Strongly-Consistent Distributed Discrete-event Systems." arXiv:2405.12117v1 [cs.DC] 20 May 2024.
Master's Thesis: Samuel Berkun. "Concurrency Without Threads for Multicore Microprocessors." , University of California, Berkeley, 2024.
Master's Thesis: Jacky Kwok. "Towards Efficient and Deterministic Dataflow Systems for Machine Learning." , University of California, Berkeley, 2024.
Master's Thesis: Efsane Soyer. "Dealing with Time: Measuring Real-Time Capabilities of Lingua Franca." , University of California, Berkeley, 2024.
ICSE '24: Alexander Schulz-Rosengarten, Benjamin Asch, Gustavo Quiros, Akash Ahmad, Marten Lohstroh, Ankit Shukla, Malte Clement, Edward A. Lee, and Reinhard von Hanxleden, "Behavior Trees with Dataflow: Coordinating Reactive Tasks in Lingua Franca", in Companion Proceedings of the International Conference on Software Engineering (ICSE-Companion), Lisbon, Portugal, April 2024.
VSSTE '23: Marcus Rossel, Shaokai Lin, Marten Lohstroh, Jeronimo Castrillon, Andrés Goens, "Provable Determinism for Software in Cyber-Physical Systems," inProceedings of the 15th International Conference on Verified Software: Theories, Tools, and Experiments, October 2023.
MEMOCODE '23: Soroush Bateni, Marten Lohstroh, Hou Seng Wong, Hokeun Kim, Shaokai Lin, Christian Menard, Edward A. Lee, "Risk and Mitigation of Nondeterminism in Distributed Cyber-Physical Systems," in Proceedings of the 21st ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE '23). Association for Computing Machinery, New York, NY, USA, 1–11.
TECS '23: Shaokai Lin, Yatin A. Manerkar, Marten Lohstroh, Elizabeth Polgreen, Sheng-Jung Yu, Chadlia Jerad, Edward A. Lee, Sanjit A. Seshia, "Towards Building Verifiable CPS using Lingua Franca," in ACM Transactions on Embedded Computing Systems (TECS), Vol. 22, No. 5s, Sept. 9, 2023. (Presented at EMSOFT '23, Hamburg, Germany, September, 2023)
EMSOFT '23: Edward A. Lee, Ravi Akella, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard, "Consistency vs. Availability in Distributed Cyber-Physical Systems," inACM Transactions on Embedded Computing Systems (TECS), Vol. 22, No. 5s, Sept. 9, 2023. (Presented at EMSOFT '23, Hamburg, Germany, September, 2023)
TACO '23: Christian Menard, Marten Lohstroh, Soroush Bateni, Matthew Chorlian, Arthur Deng, Peter Donovan, Clément Fournier, Shaokai Lin, Felix Suchert, Tassilo Tanneberger, Hokeun Kim, Jeronimo Castrillon, Edward A. Lee, "High-Performance Deterministic Concurrency using Lingua Franca," inACM Transactions on Architecture and Code Optimization (TACO), Accepted Aug. 29, 2023
CPS-IoT Week '23: Alexander Schulz-Rosengarten, Reinhard von Hanxleden, Marten Lohstroh, Soroush Bateni, Edward A. Lee, "Polyglot Modal Models through Lingua Franca," inProceedings of Cyber-Physical Systems and Internet of Things Week 2023 (CPS-IoT Week '23). Association for Computing Machinery, New York, NY, USA, 337–342.
PSD '23: Edward A. Lee and Marten Lohstroh, "Generalizing Logical Execution Time," inPrinciples of Systems Design - Essays Dedicated to Thomas A. Henzinger on the Occasion of his 60th Birthday, Lecture Notes in Computer Science, vol 13660. Springer, Cham.
Master's Thesis: Johannes HayeĂź, "Verifying the Rust Runtime of Lingua Franca." , TU Dresden, 06 March 2023.
IC '23: Edward A. Lee, Soroush Bateni, Shaokai Lin, Marten Lohstroh, and Christian Menard, "Trading Off Consistency and Availability in Tiered Heterogeneous Distributed Systems," inIntelligent Computing, vol. 2, no. Article 0013, pp. 1-23, February 15 2023.
NG-RES '23: Erling Rennemo Jellum, Shaokai Lin, Peter Donovan, Efsane Soyer, Fuzail Shakir, Torleiv Bryne, Milica Orlandic, Marten Lohstroh, Edward A. Lee, "Beyond the Threaded Programming Model on Real-Time Operating Systems," inWorkshop on Next Generation Real-Time Embedded Systems (NG-RES), January 18 2023.
Master's Thesis: Clément Fournier, "A Rust Backend for Lingua Franca." , TU Dresden, 06 December 2021.
ISoLA '21: Edward A. Lee and Marten Lohstroh, "Time for All Programs, Not Just Real-Time Programs," in Proc. Int. Symp. on Leveraging Applications of Formal Methods (ISoLA), Rhodes, Greece, October 17-29, 2021.
CAL '21: Edward A. Lee, Soroush Bateni, Shaokai Lin, Marten Lohstroh, Christian Menard, "Quantifying and Generalizing the CAP Theorem," arXiv:2109.07771 [cs.DC], Sep. 16, 2021.
TECS '21: Marten Lohstroh, Christian Menard, Soroush Bateni, and Edward A. Lee, "Toward a Lingua Franca for Deterministic Concurrent Systems," in ACM Transactions on Embedded Computing Systems (TECS), 20(4), May 2021.
Doctoral Thesis: Marten Lohstroh, "Reactors: A Deterministic Model of Concurrent Computation for Reactive Systems", UC Berkeley, EECS Department.
FDL '20: Marten Lohstroh, Christian Menard, Alexander Schulz-Rosengarten, Matthew Weber, Jeronimo Castrillon, Edward A. Lee, "A Language for Deterministic Coordination Across Multiple Timelines," in Forum on Design Languages (FDL), Kiel, Germany, September, 2020.
Bachelor's Thesis: Marcus Rossel, "Provable Determinism in Reactors." , TU Dresden, 01 April 2021.
DATE '20: Christian Menard, Andrés Goens, Marten Lohstroh, Jeronimo Castrillon, "Achieving Determinism in Adaptive AUTOSAR," in Proceedings of the 2020 Design, Automation and Test in Europe Conference (DATE), EDA Consortium, Mar 2020.
RTSS '19: Marten Lohstroh and Edward A. Lee, "Work-in-Progress: Real-Time Reactors in C," Proceedings of the Real-Time Systems Symposium (RTSS), Hong Kong, Dec. 2019. doi:10.1109/RTSS46320.2019.00067.
CyPhy '19: Marten Lohstroh, Iñigo Incer Romeo, Andrés Goens, Patricia Derler, Jeronimo Castrillon, Edward A. Lee, and Alberto Sangiovanni-Vincentelli, "Reactors: A Deterministic Model for Composable Reactive Systems," in Model-Based Design of Cyber Physical Systems (CyPhy'19), Held in conjunction with ESWEEK 2019, New York, NY, Oct. 17-18, 2019.
EMSOFT '19: Marten Lohstroh, Martin Schoeberl, Mathieu Jan, Edward Wang, Edward A. Lee "Work-in-Progress: Programs with Ironclad Timing Guarantees," in ACM SIGBED International Conference on Embedded Software (EMSOFT), New York, NY, October 13-18, 2019.
FDL '19: Marten Lohstroh and Edward A. Lee, "Deterministic Actors," in Forum on Design Languages (FDL), Southampton, UK, September, 2019.
DAC '19 Marten Lohstroh, Martin Schoeberl, Andres Goens, Armin Wasicek, Christopher Gill, Marjan Sirjani, Edward A. Lee, "Invited: Actors Revisited for Time-Critical Systems," in Design Automation Conference (DAC), June, 2019.
Presentations
Time for All Programs, Not Just Real-Time Programs, invited talk by Edward A. Lee, Oct. 25 2021, ISoLA, Rhodes, Greece
Video recordings of a four-hour Lingua Franca Tutorial offered at EMSOFT, Oct. 8, 2021.
Video recording of talk by Marten Lohstroh on "Deterministic Reactive Software for Embedded, Edge, and Cloud Systems," at KTH, Center for Trustworthy Edge Computing Systems and Applications (TECoSA), June 3, 2021.
Video recording of talk by Efsane Soyer on "[Hardware-Supported Timing-Critical Software in Lingua Franca," at NSF CPS PI Meeting, June 2, 2021. (Received best graduate student presentation award!)
Video recording of talk by Marten Lohstroh on Making Mainstream Programming Languages Deterministic Again, at 27th International Open Workshop on Synchronous Programming (Synchron), November 25-27, 2020
Marten Lohstroh, Christian Menard, Alexander Schulz-Rosengarten, Matthew Weber, Jeronimo Castrillon, Edward A. Lee, "A Language for Deterministic Coordination Across Multiple Timelines," (Slides only) Forum on Design Languages (FDL), Kiel, Germany, September, 2020.
Video recording of a presentation by Christian Menard, Achieving Determinism in Adaptive AUTOSAR, at virtual 23rd DATE conference 2020.
Video recording of a guest lecture by Edward A. Lee, Reactors and Lingua Franca: A Programming Model for Cyberphysical Systems, April 16, 2020.
Video recording of a presentation by Edward A. Lee of two Lingua Franca examples, Reflex Game and Distributed, at "virtual" group lunch on 04-15-20.
Marten Lohstroh, Iñigo Incer Romeo, Andrés Goens, Patricia Derler, Jeronimo Castrillon, Edward A. Lee, and Alberto Sangiovanni-Vincentelli, "Reactors: A Deterministic Model for Composable Reactive Systems," (Slides only) Model-Based Design of Cyber Physical Systems (CyPhy'19), Held in conjunction with ESWEEK 2019, New York, NY, Oct. 18.
Marten Lohstroh, Martin Schoeberl, Mathieu Jan, Edward Wang, Edward A. Lee "Work-in-Progress: Programs with Ironclad Timing Guarantees," (Slides only) ACM SIGBED International Conference on Embedded Software (EMSOFT), New York, NY, October 14.
Marten Lohstroh and Edward A. Lee "Deterministic Actors," (Slides only) Forum on Design Languages (FDL), Southampton, UK, September 3, 2019.
Edward A. Lee, "Actors Revisited for Predictable Systems," (Slides only) Model-Based Design of Cyber-Physical Systems (CyPhy), New York, Oct. 17, 2019.
Press Coverage
- "Toward A Lingua Franca For Intelligent System Design," by Frank Schirrmeister, Semiconductor Engineering, September 26, 2019.