We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham e-Theses
You are in:

Randomised Load Balancing

NAGEL, LARS (2011) Randomised Load Balancing. Doctoral thesis, Durham University.

PDF (PhD thesis of Lars Nagel) - Accepted Version


Due to the increased use of parallel processing in networks and multi-core architectures, it is important to have load balancing strategies that are highly efficient and adaptable to specific requirements. Randomised protocols in particular are useful in situations in which it is costly to gather and update information about the load distribution (e.g. in networks).
For the mathematical analysis randomised load balancing schemes are modelled by balls-into-bins games, where balls represent tasks and bins computers. If m balls are allocated to n bins and every ball chooses one bin at random, the gap between maximum and average load is known to grow with the number of balls m. Surprisingly, this is not the case in the multiple-choice process in which each ball chooses d > 1 bins and allocates itself to the least loaded. Berenbrink et al. proved that then the gap remains ln ln(n) / ln(d).
This thesis analyses generalisations and variations of the multiple-choice process. For a scenario in which batches of balls are allocated in parallel, it is shown that the gap between maximum and average load is still independent of m. Furthermore, we look into a process in which only predetermined subsets of bins can be chosen by a ball. Assuming that the number and composition of the subsets can change with every ball, we examine under which circumstances the maximum load is one. Finally, we consider a generalisation of the basic process allowing the bins to have different capacities. Adapting the probabilities of the bins, it is shown how the load can be balanced over the bins according to their capacities.

Item Type:Thesis (Doctoral)
Award:Doctor of Philosophy
Keywords:Load balancing, randomised algorithms, balls-into-bins games
Faculty and Department:Faculty of Science > Engineering and Computing Science, School of (2008-2017)
Thesis Date:2011
Copyright:Copyright of this thesis is held by the author
Deposited On:13 Oct 2011 15:12

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter