Provable Determinism for Software in Cyber-Physical Systems

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

Abstract

In Cyber-Physical Systems (CPS), concurrently executing software components interact with each other and the physical environment to deliver functionality that is often safety-critical and time-sensitive. Verifying the correctness of the joint behavior of concurrent software components, however, is challenging. It is helpful to eliminate nondeterminism in the software, at the level of the programming model, and provide first-class programming constructs for expressing timed behavior. The Lingua Franca (LF) coordination language achieves this through the use of the Reactor model as its underlying model of computation. In this paper, we present the first formal operational semantics for the Reactor model, and prove its key properties of progress and determinism. The Reactor model and its associated proofs are fully mechanized in the Lean theorem prover. As an operational model, our semantics are close to the intuition for implementation and a helpful reference. The computational objects of the Reactor model are formalized in a modular fashion, which provides insights into the different structural properties of the model, and their effect on execution behavior.

Details

Original languageEnglish
Title of host publicationVerified Software. Theories, Tools and Experiments - 15th International Conference, VSTTE 2023, Revised Selected Papers
EditorsAndrew Reynolds, Serdar Tasiran
PublisherSpringer Science and Business Media B.V.
Pages85-107
Number of pages23
ISBN (print)9783031660634
Publication statusPublished - 2024
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14095 LNCS
ISSN0302-9743

Conference

Title15th International Conference on Verified Software
SubtitleTheories, Tools, and Experiments
Abbreviated titleVSTTE 2023
Conference number15
Duration23 - 24 October 2023
CityAmes
CountryUnited States of America

External IDs

ORCID /0000-0002-5007-445X/work/173985265

Keywords