Shaokai Lin

Shaokai Lin


Research Focus & Metrics

Academic Career Length

5Years (2022-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 October 2023 in ACM Transactions on Architecture and Code Optimization
Verified
Journal Article
Open access
CMChristian Menard
Christian Menard
MLMarten Lohstroh
Marten Lohstroh
SBSoroush Bateni
Soroush Bateni
MCMatthew Chorlian
Matthew Chorlian
ADArthur Deng
Arthur Deng
ELEdward Lee
Edward Lee
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 deterministic concurrency. In this paper, we present an efficient, parallel implementation of reactors and demonstrate that the determinacy of reactors does not imply a loss in performance. To show this, we evaluate Lingua Franca (LF), a reactor-oriented coordination language. LF equips mainstream programming languages with a deterministic concurrency model that automatically takes advantage of opportunities to exploit parallelism. 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.

9 September 2023 in ACM Transactions on Embedded Computing Systems
Verified
Journal Article
Open access
ELEdward Lee
Edward Lee
RARavi Akella
Ravi Akella
SBSoroush Bateni
Soroush Bateni
SLShaokai Lin
Shaokai Lin
MLMarten Lohstroh
Marten Lohstroh
CMChristian Menard
Christian Menard
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.

9 September 2023 in ACM Transactions on Embedded Computing Systems
Verified
Journal Article
Open access
SLShaokai Lin
Shaokai Lin
YMYatin A. Manerkar
Yatin A. Manerkar
MLMarten Lohstroh
Marten Lohstroh
EPElizabeth Polgreen
Elizabeth Polgreen
SYSheng-Jung Yu
Sheng-Jung Yu
SSSanjit A. Seshia
Sanjit A. Seshia
Formal verification of cyber-physical systems (CPS) is challenging because it has to consider real-time and concurrency aspects that are often absent in ordinary software. Moreover, the software in CPS is often complex and low-level, making it hard to assure that a formal model of the system used for verification is a faithful representation of the actual implementation, which can undermine the value of a verification result. To address this problem, we propose a methodology for building verifiable CPS based on the principle that a formal model of the software can be derived automatically from its implementation. Our approach requires that the system implementation is specified in Lingua Franca (LF), a polyglot coordination language tailored for real-time, concurrent CPS, which we made amenable to the specification of safety properties via annotations in the code. The program structure and the deterministic semantics of LF enable automatic construction of formal axiomatic models directly from LF programs. The generated models are automatically checked using Bounded Model Checking (BMC) by the verification engine Uclid5 using the Z3 SMT solver. The proposed technique enables checking a well-defined fragment of Safety Metric Temporal Logic (Safety MTL) formulas. To ensure the completeness of BMC, we present a method to derive an upper bound on the completeness threshold of an axiomatic model based on the semantics of LF. We implement our approach in the LF V erifier and evaluate it using a benchmark suite with 22 programs sampled from real-life applications and benchmarks for Erlang, Lustre, actor-oriented languages, and RTOSes. The LF V erifier correctly checks 21 out of 22 programs automatically.

9 May 2023
Verified
Conference Paper
Open access
EJErling R. Jellum
Erling R. Jellum
SLShaokai Lin
Shaokai Lin
PDPeter Donovan
Peter Donovan
CJChadlia Jerad
Chadlia Jerad
EWEdward Wang
Edward Wang
MSMartin Schoeberl
Martin Schoeberl
With the end of Moore’s law and the breakdown of Dennard scaling, multicore processors are the standard way to continue improving performance while reducing Size, Weight and Power (SWaP). However, this performance is typically achieved at the cost of repeatability and predictability. Precision-timed (PRET) architectures have been shown to deliver high performance without sacrificing predictability. In this paper, we introduce InterPRET: an architecture consisting of FlexPRET cores interconnected via the S4NOC network-on-chip. Both the processor cores and the network-on-chip are time-predictable, yielding an end-to-end time-predictable architecture suitable for real-time systems.

21 September 2023
Verified
Conference Paper
Open access
SBSoroush Bateni
Soroush Bateni
MLMarten Lohstroh
Marten Lohstroh
HWHou Seng Wong
Hou Seng Wong
HKHokeun Kim
Hokeun Kim
SLShaokai Lin
Shaokai Lin
ELEdward Lee
Edward Lee
Asynchronous frameworks for distributed embedded systems, like ROS and MQTT, are increasingly used in safety-critical applications such as autonomous driving, where the cost of unintended behavior is high. The loose coordination between the components in these frameworks gives rise to nondeterminism, where factors such as communication timing can lead to arbitrary ordering in the handling of messages. In this paper, we show that this problem compromises safety and complicates system design in Autoware.Auto 1.0, a popular open-source autonomous driving framework based on ROS 2. We extend the Lingua Franca coordination language to support distributed execution, port Autoware.Auto to Lingua Franca, and show that our solution avoids the identified problems. We assess the performance of our federated runtime implementation and show that it is competitive for this application. We also compare our achievable throughput to ROS 2 and MQTT using microbench-marks and find that we can match or exceed the throughput of those frameworks while preserving determinism.

7 August 2022
Verified
Book Chapter
Open access
PDF file
EPElizabeth Polgreen
Elizabeth Polgreen
KCKevin Cheang
Kevin Cheang
PGPranav Gaddamadugu
Pranav Gaddamadugu
AGAdwait Godbole
Adwait Godbole
KLKevin Laeufer
Kevin Laeufer
SSSanjit A. Seshia
Sanjit A. Seshia
UCLID5 is a tool for the multi-modal formal modeling, verification, and synthesis of systems. It enables one to tackle verification problems for heterogeneous systems such as combinations of hardware and software, or those that have multiple, varied specifications, or systems that require hybrid modes of modeling. A novel aspect of UCLID5 is an emphasis on the use of syntax-guided and inductive synthesis to automate steps in modeling and verification. This tool paper presents new developments in the UCLID5 tool including new language features, integration with new techniques for syntax-guided synthesis and satisfiability solving, support for hyperproperties and combinations of axiomatic and operational modeling, demonstrations on new problem classes, and a robust implementation.