Detta dokument är centrerat på komplexiteten i grafproblemen i den välstuderade LOCAL-modellen av distribuerade datorer, som infördes av Linial [FOCS '87]. Det är allmänt känt att för många av de klassiska distribuerade graf problem (inklusive maximal oberoende uppsättning (MIS) och ( till + 1)-vertex färgning), är den randomiserade komplexiteten som mest polylogaritmisk i storleken n av nätverket, medan den bästa deterministiska komplexiteten är typiskt 2 O ( ε log n). Förståelse och potentiellt minska denna exponentiella gap anses vara en av de centrala långvariga öppna frågor inom området distribuerade grafalgoritmer. Vi undersöker problemet genom att införa ett komplext-teoretiskt ramverk som gör att vi kan belysa slumpmässighetens roll i LOCAL-modellen. Vi de ne SLOCAL modellen som en sekventiell version av LOCAL modellen. Vårt ramverk gör det möjligt för oss att bevisa fullständighet resultat med avseende på den klass av problem som kan lösas eektivt i SLOCAL-modellen, vilket innebär att om något av de fullständiga problemen kan lösas deterministiskt i poly log n rundor i LOCAL-modellen, kan vi deterministiskt lösa alla e e questic SLOCAL-problem (inklusive MIS och ( på + 1) färgning) i poly log n rundor i LOCAL-modellen. Kanske mest förvånande, visar vi att en ganska rudimentär utseende graf färg problemet är komplett i ovanstående betydelse: Färg noderna i en graf med färger röd och blå sådan att varje nod av tillräckligt stor polylogaritmisk grad har minst en granne av varje färg. Problemet medger en trivial noll-runda randomiserad lösning. Resultatet kan ses som att visa att det enda hindret för att få e cient determinstic algoritmer i LOCAL-modellen är en e cient algoritm till ungefär runda fraktionerade värden i heltalsvärden. Dessutom gör vårt formella ramverk också att vi kan utveckla polylogaritmisk tid randomiserade distribuerade algoritmer på ett enklare sätt. Som ett resultat, vi ger en polylog-tid distribuerad approximation system för godtyckligt distribuerad täckning och förpackning heltal linjära program.
I LOCAL-modellen beror en randomiserad (1 + ) - approximation i (logg n) O(1) rundor på REF.
On the complexity of local distributed graph problems
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}