Partially Synchronous Distributed Real-Time Systems

26.02.2008 - 30.11.2012
Forschungsförderungsprojekt
The project "Partially Synchronous Distributed Real-Time Systems" (PSRTS) is devoted to the development of a sound scientific basis for fault-tolerant distributed hard real-time systems with a high degree of concurrency and, hence, relaxed synchrony-by-design. By contrast, most existing distributed hard real-time systems adhere to the synchronous distributed computing paradigm, which is based on a fine-grained common notion of time that can be used to closely synchronize all distributed computations. For example, the popular Time-Triggered Protocol TTP is based on distributed processes that communicate over shared buses via time-slotted communication (TDMA). This approach, which obviously limits the concurrency in the system considerably, greatly simplifies the handling of both real-time and fault-tolerance requirements, but does not allow the application to fully exploit the computing power available in the system: Due to the inevitable overhead of synchronous computation and communication, it is essentially the slowest part of the system that determines the overall computing speed. Besides wasting resources, this also creates the danger of under-estimating the worst case delay bounds required for synchrony-by-design, and hence running the system outside its specification sometimes. Given the often severe power & space constraints and the criticality of aerospace/automotive applications, for example, it is tempting to increase the concurrency in the system in order to better utilize the scarce computing resources and to reduce the system's vulnerability with respect to incorrectly estimated worst case bounds. Past research has explored several ways for achieving this: Essentially, the synchrony degree of a distributed real-time system can be relaxed in time, in space, and via suitable (partially synchronous) algorithms. We focus entirely on the latter approach here, which is particularly promising and challenging from a research perspective: Much research has been (and is being) conducted on partially synchronous distributed algorithms that can be started from. On the other hand, we are not aware of any research on how to conduct a worst case response time analysis in a system that it not synchronous by design. The project PSRTS targets exactly this gap in the intersection between distributed algorithms and real-time systems: Its purpose is to revise/adapt/extend existing approaches in order to add a proper real-time systems perspective to the theory of distributed algorithms. The project consists of three cleanly defined sub-topics, namely, (1) provision of a distributed real-time computing model, which is compatible with classic distributed computing models but also allows to incorporate real-time scheduling and analysis, (2) the selection/development of a partially synchronous system model, which is synchronous enough to allow a solution of all important distributed computing problems (like consensus) but asynchronous enough to allow a significant degree of concurrency, and, (3) a reasonably simple but realistic worst case schedulability analysis of distributed algorithms running atop of (1) & (2), which allows to break the inevitable cyclic dependency of the timing performances of a distributed algorithm and the underlying distributed computing system.

Personen

Projektleiter_in

Projektmitarbeiter_innen

Institut

Grant funds

  • FWF - Österr. Wissenschaftsfonds (National) Austrian Science Fund (FWF)

Forschungsschwerpunkte

  • Computer Engineering: 100%

Schlagwörter

DeutschEnglisch
Distributed Computing Modelsdistributed computing models
Partiell Synchrone Systemepartially synchronous systems
Fehlertolerante verteilte Echtzeitsystemefault-tolerant distributed real-time systems
Echtzeit-Schedulingreal-tim scheduling
Worst-Case Response Time Analysisworst case response time analysis

Publikationen