Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm

MPG-Autoren
/persons/resource/persons123371

Lenzen,  Christoph
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0024-48BB-3
Zusammenfassung
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.