Ravindran B., Anderson J. S., Jensen E. D., On Distributed Real-Time Scheduling in Networked Embedded Systems in the Presence of Crash Failures, Lecture Notes in Computer Science, vol. 4761, pp. 67-81, DOI: 10.1007/978-3-540-75664-4_8.
We consider the problem of scheduling distributable real-time threads in networkedembedded systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. We present a distributed scheduling algorithm called CUA. We show that CUA satisfies thread time constraints in the presence of crash failures, is early-deciding, has an efficient message complexity of O(f n) (where f is the number of crashes that actually occur and n is the number of nodes), and is time-optimal with a time lower bound of O(D + f d + nk) (where D is the message delay upper bound, d is the failure detection bound, and k is the maximum number of threads). In crash-free runs, the algorithm constructs schedules within O(D + nk), and yields optimal total utility if nodes are also not overloaded. The algorithm is also “best-effort” in that a high importance thread that may arrive at any time has a very high likelihood for feasible completion (in contrast to classical admission control algorithms which favor feasible completion of admitted threads over admitting new ones, irrespective of thread importance).