A TASK MIGRATION ALGORITHM FOR HETEROGENEOUS DISTRIBUTED COMPUTING SYSTEMS

Most load balancing schemes are based on the assumption that all proce ssors in a distributed computing system (DCS) have similar processing power and workload. However, as technology continues to advance, netwo rks have become more likely to contain processors of different capabil ities and configurations. The proposed load balancing method is based on the coterie, a tool first used in mutual exclusion and vote assignm ent. This paper describes how the unique properties of coteries allow the underlying protocol to be tailored to the capabilities of the indi vidual nodes in a connected network. In general, each processor commun icates with only a subset of the other processors in the network, keep ing message traffic relatively low. The coterie allows these subsets t o be constructed according to a more thoughtful method - one that is d esigned to better meet the needs of networks of varying characteristic s. It is also shown that the proposed method will always perform task migration whenever possible i.e., if at least one lightly loaded proce ssor and at least one heavily loaded processor exist in the network, t ask migration will occur. Further, an extension of our algorithm to pr ovide fault tolerance is given: when a processor fails, the network ca n continue to function with a modified system configuration. (C) 1998 Elsevier Science Inc. All rights reserved.