English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm

Bertrand, P., & Lenzen, C. (2015). The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm. In U. Brandes, & D. Eppstein (Eds.), Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (pp. 44-54). Philadelphia, PA: SIAM. doi:10.1137/1.9781611973754.5.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-48BB-3 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-002C-83C7-C
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Bertrand, Pierre1, Author
Lenzen, Christoph2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
 Abstract: In this work, we examine a generic class of simple distributed balls-into-bins algorithms. Exploiting the strong concentration bounds that apply to balls-into-bins games, we provide an iterative method to compute accurate estimates of the remaining balls and the load distribution after each round. Each algorithm is classified by (i) the load that bins accept in a given round, (ii) the number of messages each ball sends in a given round, and (iii) whether each such message is given a rank expressing the sender's inclination to commit to the receiving bin (if feasible). This novel ranking mechanism results in notable improvements, in particular in the number of balls that may commit to a bin in the first round of the algorithm. Simulations independently verify the correctness of the results and confirm that our approximation is highly accurate even for a moderate number of $10^6$ balls and bins.

Details

show
hide
Language(s): eng - English
 Dates: 201420152015
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: BertrandL15
DOI: 10.1137/1.9781611973754.5
URI: http://groups.csail.mit.edu/tds/papers/Lenzen/BL15toolkit-alenex.pdf
 Degree: -

Event

show
hide
Title: Seventeenth Workshop on Algorithm Engineering and Experiments
Place of Event: San Diego, CA, USA
Start-/End Date: 2015-01-05 - 2015-01-05

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments
  Subtitle : ALENEX15 ; Meeting on Algorithm Engineering & Experiments
  Abbreviation : ALENEX 2015
Source Genre: Proceedings
 Creator(s):
Brandes, Ulrik1, Editor
Eppstein, David1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Philadelphia, PA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 44 - 54 Identifier: ISBN: 978-1-61197-375-4