Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/10913
 Title: A $$\sqrt N$$ dynamic load distribution algorithm using anti-tasks and load state vectors Authors: Lu, Q Leung, KSLau, SM Keywords: Dynamic load distributionAnti-taskLoad state vectorFinite projective planeDistributed algorithmsPerformance modeling Issue Date: 2004 Publisher: Kluwer Academic Publishers Source: Cluster computing, 2004, v. 7, no. 1, p. 51-63 How to cite? Journal: Cluster computing 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. URI: http://hdl.handle.net/10397/10913 ISSN: 1386-7857 DOI: 10.1023/B:CLUS.0000003943.34384.93 Appears in Collections: Journal/Magazine Article

###### Access
View full-text via PolyU eLinks

#### Page view(s)

44
Last Week
0
Last month
Citations as of Aug 13, 2018