Problema de bolas en contenedores

El problema de las bolas en los contenedores (o asignaciones equilibradas ) es un problema clásico de la teoría de la probabilidad que tiene muchas aplicaciones en la informática . El problema implica m bolas y n cajas (o "contenedores"). Cada vez, se coloca una sola bola en uno de los contenedores. Una vez que todas las bolas están en los contenedores, observamos la cantidad de bolas en cada contenedor; a este número lo llamamos carga en el contenedor. El problema se puede modelar utilizando una distribución multinomial y puede implicar la formulación de una pregunta como: ¿Cuál es el número esperado de contenedores con una bola en ellos? ^[1]

Obviamente, es posible hacer que la carga sea tan pequeña como m / n colocando cada bola en el contenedor menos cargado. El caso interesante es cuando el contenedor se selecciona al azar, o al menos parcialmente al azar. Un paradigma poderoso de bolas en contenedores es el "poder de dos elecciones aleatorias ^[2] ", donde cada bola elige dos (o más) contenedores aleatorios y se coloca en el contenedor menos cargado. Este paradigma ha encontrado amplias aplicaciones prácticas en emulaciones de memoria compartida, esquemas de hash eficientes, balanceo de carga aleatorio de tareas en servidores y enrutamiento de paquetes dentro de redes paralelas y centros de datos. ^[2]

Asignación aleatoria

Cuando el contenedor para cada bola se selecciona al azar, independientemente de otras opciones, la carga máxima puede ser tan grande como . Sin embargo, es posible calcular un límite más estricto que se cumple con una alta probabilidad . Una "alta probabilidad" es una probabilidad , es decir, la probabilidad tiende a cuando crece hasta el infinito. ${\estilo de visualización m}$ ${\estilo de visualización 1-o(1)}$ ${\estilo de visualización 1}$ ${\estilo de visualización n}$

Para el caso , con probabilidad la carga máxima es: ^[3]^[4] $m=n$ ${\estilo de visualización 1-o(1)}$

${\frac {\log n}{\log \log n}}\cdot (1+o(1))$ .

Gonnet ^[5] dio un límite estricto para el valor esperado de la carga máxima, que para es , donde es la inversa de la función gamma , y se sabe ^[6] que . $m=n$ $\Gamma ^{-1}(n)-{\frac {3}{2}}+o(1)$ $Estilo de visualización: Gamma ^{-1}}$ $\Gamma ^{-1}(n)={\frac {\log n}{\log \log n}}\cdot (1+o(1))$

La carga máxima también se puede calcular para , y por ejemplo, para es , y para es , con alta probabilidad. ^[7] $m\neq n$ $m>n\log n$ ${\frac {m}{n}}+\Theta \left({\sqrt {\frac {m\log n}{n}}}\right)$ $m<n/\log n$ $\Theta \left({\frac {\log n}{\log(n/m)}}\right)$

Las probabilidades exactas para valores pequeños se pueden calcular según se define en OEIS A208250. $m=n$ $a(n)/n^{n}$ $a(n)$

Asignación parcialmente aleatoria

En lugar de seleccionar simplemente un contenedor aleatorio para cada bola, es posible seleccionar dos o más contenedores para cada bola y luego colocar la bola en el contenedor menos cargado. Este es un compromiso entre una asignación determinista, en la que se verifican todos los contenedores y se selecciona el contenedor menos cargado, y una asignación totalmente aleatoria, en la que se selecciona un solo contenedor sin verificar otros contenedores. Este paradigma, a menudo llamado el "poder de dos elecciones aleatorias", se ha estudiado en varios entornos a continuación. ^[2]

En el caso más simple, si uno asigna bolas a contenedores (con ) secuencialmente una por una, y para cada bola uno elige contenedores aleatorios en cada paso y luego asigna la bola al contenedor menos cargado de los seleccionados (los empates se resuelven arbitrariamente), entonces con alta probabilidad la carga máxima es: ^[8] ${\estilo de visualización m}$ ${\estilo de visualización n}$ $m=n$ $d\geq 2$

{\frac {\log \log n}{\log d}}+\Theta (1)

lo cual es casi exponencialmente menor que con una asignación totalmente aleatoria.

Este resultado se puede generalizar al caso (con ), cuando con alta probabilidad la carga máxima es: ^[9] $m\geq n$ $d\geq 2$

{\frac {m}{n}}+{\frac {\log \log n}{\log d}}+\Theta (1)

que es estricto hasta una constante aditiva. (Todos los límites se cumplen con probabilidad al menos para cualquier constante ). Nótese que para , el proceso de asignación aleatoria proporciona solo la carga máxima de con alta probabilidad, por lo que la mejora entre estos dos procesos es especialmente visible para valores grandes de . $1-1/n^{c}$ $c>0$ $m>n\log n$ ${\frac {m}{n}}+O\left(\log \log n\right)$ ${\estilo de visualización m}$

Otras variantes clave del paradigma son las "bolas en contenedores paralelas", donde las bolas eligen contenedores aleatorios en paralelo, ^[10] las "bolas en contenedores ponderados", donde las bolas tienen pesos no unitarios, ^[11]^[12]^[13] y las "bolas en contenedores con eliminaciones", donde las bolas se pueden agregar y eliminar. ^[2]^[14] ${\estilo de visualización n}$ ${\estilo de visualización d}$

Flujo infinito de bolas

En lugar de simplemente colocar m bolas, es posible considerar un proceso infinito en el que, en cada paso de tiempo, se añade una sola bola y se retira una sola bola, de modo que el número de bolas permanece constante. Para m = n , después de un tiempo suficientemente largo, con alta probabilidad la carga máxima es similar a la versión finita, tanto con asignación aleatoria como con asignación parcialmente aleatoria. ^[8]

Bolas en contenedores repetidas

En una variante repetida del proceso, las bolas se distribuyen inicialmente en contenedores de forma arbitraria y luego, en cada paso posterior de un proceso de tiempo discreto, se elige una bola de cada contenedor no vacío y se reasigna a uno de los contenedores de manera uniforme y aleatoria. Cuando se ha demostrado que con alta probabilidad el proceso converge a una configuración con carga máxima después de los pasos. ^[15] ${\estilo de visualización m}$ ${\estilo de visualización n}$ ${\estilo de visualización n}$ $m=n$ ${\mathcal {O}}(\log(n))$ ${\mathcal {O}}(n)$

Aplicaciones

Balanceo de carga en línea :^[16] considere un conjunto de n computadoras idénticas. Hay n usuarios que necesitan servicios informáticos. Los usuarios no están coordinados: cada usuario viene por su cuenta y selecciona qué computadora usar. Por supuesto, a cada usuario le gustaría seleccionar la computadora con menos carga, pero esto requiere verificar la carga en cada computadora, lo que puede llevar mucho tiempo. Otra opción es seleccionar una computadora al azar; esto conduce, con alta probabilidad, a una carga máxima de. Un posible compromiso es que el usuario verifique solo dos computadoras y use la menos cargada de las dos. Esto conduce, con alta probabilidad, a una carga máxima mucho menor de. ${\frac {\log n}{\log \log n}}\cdot (1+o(1))$ $\log _{2}\log n+\Theta (1)$

Hashing : considere una tabla hash en la que todas las claves asignadas a la misma ubicación se almacenan en una lista enlazada. La eficiencia de acceso a una clave depende de la longitud de su lista. Si utilizamos una única función hash que selecciona ubicaciones con probabilidad uniforme, con alta probabilidad la cadena más larga tieneclaves. Una posible mejora es utilizar dos funciones hash y poner cada nueva clave en la más corta de las dos listas. En este caso, con alta probabilidad la cadena más larga tiene soloelementos.^[17] $O\left({\frac {\log n}{\log \log n}}\right)$ $O(\log \log n)$

División justa de la torta : considere el problema de crear una división parcialmente proporcional de un recurso heterogéneo entrepersonas, de modo que cada persona reciba una parte del recurso que esa persona valora como al menosdel total, dondees una constante suficientemente grande. El protocolo Edmonds-Pruhs es un algoritmo aleatorio cuyo análisis hace uso de argumentos de bolas en contenedores.^[18] $n$ $1/an$ $a$

Referencias

^ Oliveira, Rafael (20 de mayo de 2021). "Conferencia 4: Pelotas y contenedores" (PDF) .
^ abcd Mitzenmacher, Michael ; Richa, Andrea ; Sitaraman, Ramesh (julio de 2001). "El poder de dos elecciones aleatorias: un estudio de técnicas y resultados". Manual de computación aleatoria . 1 . Kluwer Press: 255–305. CiteSeerX 10.1.1.62.6677 .
^ Kolchin, Valentín F. (1978). Asignaciones aleatorias . Washington: Winston [usw.] ISBN 978-0470993941.
^ Kotz, Samuel; Johnson, Norman Lloyd (1977). Modelos de urnas y sus aplicaciones . Nueva York, NY: John Wiley & Sons. ISBN 978-0471446309.
^ Gonnet, Gaston H. (1981). "Longitud esperada de la secuencia de sonda más larga en la búsqueda de código hash". Revista de la Asociación de Maquinaria Computacional . 28 (2): 289–304. doi : 10.1145/322248.322254 . S2CID 15483311.
^ Devroye, Luc (1985). "La longitud esperada de la secuencia de sonda más larga para la búsqueda en cubetas cuando la distribución no es uniforme". Journal of Algorithms . 6 (1): 1–9. doi :10.1016/0196-6774(85)90015-X.
^ Raab, Martín (1998). ""Bolas en contenedores" — Un análisis simple y preciso". Técnicas de aleatorización y aproximación en informática . Apuntes de clase en informática. Vol. 1518. págs. 159–170. doi :10.1007/3-540-49543-6_13. ISBN 978-3-540-65142-0.
^ ab Azar, Yossi; Broder, Andrei Z.; Karlin, Anna R.; Upfal, Eli (1999). "Asignaciones equilibradas". Revista SIAM de informática . 29 (1): 180–200. doi :10.1137/s0097539795288490.
^ Berenbrink, Petra; Czumaj, Artur; Steger, Angelika; Vöcking, Berthold (2006). "Asignaciones equilibradas: el caso de carga pesada". Revista SIAM de informática . 35 (6): 180–200. doi :10.1137/S009753970444435X.
^ Berenbrink, Petra; Czumaj, Artur; Englert, Matthias; Friedetzky, Tom; Nagel, Lars (2012). Asignación equilibrada de opciones múltiples en (casi) paralelo . APPROX 2012, RANDOM 2012: Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas. págs. 411–422. CiteSeerX 10.1.1.297.6120 . doi :10.1007/978-3-642-32512-0_35.
^ Talwar, Kunal; Udi, Wieder (2007). Asignaciones equilibradas: el caso ponderado . Actas del 39.º Simposio anual de la ACM sobre teoría de la computación (STOC). págs. 256-265. doi :10.1145/1250790.1250829.
^ Berenbrink, Petra; Friedetzky, Tom; Zengjian, Hu; Russell, Martin (2005). Juegos de lanzamiento de bolas con peso a los contenedores . STACS. págs. 231–243. doi :10.1007/978-3-540-31856-9_19.
^ Peres, Yuval; Talwar, Kunal; Wieder, Udi (2015). Asignaciones equilibradas gráficas y el proceso de elección . Algoritmos de estructuras aleatorias . págs. 760–775. doi :10.1002/rsa.20558. $(1+\beta )$
^ Cole, Richard; Frieze, Alan; Maggs, Bruce M.; Mitzenmacher, Michael; Richa, Andrea; Sitaraman, Ramesh; Upfal, Eli (1998). Sobre bolas y contenedores con deleciones . Técnicas de aleatorización y aproximación en informática (Barcelona, 1998). pp. 145–158. doi :10.1007/3-540-49543-6_12.
^ Becchetti, LucaBecchetti; Clementi, Andrea; Natale, Emanuele; Pasquale, Francesco; Posta, Gustavo (13 de junio de 2015). "Bolas-en-cubos repetidas autoestabilizadoras". Actas del 27.º simposio de la ACM sobre paralelismo en algoritmos y arquitecturas . SPAA '15. Portland, Oregón, EE. UU.: Association for Computing Machinery. págs. 332–339. doi :10.1145/2755573.2755584. hdl : 11573/780594 . ISBN . 978-1-4503-3588-1.
^ Raab, Martin; Steger, Angelika (1998). ""Balls into Bins" — A Simple and Tight Analysis". En Luby, Michael; Rolim, José DP; Serna, Maria (eds.). Técnicas de aleatorización y aproximación en informática . Apuntes de clase en informática. Vol. 1518. Berlín, Heidelberg: Springer. págs. 159–170. doi :10.1007/3-540-49543-6_13. ISBN 978-3-540-49543-7.
^ Karp, RM (1996). "Simulación eficiente de PRAM en una máquina de memoria distribuida". Algorithmica . 16 (4–5): 517–542. doi :10.1007/bf01940878. S2CID 2535727.
^ Edmonds, Jeff; Pruhs, Kirk (2006). "Asignaciones equilibradas de la torta" (PDF) . 2006 47.° Simposio anual IEEE sobre fundamentos de la informática (FOCS'06) . pp. 623–634. doi :10.1109/FOCS.2006.17. ISBN 0-7695-2720-5.S2CID2091887 .