Effective load sharing in distributed real-time systems

In a distributed real-time system, temporary uneven task arrivals among the nodes may cause some tasks to miss their deadlines even if the overall system has the capacity to meet the deadlines of all tasks. In this paper, an effective load sharing (LS) scheme is proposed as a solution to this problem. Upon arrival of a task at a node, the node determines whether or not it can complete the task in time under the minimum-laxity-first-served policy. If the task cannot be guaranteed or if guarantees of some other tasks are to be violated due to the insertion of this task into the existing schedule, the node looks up the list of loss-minimizing decisions, and determines the best node among a set of nodes in its physical proximity, called its buddy set, to which the task(s) may be transferred. This list of decisions is periodically updated using Bayesian decision analysis and prior/posterior state distributions. These probability distributions are derived from the information collected via time-stamped state-region change broadcasts within each buddy set. The performance of the proposed scheme is evaluated via simulation along with five other schemes. The proposed scheme is shown to outperform all but perfect LS scheme in (i) meeting task deadlines and (ii) tolerating the delays in state-information collection and task transfer