Detta dokument tar upp den grundläggande familjen av lokala problem i distribuerade datorer, och undersöker den underliga klyftan mellan randomiserade och deterministiska lösningar under bandbreddsbegränsningar. Vårt huvudsakliga bidrag är att tillhandahålla verktyg för att avrandomisera lösningar på lokala problem, när n noderna bara kan skicka O(log n)-bit meddelanden i varje omgång av kommunikation. Vi kombinerar begränsat oberoende, som vi visar vara tillräckligt för vissa algoritmer, med metoden för villkorliga förväntningar och med ytterligare maskiner, för att få följande resultat. Våra tekniker ger en deterministisk maximal oberoende uppsättning (MIS) algoritm i CONGEST-modellen, där kommunikationsgrafen är identisk med ingångsgrafen, i O(D log 2 n) rundor, där D är diametern på grafen. Den mest kända körtiden i termer av n ensam är 2 O ( ε log n), som är super-polylogaritmiska, och kräver stora meddelanden. För CONGEST-modellen är den enda kända tidigare lösningen en färgbaserad O( på + log * n)-round-algoritm, där  till är den maximala graden i grafen. Såvitt vi vet är vår första deterministiska MIS-algoritm för CONGEST-modellen, som för D-polylogaritmiska värden endast är en polylogaritmisk faktor av jämfört med dess randomiserade motsvarigheter. På vägen till att erhålla ovanstående, visar vi att i den överbelastade Clique modellen, som tillåter all-till-alla kommunikation, det finns en deterministisk MIS algoritm som körs i O(log  på log n) rundor.När  på = O(n 1/3 ), den bundna förbättras till O (logga) och håller också för ( till + 1)-färgning. Dessutom konstruerar vi deterministiskt en (2k − 1)-spanner med O(kn 1+1/k log n) kanter i O(k log n) rundor. För jämförelse, i den strängare CONGEST modellen, den bästa deterministiska algoritmen för att konstruera en (2k − 1)-spanner med O(kn 1+1/k ) kanter körs i O(n)
Nyligen visade REF att Baswana-Sen-algoritmen kan derandomiseras i den överbelastade klickmodellen av kommunikation där varje par av noder (även icke-grannar i inmatningskurvan) kan byta O(log n) bitar per runda.
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}