University of Cambridge > Talks.cam > Wednesday Seminars - Department of Computer Science and Technology > Randomised Load Balancing For Networks

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Randomised Load Balancing For Networks

Download to your calendar using vCal

If you have a question about this talk, please contact David Greaves .

We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbours. The goal is to obtain a load distribution where all nodes have the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is fairly well-understood.

However, in many applications load items cannot be divided arbitrarily often and we need to deal with the discrete case where load is composed of indivisible tokens. In this talk we investigate a natural randomised protocol and demonstrate that there is almost no difference between the discrete and continuous case. Specifically we show that for any regular network all nodes have the same number of tokens up to an additive constant in the same number of rounds as in the continuous case.

This talk is part of the Wednesday Seminars - Department of Computer Science and Technology series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

LR12, Baker Building, Department of Engineering (Trumpington Street, Cambridge CB2 1PZ) The Royal College of Pathologists, London, UK Master's Lodge, Clare College

Other talks

Cooperation as a Laboratory of Being Cooperation for Nature Title to be confirmed Paediatric Medicine and Rheumatology Group Work Cambridge RNA Club - ONLINE
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity