Optimal Load Sharing in Distributed Real-Time Systems

Abstract

The main goal of this paper is to derive an approximate, closed-form solution for the decentralized, dynamic load sharing (LS) problem treated in an earlier paper. In that paper, whenever the load state of a node changes from underloaded to fully loaded and vice versa, the node broadcasts this change to a set of nodes in its physical proximity, called a buddy set. An overloaded node can select, without probing other nodes, the first available node from its preferred list, an ordered buddy set. Preferred lists are so constructed that the probability of more than one overloaded node sending tasks to an underloaded node may be made very small. In hard real-time systems, the problem of scheduling periodic tasks to meet their deadlines has been studied extensively, but scheduling aperiodic tasks has been addressed far less, due mainly to their random arrivals. We show that the proposed LS method can be used to effectively handle aperiodic tasks in distributed real-time systems. The probability of missing task deadlines can be kept below a specified level by choosing appropriate threshold patterns and buddy set sizes which are derived from the approximate closed-form solution. Specifically, "optimal" threshold patterns and buddy set sizes are derived for different system loads by minimizing the communication overhead subject to a constraint of keeping the probability of missing task deadlines below any given level. (One can also derive optimal solutions by minimizing the probability of missing deadlines while keeping the communication overhead below a specified level.) Several examples are presented to demonstrate the power and utility of the proposed LS approach.