Parallel Balanced Allocations: The Heavily Loaded Case

Christoph Lenzen, Merav Parter, Eylon Yogev

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנס

תקציר

We study parallel algorithms for the classical balls-into -bins problem, in which m balls acting in parallel as separate agents are placed into n bins. Algorithms operate in synchronous rounds, in each of which balls and bins exchange messages once. The goal is to minimize the maximal load over all bins using a small number of rounds and few messages. While the case of m = n balls has been extensively studied, little is known about the heavily loaded case. In this work, we consider parallel algorithms for this somewhat neglected regime of m >> n. The naive solution of allocating each ball to a bin chosen uniformly and independently at random results in maximal load m/n 0(Vm/n " log n) (for m > n log n) with high probability (w.h.p.). In contrast, for the sequential setting Berenbrink et al. [5] showed that letting each ball join the least loaded bin of two randomly selected bins reduces the maximal load to m/ n 0(log log m) w.h.p. To date, no parallel variant of such a result is known. We present a simple parallel threshold algorithm that obtains a maximal load of m/ n + 0(1) w.h.p. within 0(log log(m/n) + log* n) rounds. The algorithm is symmetric (balls and bins all "look the same"), and balls send 0(1) messages in expectation. The additive term of O(log* n) in the complexity is known to be tight for such algorithms [10]. We also prove that our analysis is tight, i.e., algorithms of the type we provide must run for 11(min{log log (m / n), n}) rounds w.h.p. Finally, we give a simple asymmetric algorithm (i.e., balls are aware of a common labeling of the bins) that achieves a maximal load of m/ n + 0(1) in a constant number of rounds w.h.p. Again, balls send only a single message per round, and bins receive (1 + o(1))m/n 0 (log n) messages w.h.p. This goes to show that, similar to the case of m = n, asymmetry allows for highly efficient solutions.

שפה מקוריתאנגלית
כותר פרסום המארחSPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures
מוציא לאורAssociation for Computing Machinery (ACM)
עמודים313-322
מספר עמודים10
מסת"ב (אלקטרוני)9781450361842
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 17 יוני 2019
אירוע31st ACM Symposium on Parallelism in Algorithms and Architecturess (SPAA) - Phoenix, אזרבייג'אן
משך הזמן: 22 יוני 201924 יוני 2019

סדרות פרסומים

שםAnnual ACM Symposium on Parallelism in Algorithms and Architectures

כנס

כנס31st ACM Symposium on Parallelism in Algorithms and Architecturess (SPAA)
מדינה/אזוראזרבייג'אן
עירPhoenix
תקופה22/06/1924/06/19

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1708???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Parallel Balanced Allocations: The Heavily Loaded Case'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי