Integrated Real-Time Scheduling and Communication with Probabilistic Timing Assurances in Unreliable Distributed Systems
Fei Huang, Kai Han, Binoy Ravindran, E. Douglas Jensen · 2008
We consider distributed real-time systems that operate under run-time uncertainties including those on execution times and communication delays, and subject to arbitrary node failures and message losses. We present an integrated real-time scheduling and communication algorithm called real-time scheduling with reliable data delivery (RTSRD) that provides probabilistic end-to-end assurances on distributed task timeliness behaviors in such systems. RTSRD considers distributed tasks with end-to-end timing requirements that are expressed using time/utility functions and the optimality criterion of maximizing the total accrued utility. The algorithm decomposes end-to-end time constraints into local time constraints, and uses local slack time for node-local real-time scheduling and node-to-node real-time communication. We analytically establish RTSRD's properties including probabilistic satisfaction of task time constraints. We also compare RTSRD with a prior algorithm called RTG- L for the same problem. Our comparisons show that RTSRD outperforms RTG-L in terms of timeliness assurances (stronger) and algorithm overhead (lower).