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 
Leung, KS
Lau, SM
Keywords: Dynamic load distribution
Load state vector
Finite projective plane
Distributed algorithms
Performance 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.
ISSN: 1386-7857
DOI: 10.1023/B:CLUS.0000003943.34384.93
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Citations as of Aug 13, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.