A task migration algorithm for heterogeneous distributed computing systems
Abstract Most load balancing schemes are based on the assumption that all processors in a distributed computing system (DCS) have similar processing power and workload. However, as technology continues to advance, networks have become more likely to contain processors of different capabilities and configurations. The proposed load balancing method is based on the coterie , a tool first used in mutual exclusion and vote assignment. This paper describes how the unique properties of coteries allow the underlying protocol to be tailored to the capabilities of the individual nodes in a connected network. In general, each processor communicates with only a subset of the other processors in the network, keeping message traffic relatively low. The coterie allows these subsets to be constructed according to a more thoughtful method – one that is designed to better meet the needs of networks of varying characteristics. It is also shown that the proposed method will always perform task migration whenever possible i.e., if at least one lightly loaded processor and at least one heavily loaded processor exist in the network, task migration will occur. Further, an extension of our algorithm to provide fault tolerance is given: when a processor fails, the network can continue to function with a modified system configuration.