Achieving determinism in distributed real-time systems is challenging, due to uncertainties in execution time, communication jitter, and resource scheduling. This dissertation presents a concurrent model of computation (MoC) for distributed real-time systems called PTIDES (pronounced "tides," for "Programming Temporally Integrated Distributed Embedded Systems"). PTIDES uses a discrete-event (DE) model as the underlying formal semantics to achieve analyzable deterministic behavior. PTIDES programs are discrete-event models constructed as networks of concurrent components, called actors, communicating via time-stamped events. These time stamps serve as the basis to define the unique order among events. Rather than using DE models for performance modeling and simulation, where time stamps are a modeling property bearing no relationship to real time during execution of the model, PTIDES uses DE model as a specification language for real-time applications. It extends DE models with the capability of relating events that interact with the physical world with physical time.

Preserving DE semantics at runtime can be challenging, since the global, consistent notion of time may lead to a total ordering of execution in a distributed system, an unnecessary waste of resources. A dependency analysis framework is presented to allow out of order processing of events without compromising determinism and without requiring backtracking. The key idea is that if two events have independent affects, formally defined through causality analysis, then they can be processed in any order. As a result, if the earlier event is delayed due to communication, processing of the later event does not need to be blocked.

General event triggered real-time systems with multiple shared resources are not amenable to compile-time feasibility analysis. However, when the discrete activities can come in predictable patterns, real-time scheduling theories are applicable to many PTIDES models. This dissertation studies a sufficient condition for a PTIDES model to be feasible when the inputs to a PTIDES model are sporadic, i.e. when there is a minimum interval between any two consecutive events of the same input.




Download Full History