Distributed cyber-physical systems (CPS), where multiple computer programs distributed across a network interact with each other and with physical processes, are challenging to design and verify. Such systems are found in industrial automation, transportation systems, energy distribution systems, and many other applications. This project is developing a ?systems theory? for such applications that provides a good analytical toolkit for understanding how a system will behave when networks misbehave. It is building tools that make it possible to reason about the design of safe and reliable distributed CPS applications in an accessible user-friendly environment. In distributed applications, Brewer's CAP theorem tells us that when networks become partitioned, there is a tradeoff between consistency and availability in distributed software systems. Consistency is agreement on the values of shared variables; availability is the ability to respond to reads and writes of those shared variables. This project builds on an extension that has shown that consistency, availability, and network latency can be quantified, and that the CAP theorem can be generalized to give an algebraic relation between these quantities. This generalization is called the CAL theorem because it replaces ?network Partitioning? with ?Latency,? where partitioning is just a limiting case of latency. The CAL theorem can be used to help design distributed systems that fail gracefully when network performance degrades. With increasing latency, either consistency or availability (or some measure of both) must be sacrificed, and the CAL theorem quantifies these sacrifices.

This project is applying the CAL theorem to distributed CPS. The project is deriving the fundamental limits implied by the CAL theorem and developing a methodology for systematically trading off availability and consistency in application-specific ways. The application of the CAL theorem to CPS generalizes consistency to include agreement on the state of the physical world and availability to include the latency of software responses to stimulus from the physical world. Instead of focusing solely on network latency, the project adopts a measure called ?apparent latency? that includes network latency plus all other sources of latency (e.g., computation time). This measure is practically measurable. The project builds upon the recently developed Lingua Franca coordination language to provide system designers with concrete analysis and design tools to make the required tradeoffs in deployable software. The tools automatically produce graphical renditions of systems and user-friendly feedback on the concurrent, distributed, and real-time aspects.

Abstract

Performance Period: 01/15/2023 - 12/31/2025

Institution: University of California-Berkeley

Award Number: 2233769