The Asymptotics of Selecting the Shortest of Two, Improved

DSpace/Manakin Repository

The Asymptotics of Selecting the Shortest of Two, Improved

Citable link to this page

 

 
Title: The Asymptotics of Selecting the Shortest of Two, Improved
Author: Mitzenmacher, Michael D.; Vocking, Berhold

Note: Order does not necessarily reflect citation order of authors.

Citation: Mitzenmacher, Michael and Berhold Voecking. 1999. The Asymptotics of Selecting the Shortest of Two, Improved. Harvard Computer Science Group Technical Report TR-08-99.
Full Text & Related Files:
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#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:24829612
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters