How useful is old information (extended abstract)?
Michael Mitzenmacher · 1997
We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old information.For example, consider a multiprocessor system where incoming tasks with exponentially distributed service requirements arrive x a Poisson process, the tasks must choose a processor for service, and a task knows when making this choice the processor loads from T seeonds ago, What is a good strategy for choosing a processor, in order for tasks to minimize their expected time in the system?Such models can also be used to describe set tings where there is a transfer delay between the time a task enters a system and the time it reaches a processor for service.Our models are based on considering the behavior of limiting systems where the number of processors goes to infinity.The limiting systems can be shown to accurately describe the behavior of sufficiently large systems, and simulations demonstrate that they me reasonably accurate even for systems with a small number of processors.Our studies of specific models demonstrate the importance of using randomness to break symmetry in these systems and yield importaut rules of thumb for system design.The most significant result is that only small amounts of load information cart be extremely useful in these settings; for example, having incoming tasks choose the least loaded of two randomly chosen processors is extremely effective over a large range of possible system parameters.In contrast, using global information can actuzdly degrade performwtce unless used correctly; for example, unlike most settings where the load information is current, having tasks go to the least loaded server can significantly hurt performance.Permissionto make digitiilkrrd copiesof all or pori of thismaterial for personalor classroomuseis grantedwithoutfee providedthl thecopies are nol modeor distributedfor profit or commercialadvwl~tgq (heeapyright notice, the tilie of the publimtie-rr mrd its date appew, and notiw is given that copyright is by permission of the ACM, Inc.To copyotherwise, 10republish, to post on servers or to redistribute to lists, requires specific pemlission mvdlor fee 1997