Abstrakt. Vi föreslår en enkel distribuerad algoritm för att balansera odelbara polletter på grafer. Algoritmen är helt deterministisk, även om den försöker imitera (och förbättra) en slumpmässig algoritm genom att hålla de ackumulerade avrundningsfelen så små som möjligt. Vår nya algoritm är förvånansvärt nära den idealiserade processen (där polletterna är delbara) på viktiga nätverkstopologier. På d-dimensionella torusgrafer med n noder avviker den från den idealiserade processen endast genom en additiv konstant. I motsats till detta kan den randomiserade avrundningsmetoden för Friedrich och Sauerwald [11] avvika upp till (polylog(n)) och den deterministiska algoritmen för Rabani, Sinclair och Wanka [32] har en avvikelse på (n 1/d ). Detta gör vår kvasirandomalgoritm till den första kända algoritmen för denna inställning som är optimal både i tid och uppnådd jämnhet. Vi visar vidare att även på hyperkuben har vår algoritm en mindre avvikelse från den idealiserade processen än de tidigare algoritmerna. 1. Vad är det för fel på dig? Inledning. Belastningsbalansering är en viktig förutsättning för ett effektivt utnyttjande av beräkningsresurserna i parallella och distribuerade system. Syftet är att omfördela lasten så att varje nod i slutet har ungefär samma last. Belastning balansering problem har olika applikationer, t.ex., för schemaläggning [36], routing [5], och numerisk beräkning [37, 38]. Vanligtvis, last balansera algoritmer iterativt byta belastning längs kanterna på en oriktad ansluten graf. I det naturliga diffusionsparadigmet kan en godtycklig mängd last skickas längs varje kant i varje steg [30, 32]. För idealiserade fall av delbar belastning, en populär diffusion algoritm är den första ordningen-system av Subramanian och Scherson [35] vars konvergenshastighet är ganska väl fångad i termer av spektral gap [26]. För många tillämpningar kan antagandet om delbar belastning dock vara ogiltigt. Därför anser vi att det diskreta fallet där lasten endast kan brytas ned i odelbara enhet-storlek tokens. Det är en mycket naturlig fråga genom hur mycket detta integritet antagande minskar effektiviteten i lastbalansering. Faktum är att hitta en exakt kvantitativ relation mellan det diskreta och det idealiserade fallet är ett öppet problem som många författare, t.ex. [9, 11, 14, 15, 27, 30, 32, 35]. En enkel metod för att approximera den idealiserade processen analyserades av Rabani, Sinclair och Wanka [32]. Deras tillvägagångssätt (som vi kommer att kalla "RSW-algoritm") är att avrunda ner det fraktionerade flödet av den idealiserade processen. De introducerar en mycket användbar parameter av grafen som kallas lokal divergens och bevisar att det ger snäva övre gränser på avvikelsen mellan den idealiserade processen och deras diskreta process. En nackdel med RSW-algoritmen är dock att den kan hamna i ganska obalanserade stater (jfr. Förslag 6. 1). För att övervinna detta problem analyserade Friedrich och Sauerwald en ny algoritm baserad på randomiserad avrundning [11]. På många grafer, denna algoritm approximerar det idealiserade fallet mycket bättre än tillvägagångssättet att alltid avrundning ner av RSW-algoritmen. En naturlig fråga är om denna randomiserade algoritm kan avrandomiseras utan att offra på dess prestanda. För de grafer som behandlas i detta arbete besvarar vi denna fråga till det positiva. Vi introducerar en kvasirandom lastbalansalgoritm som avrundar uppåt eller nedåt deterministiskt så att de ackumulerade avrundningsfelen på varje kant minimeras. Vårt tillvägagångssätt följer begreppet kvasirandomness som det deterministiskt imiterar det förväntade beteendet hos dess slumpmässiga motsvarighet.
Författarna till Ref. I REF föreslås en deterministisk lastbalanseringsprocess där den kontinuerliga belastning som överförs längs varje kant avrundas uppåt eller nedåt deterministiskt, så att summan av avrundningsfelen på varje kant upp till ett godtyckligt steg t begränsas av en konstant.
Quasirandom Load Balancing
{'venue': 'SIAM Journal on Computing, Vol. 41, No. 4, pp. 747-771, 2012', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}