Med tanke på ett distribuerat system av n bollar och n bins, hur jämnt kan vi fördela bollarna till bins, minimera kommunikation? Den snabbaste icke-adaptiva och symmetriska algoritmen för att uppnå en konstant maximal bin- belastning kräver rundor (log log n) och alla sådana algoritmer som körs för r  och O(1)- rundor ådrar sig en bin- belastning av  och/eller (log n/ log log log n) 1/r ). I detta arbete utforskar vi de grundläggande gränserna för det allmänna problemet. Vi presenterar en enkel adaptiv symmetrisk algoritm som uppnår en bin belastning på 2 i logg * n + O(1) kommunikationsrundor med O(n) meddelanden totalt. Vårt huvudsakliga resultat är dock en matchande nedre gräns (1 − o(1)) log * n om tids komplexiteten hos symmetriska algoritmer som garanterar små bin belastningar. 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 behöver inte vara 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. En längre sammanfattning av förarbetet publicerades på STOC 2011 [25] och motsvarande artikel har publicerats på arxiv [24].
Till exempel visar Lenzen och Wattenhofer REF att man kan uppnå en maximal belastning på 2 med hjälp av log * n + O(1) rundor av kommunikation, w.h.p.
Tight bounds for parallel randomized load balancing
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Mathematics', 'Engineering', 'Computer Science']}