非表示:
キーワード:
Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
要旨:
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.
