Design and evaluation of effective load sharing in distributed real-time systems

In a distributed real-time system, uneven task arrivals temporarily overload some nodes and leave others idle or underloaded. Consequently, some tasks may miss their deadlines even if the overall system has the capacity to meet the deadlines of all tasks. 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 the node 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 as a result of the addition of this task to 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. By characterizing the inconsistency between a node´s “observed” state and the corresponding true state with prior and posterior distributions, the node can first estimate the states of other nodes, and then use them to reduce the probability of transferring a task to an “incapable”) node. Moreover, the use of prior and posterior distributions and Bayesian analysis has made the proposed scheme robust to the variation of design parameters that usually require fine-tuning for adaptive LS. The performance of the proposed scheme is evaluated via simulation, along with five other schemes: no LS, LS with state probing, LS with random selection, LS with focused addressing, and perfect LS