Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

On the Design of Concurrent, Distributed Real-Time Systems

Yang Zhao

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-117
August 13, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-117.pdf

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.

Advisor: Edward A. Lee


BibTeX citation:

@phdthesis{Zhao:EECS-2009-117,
    Author = {Zhao, Yang},
    Title = {On the Design of Concurrent, Distributed Real-Time Systems},
    School = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Aug},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-117.html},
    Number = {UCB/EECS-2009-117},
    Abstract = {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.}
}

EndNote citation:

%0 Thesis
%A Zhao, Yang
%T On the Design of Concurrent, Distributed Real-Time Systems
%I EECS Department, University of California, Berkeley
%D 2009
%8 August 13
%@ UCB/EECS-2009-117
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-117.html
%F Zhao:EECS-2009-117