The Asymptotics of Selecting the Shortest of Two, Improved

View/ Open
Author
Vocking, Berhold
Note: Order does not necessarily reflect citation order of authors.
Metadata
Show full item recordCitation
Mitzenmacher, Michael and Berhold Voecking. 1999. The Asymptotics of Selecting the Shortest of Two, Improved. Harvard Computer Science Group Technical Report TR-08-99.Abstract
We investigate variations of a novel, recently proposed load balancing scheme based on small amounts of choice. The static (hashing) setting is modeled as a balls-and-bins process. The balls are sequentially placed into bins, with each ball selecting d bins randomly and going to the bin with the fewest balls. A similar dynamic setting is modeled as a scenario where tasks arrive as a Poisson process at a bank of FIFO servers and queue at one for service. Tasks probe a small random sample of servers in the bank and queue at the server with the fewest tasks. Recently is has been shown that breaking ties in a fixed, asymmetric fashion, actually improves performance, whereas in all previous analyses, ties were broken randomly. We demonstrate the nature of this improvement using fluid limit models, suggest further improvements, and verify and quantify the improvement using fluid limit models, suggest further improvements, and verify and quantify the improvement through simulations.Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:24829612
Collections
- FAS Scholarly Articles [18172]
Contact administrator regarding this item (to report mistakes or request changes)