Partially Synchronous Distributed Real-Time Systems

The proposed project "Partially Synchronous Distributed Real-Time Systems" (PSRTS) ist 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 proposed 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.

The ultimate goal of PSRTS (Partially Synchronous Distributed Real-Time Systems) has been to add a proper real-time systems perspective to fault-tolerant distributed algorithms, by establishing a sound scientific basis for fault-tolerant distributed real-time systems with a high degree of concurrency and, hence, relaxed synchrony-by-design. By contrast, state-of-the-art 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. Although strict synchrony-by-design greatly simplifies the handling of both real-time and fault-tolerance requirements, it 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 sub-optimal utilization, i.e., wasting resources, this also creates the danger of running the system outside its specification sometimes. Given the often severe power & space constraints and the criticality of aerospace/automotive applications, for example, increasing the concurrency in the system in order to better utilize scarce computing resources and to reduce the system's vulnerability is important. PSRTS has been devoted to the development of the scientific basis for such systems, and provided the following major results:A comprehensive Real-Time Model, which is the first distributed computing model that reconciles fault-tolerant distributed algorithms with real-time analysis. Essentially, it replaces zero-time state transitions by non-zero non-preemptable time computing steps and thus allows queueing effects and scheduling issues to enter the picture.Several instances of partially synchronous system models, like the time-free Asynchronous Bounded Cycle model, which provide different relaxations of synchrony conditions, as well as related algorithms for fault-tolerant distributed agreement and proof techniques. Advanced (real-time) analysis techniques, primarily based on non-standard algebras, and their application to some network algorithms. Essentially, these methods allow to treat distributed systems as linear dynamic systems.Besides its primary research results, PSRTS also stimulated several follow-up projects, including transdisciplinary research in formal verification and digital integrated circuits.