¡¡	Chinese Journal of Computers   Full Text
Title	Load Balancing Based Process Scheduling with Fault-Tolerance in Heterogeneous Distributed System
Authors	GUO Hui1) WANG Zhi-Guang1) ZHOU Jing-Li2)
Address	1)(Department of Computer Science and Technology, Petroleum University of China, Beijing 100220) 2)(School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074)
Year	2005
Issue	No.11(1807¡ª1816)
Abstract &   Background	The primary-backup process model for process allocation is an important research area in the study of fault-tolerant distributed system. In this paper, two heuristic approximation algorithms are proposed and analyzed, which are named as HDALF(heterogeneous distributed-system actual load first) and HDLDF(heterogeneous distributed-system load difference first). And the algorithms¡¯ complexity is presented. Different from the previous work, the new fault-tolerant process model is based on the passive process replica model. Previous research work usually provided that the primary and backup processes have the same overhead all the time, or are based on homogeneous distributed system. The proposed algorithms are compared with the two-stage allocation algorithm, which is for homogeneous distributed system. The experimental results show that the proposed algorithms have significantly better performance than the two-stage algorithm. Additionally, in the case that the relative important weights are equal between before and after fault occurrence, the performance of HDLDF algorithm is better than HDALF from the view of load-balancing and the processor utilizing rate. keywords fault-tolerant system£» heterogeneous distributed system£» load balancing£» fault-tolerant scheduling algorithm£» process allocation background This work was supported by the National High Technology Research and Development Program of China (863 Program) under grant Noª±2001AA111011. Process allocation is a pivotal issue in distributed systems. In this area, primary-backup process model is an important scheme for system fault-tolerance. The traditional algorithms (such as two-stage algorithm) based on primary-backup process mode only adapt to homogeneous distributed system. As the heterogeneous multi-processor system is more prevalent now, authors¡¯ research work focused on process allocation issue in heterogeneous multi-processor circumstance, and the allocation results should guarantee load balance for each processor. In this paper, two heuristic approximation algorithms are proposed and analyzed. The experimental results show that the proposed algorithms have significantly better performance especially for heterogeneous distributed system environment.