Back to results list
Show full item record
Please use this identifier to cite or link to this item:
|Title:||A \(\sqrt N \) dynamic load distribution algorithm using anti-tasks and load state vectors|
|Authors:||Lu, Q |
|Keywords:||Dynamic load distribution|
Load state vector
Finite projective plane
|Publisher:||Kluwer Academic Publishers|
|Source:||Cluster computing, 2004, v. 7, no. 1, p. 51-63 How to cite?|
|Abstract:||One of the fundamental issues to ensure maximal performance improvement in a cluster computing environment is load distribution, which is commonly achieved by using polling-based load distribution algorithms. Such algorithms suffer from two weaknesses: (1) Load information exchanged during a polling session is confined to the two negotiating nodes only. (2) Such algorithms are not scalable in that growth of the distributed system is accompanied with increasing amount of polling sessions.|
In this paper, we proposed a LD algorithm which is based on anti-tasks and load state vectors. Anti-tasks travel around the distributed system for pairing up task senders and receivers. As an anti-task travels, timed load information is collected and disseminated over the entire system via the load state vector bundled with the anti-task. Guided by load state vectors, anti-tasks are spontaneously directed towards processing nodes having high transient workload, thus allowing their surplus workload to be relocated soonest possible. No peer-to-peer negotiations between senders and receivers are needed.
To reduce the network bandwidth consumption caused by the anti-task algorithm, the number of hosts that an anti-task needs to travel to must be carefully limited. The algorithm achieves this by employing the mathematical notion of Finite Projective Plane (FPP). By employing FPP, the number of nodes that each anti-task has to travel is at most \(\sqrt N \), where N is the number of nodes in the system, without sacrifying the spread of load information.
|Appears in Collections:||Journal/Magazine Article|
Show full item record
Checked on May 21, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.