Dynamic Load Sharing Algorithm For Distributed Real-time System

If task arrivals are not uniformly distributed over the nodes in a distributed real-time system, some nodes may become overloaded while others are underloaded. Consequently, some tasks cannot be completd before their deadlines, even if the overall system has the capacity to meet all deadlines. Load sharing (LS) is one way to alleviate this problem.This paper addresses a ?fault-tolerant, dynamic load sharing (LS) with state-region change broadcasts in the presence of node failures for a distributed real-time system. Whenever the state of a node changes from underloaded to fully- loaded and vice versa, the node broadcast this change to a set of nodes, called a buddy set, in the system. An overloaded node can select, without probing other nodes, the first available node from its preferred list. In this paper, mainly, we address two important issues associated with the LS:(1) we determine the "best" timeout period 7^'/ though which failure of a node is diagnosed by the other nodes. That is to say, if node n has not heard from node i for T^ since its receipt of the latest broadcast from node i, it will consider node i failed, and will not consider any task transfer to node i until it receives a broadcast message from node i again.(2) we propose algorithms to modify the preferred list in such a way that each node will be selected as the km preferred node of one and only one other node and proposed a simple mechanism to tolerate node failures.The timeout period used to diagnose whether a node is faulty or not usually depends on the dynamic changes in system load, the task attributes at the node, and the state the node was initially in. The parameters needed for the calculation of T^ are estimated'on-line by node i using the Bayesian techique. The broadcast information is then used to determineOur simulation results show that the LS algorithms which combines the on-line parameter estimation, the timeout mechanism, and a few extra timely broadcasts can significantly reduce the probability of missing task deadlines, as compared to the other algorithms either without any timeout mechanism or with a fixed timeout period. The preferred lists modified by the proposed algorithms are shown to retain their original properties regardless of the number of faulty nodes in the system, and the simple fault-tolerant BKQ is shown to reduce the number of task losses.