The balls into bins (or balanced allocations) problem is a classic problem in probability theory that has many applications in computer science. The problem involves m balls and n boxes (or "bins"). Each time, a single ball is placed into one of the bins. After all balls are in the bins, we look at the number of balls in each bin; we call this number the load on the bin. The problem can be modelled using a Multinomial distribution, and may involve asking a question such as: What is the expected number of bins with a ball in them?[1]
Obviously, it is possible to make the load as small as m/n by putting each ball into the least loaded bin. The interesting case is when the bin is selected at random, or at least partially at random. A powerful balls-into-bins paradigm is the "power of two random choices[2]" where each ball chooses two (or more) random bins and is placed in the lesser-loaded bin. This paradigm has found wide practical applications in shared-memory emulations, efficient hashing schemes, randomized load balancing of tasks on servers, and routing of packets within parallel networks and data centers.[2]
^ abMitzenmacher, Michael; Richa, Andrea; Sitaraman, Ramesh (July 2001). "The power of two random choices: A survey of techniques and results". Handbook of Randomized Computing. 1. Kluwer Press: 255–305. CiteSeerX 10.1.1.62.6677.
and 22 Related for: Balls into bins problem information
The problem involves m balls and n boxes (or "bins"). Each time, a single ball is placed into one of the bins. After all balls are in the bins, we look...
velocity distributions. The Ellsberg paradox. Ballsintobins Coin-tossing problems Coupon collector's problem Dirichlet-multinomial distribution Noncentral...
Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either...
clearance shot might also be used at the end of an inning to move some problemballs that are blocking an otherwise easy run, and leave the cue ball in a...
Gang use the Dragon Balls to wish for the restoration of their youth, only for the wish to backfire and them being transformed into young children by Shenron...
unsuitable, any other material object may be used, with garbage bins (especially wheelie bins) being common, and some people also use stickers or paint lines...
indistinguishable ballsinto m {\displaystyle m} indistinguishable bins, where each bin can contain up to n {\displaystyle n} balls. The Gaussian binomial...
that sets bowling pins back in their original positions, returns bowling balls to the front of the alley, and clears fallen pins on the pin deck. Prior...
the golden balls from the collapsing machine, only to run into Tack while escaping. After a brief scuffle, the thief, realizing the balls are not worth...
addition, the ball bins were placed on opposite ends of the field and the contenders had to alternate which bin they chose balls from. The Gladiators...
mine flail consists of a number of heavy chains ending in fist-sized steel balls (flails) that are attached to a horizontal, rapidly rotating rotor mounted...
inexperience, and is left with the problem of choosing which identity to make the official member. Seeing this a problem, both personae begin to sing a Broadway-style...
film was made based on the characters in the show titled Our Russia. The Balls of Fate. The name of the show references the fact that while the name of...
on Egyptian fractions, as is the Erdős–Graham problem on whether, for every partition of the integers into finitely many classes, one of these classes has...
continuous random variable). For example, in a bag of 2 red balls and 2 blue balls (4 balls in total), the probability of taking a red ball is 1 / 2 ;...
Turning their focus to the area of the stone causeway there are problems with water flowing into the area that is being excavated. In Smith's Cove, Gary and...
Division in the same period. In March 2018, Mashrafe took four wickets in four balls bowling for Abahani Limited against Agrani Bank Cricket Club in the 2017–18...
the solar system. When the planetarium is closed, Arnold suggests they go into outer space. The class explores Mercury, Venus, and Mars, while Janet collects...
contact lens cases, a mesh filter from a range hood, refrigerator shelves and bins, toothbrush holders, pet bowls and pet toys. Cleaning vegetables and plastics...
King, Jr. Day, the swearing-in ceremony, a luncheon and parade, inaugural balls, and an interfaith inaugural prayer service. Chief Justice of the United...
The black substance proves to be naphthalene dust, and there are smoke balls to make smoke at the house fire; it was a set-up scene, all the smoke. Blake...
Global Information