Vi ser problemet med lastbalansering i ett ringnät. Vi presenterar en analys av följande lokala algoritm. I varje steg undersöker varje rings nod antalet polletter vid sin medurs granne och skickar ett tecken till grannen om grannen har färre polletter. Vi visar att i en synkron modell, för varje initial token distribution b, algoritmen konvergerar till en helt balanserad fördelning inom 4OPT(b) + n steg, där OPT(b) är den tid som tas av den optimala centraliserade algoritmen för att balansera b helt. Vårt huvudresultat är en analys av algoritmen i en asynkron modell där lokala beräkningar och meddelanden godtyckligt kan försenas, under förutsättning att varje meddelande slutligen levereras och varje beräkning slutligen utförs. Genom att generalisera vår analys för synkrona modellen, visar vi att för varje initial token distribution b, algoritmen konvergerar till en helt balanserad distribution inom 8OPT (b) + 2n rundor, där en runda är en minimal sekvens av steg där varje komponent i nätverket är schemalagd minst en gång. Vi visar också att för varje initial token distribution, meddelandet komplexitet av algoritmen är asymptotiskt optimal bland alla algoritmer som flyttar polletter i medsols riktning.
En statisk belastningsbalansering för både synkrona och asynkrona ringnät behandlas i REF.
Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings
{'venue': 'Theo. Comp. Sci', 'journal': None, 'mag_field_of_study': ['Computer Science']}