The Pebble-Crunching Model for Fault-tolerant Load Balancing in Hyercube Ensembles
S. Gulati · The Computer Journal · 1990
The successful development of fifth-generation systems requires enormous computational capability and flexibility, necessitating the ability to achieve operational responses in hard real-time through optimal resource utilisation and introduction of adaptive control. This necessitates dynamically balancing the computational load among all the processing nodes in the system. In this paper we propose a graph-theoretic, receiver-initiated, distributed protocol for dynamic load balancing protocol in large-scale hypercube ensembles. Using attributed hypergraphs as the primary data structure for constraint modelling and dynamic optimisation, we consider systems running precedence-constrained heterogeneous tasks. Fault Tolerance is ensured by incorporating a dynamic integrity check for the decision nodes and their subsequent re-election if needed. Simulation studies are used to analyse the algorithm performance and correctness.