Improved Task-Allocation Algorithms to Maximize Reliability of Redundant Distributed Computing Systems

This paper considers the problem of finding an optimal & sub-optimal task-allocation (assign the processing node for each module of a task or program) in redundant distributed computing systems, with the goal of maximizing system-reliability (probability that the system completes the entire task successfully). Finding an optimal task-allocation is NP-hard in the strong sense. An efficient algorithm is presented for optimal task-allocation in a distributed computing system with level-2 redundancy. The algorithm, a) uses branch & bound with underestimates for reducing the average time complexity of optimal task-allocation computations, and b) reorders the list of modules to allow a subset of modules that does not intra-communicate to be assigned last, for further reduction in the computations of optimal task-allocation for maximizing reliability. An efficient heuristic algorithm is given which obtains sub-optimal solutions in a reasonable computation time. The performance of our algorithms is given over a wide range of parameters such as: number of modules, number of processing nodes, ratio of average execution cost to average communication cost, and connectivity of modules. The effectiveness of the optimal task-allocation algorithm is demonstrated by comparing it to a recent competing optimal task-allocation algorithm, for maximizing reliability. The performance of our algorithm improves very much when the difference between the number of modules and the connectivity increases. Our heuristic algorithm produced optimal solutions in 24% of the cases and found allocations within 1.5 times the optimal in about 86% of the cases.1 ©1995 IEEE