On Structural Robustness of Distributed Real-Time Systems Towards Uncertainties in Service Times

As real-time systems are becoming increasingly distributed, it becomes important to understand their structural robustness with respect to timing uncertainty. Structural robustness, a concept that arises by virtue of multi-stage execution, refers to the robustness of end-to-end timing behavior of an execution graph towards unexpected timing violations in individual execution stages. A robust topology is one where such violations minimally affect end-to-end execution delay. The paper shows that the manner in which resources are allocated to execution stages can make a difference in robustness. Algorithms are presented and evaluated for resource allocation that improve the robustness of execution graphs. Evaluation shows that such algorithms are able to significantly reduce deadline misses due to unpredictable timing violations. Hence, the approach is important for soft real-time systems, systems where timing uncertainty exists, or where worst-case timing is not entirely verified.