Vi utforskar de grundläggande gränserna för distribuerade ballar-intobins algoritmer, d.v.s. algoritmer där bollar agerar parallellt, som separata agenter. Detta problem introducerades av Adler et al., som visade att icke- adaptiva och symmetriska algoritmer inte på ett tillförlitligt sätt kan prestera bättre än en maximal bin belastning av  till (log log n/ log log log n) inom samma antal rundor. Vi presenterar en adaptiv symmetrisk algoritm som uppnår en bin belastning på två i logg * n + O(1) kommunikationsrundor med O(n) meddelanden totalt. Dessutom kan större sopor laster handlas i för mindre tids komplexiteter. Vi visar en matchande nedre gräns (1 − o(1)) logg * n om tids komplexiteten hos symmetriska algoritmer som garanterar små bin belastningar vid en asymptotiskt optimal meddelande komplexitet O(n). De väsentliga förutsättningarna för beviset är i) en gräns för O(n) för det totala antalet meddelanden som skickas av algoritmen och ii) anonymitet av bins, dvs. portnumrering av bollar är inte globalt konsekvent. För att visa att vår teknik ger verkligen snäva gränser, tillhandahåller vi för varje antagande en algoritm som bryter mot den, i sin tur uppnå en konstant maximal bin belastning i konstant tid. Som en ansökan tar vi upp följande problem. Med tanke på en helt ansluten graf av n noder, där varje nod måste skicka och ta emot upp till n meddelanden, och i varje runda varje nod kan skicka ett meddelande över varje länk, leverera alla meddelanden så snabbt som möjligt till sina destinationer. Vi ger en enkel och robust algoritm av tids komplexitet O(log * n) för denna uppgift och ger en generalisering till fallet där alla noder ursprungligen har godtyckliga uppsättningar av meddelanden. Genom att slutföra bilden ger vi en mindre praktisk, men asymptotiskt optimal algoritm som avslutas inom O(1) rundor. Alla dessa gränser håller med stor sannolikhet.
Slutligen, utan sådana begränsningar, kan en maximal bin belastning på 3 garanteras inom O(1) rundor REF.
Tight bounds for parallel randomized load balancing: extended abstract
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}