The objective of this research is to define programming abstractions with temporal semantics for distributed cyber-physical systems. The approach is to create a coordination language for distributed embedded software that blends naturally with models of physical dynamics. The coordination language is based on a rigorous discrete-event concurrent model of computation. It will be used by system designers to construct models from which software implementations are derived. The objective is distributed software that, if it compiles for a platform, delivers precisely the temporal semantics specified in the model. Intellectual merit: This project addresses the core abstractions of computing, which throughout the 20th century, have abstracted away time, and of physical dynamics, which have omitted software and network behaviors. For cyber-physical systems, both are inappropriate. This project is developing new time-centric abstractions for software, programming models, analysis techniques, and integration of software and network models with physical dynamics. Broader impacts: Besides the considerable economic and societal impact of CPS in general, the project is expected to have considerable impact on engineering and computer science education. Its focus on engineering applications and on sound computer science methods will erode the boundaries between these disciplines that hamper competitiveness of our students. A new generation of students is needed to dramatically improve our energy efficiency, manufacturing capabilities, transportation efficiency, instrumentation prowess (and hence, scientific knowledge), and infrastructure robustness. Because of the broad societal implications of the work, it will help attract to engineering and computer science a more diverse talent pool.
This project focused on model-based design principles for event-triggered real-time distributed systems. Specifically, the project developed modeling and design techniques and an underlying theory for cyber-physical systems (which combine computational elements with physical systems). Such systems form an increasingly important part of the critical infrastructure in our society, as computer controllers pervade our transportation systems, energy production and distribution, safety and emergency response, security systems, and the environment. The systems of interest in this project have one or more of the following characteristics: <ul> <li> Highly asynchronous stimulus-response such that the periodic sampling often used in safety-critical systems is not a feasible solution; <li> Mixed systems where periodic sampling and asynchronous stimulus response are both present; <li> Systems where knowing the precise time (at a fine grain than possible using periodic sampling) is required; and <li> Systems where the order of distributed events must be determined to high accuracy and this order preserved in any response. </ul> The project has developed a theory of timed systems, a programming model called PTIDES (for Programming Temporally Integrated Distributed Embedded Systems), and an associated novel software toolchain for problems that include schedulability and timing analyses. A particular breakthrough result of the project concerns the theory of timed systems. In particular, project participants developed a mathematical model using a prefix order, developed its subtle relationship with a metric notion of distance, and obtained a new foundation for a truly cyber-physical systems theory. The project has provided a proof of a remarkably general constructive fixed-point theorem for strictly contracting functions on spaces of signals such as the space of all discrete-event signals. Until then, the only tool available for dealing with such problems in a systematic way was a non-constructive fixed-point theorem of Priess-Crampe and Ribenboim for strictly contracting functions on spherically complete generalized ultrametric spaces. The project also yielded a recursive procedure for constructing the unique fixed point of a strictly contracting function on a directed-complete subsemilattice of signals as the limit of an increasing chain of signal prefixes. This work provides a mathematical model of feedback in systems with unrestricted strictly causal operators, even in the presence of Zeno conditions, and a constructive procedure for translated this sound theory into software implementations. On the more applied side, a timed discrete-event (DE) is an actor-oriented formalism for modeling timed systems. A DE model is a network of actors consuming/producing timed events from/to a set of input/output channels. This project has codified a specific DE model, called deterministic DE (DDE), where actors are simple constant-delay components. It has also given two extensions of DDE: NDE, where actors are non-deterministic delays, and DETA, where actors are either deterministic delays or timed automata. These models are well suited to rigorous formulation and solution of specific verification questions on DE models. The DE models resulting from this project are realized in the open-source Ptolemy II software framework. This framework provides modeling and simulation with a very flexible multiform notion of time that supports experimentation. A PTIDES simulator and code generator have been built in Ptolemy II, and the simulator is available in open-source form (see http://ptolemy.org). In addition, the project achieved significant new results for the problem of timing analysis of real-time embedded software, implemented in the GameTime toolkit. These include the extension of the original GameTime algorithm to handle certain concurrent programs, the extension to data-dependent timing, and the use of the GameTime algorithm to evaluate the timing repeatability of platforms. The project has also made path-breaking contributions to CPS education and broader outreach, including the development of a novel undergraduate curriculum in embedded and cyber-physical systems at UC Berkeley, disseminated world-wide through a textbook co-authored by the PIs, a massive open online course (MOOC) designed and offered by the PIs, and a workshop on cyber-physical systems education.
