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)
عدد الصفحات10
رقم المعيار الدولي للكتب (الإلكتروني)9781450361842
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 17 يونيو 2019
الحدث31st ACM Symposium on Parallelism in Algorithms and Architecturess (SPAA) - Phoenix, أذربيجان
المدة: ٢٢ يونيو ٢٠١٩٢٤ يونيو ٢٠١٩

سلسلة المنشورات

الاسمAnnual ACM Symposium on Parallelism in Algorithms and Architectures


!!Conference31st ACM Symposium on Parallelism in Algorithms and Architecturess (SPAA)

All Science Journal Classification (ASJC) codes

  • !!Software
  • !!Theoretical Computer Science
  • !!Hardware and Architecture


أدرس بدقة موضوعات البحث “Parallel Balanced Allocations: The Heavily Loaded Case'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا