The balls-and-bins problem is a fundamental problem in probability theory, analyzing the distribution of m balls randomly placed into n bins. It examines the likelihood of finding a certain number of balls in any given bin. This problem has many practical applications in computer science, such as load balancing in distributed systems. Weighted rendezvous hashing is one approach where bins have different weights (capacities), and the goal is to assign balls to bins such that no bin is unbalanced and, at the same time, all bins are approximately equally utilized. Weighted rendezvous hashing uses a deterministic algorithm to achieve this balance, though the foundations of the algorithm come from probability theory. We will discuss some of the applications and the theory behind these algorithms.
Balls in bins