IMPROVED TASK-ALLOCATION ALGORITHMS TO MAXIMIZE RELIABILITY OF REDUNDANT DISTRIBUTED COMPUTING SYSTEMS

作     者：KARTIK, S MURTHY, CSR 

作者机构：INDIAN INST TECHNOL DEPT COMP SCI & ENGN MADRAS 600036 TAMIL NADU INDIA 

出 版 物：《IEEE TRANSACTIONS ON RELIABILITY》 (IEEE Trans. Rel.)

年 卷 期：1995年第44卷第4期

页      面：575-586页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Indian National Science Academy, INSA Department of Science and Technology, Ministry of Science and Technology, India, डीएसटी 

主　　题：TASK ALLOCATION DISTRIBUTED COMPUTING SYSTEM SYSTEM RELIABILITY OPTIMALITY SEARCH TREE HEURISTIC 

摘      要：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