Abstract-Många moderna parallella system, såsom MapReduce, Hadoop och Spark, kan modelleras väl av MPC-modellen. MPC modellen fångar väl grovkornig beräkning på stora data - data distribueras till processorer, som var och en har en sublineär (i indata) mängd minne och vi växlar mellan rundor av beräkning och rundor av kommunikation, där varje maskin kan kommunicera en mängd data så stor som storleken på sitt minne. Denna modell är starkare än den klassiska PRAM-modellen, och det är en spännande fråga att designa algoritmer vars körtid är mindre än i PRAM-modellen. Ett grundläggande grafproblem är konnektivitet. På en oriktad graf med n noder och m-kanter har O(log n) runda anslutningsalgoritmer varit kända i över 35 år. Men inga algoritmer med bättre komplexa gränser var kända. I detta arbete ger vi fullt skalbara, snabbare algoritmer för anslutningsproblem, genom att parameterisera tids komplexiteten som en funktion av diametern på grafen. Vårt huvudsakliga resultat är en O(log D log log m/n n) tid konnektivitetsalgoritm för diameter-D grafer, med hjälp av  till(m) totalt minne. Om vår algoritm kan använda mer minne, kan det sluta i färre rundor, och det finns ingen lägre gräns på minnet per processor. Vi utökar våra resultat till relaterade grafproblem som t.ex. att spänna skog, hitta en DFS-sekvens, exakt/ungefär minsta spännviddsskog och flaskhalsspannskog. Vi visar också att uppnå liknande gränser för nåbarhet i riktade grafer skulle innebära snabbare booleska matris multiplikationsalgoritmer. Vi introducerar flera nya algoritmiska idéer. Vi beskriver en allmän teknik som kallas dubbel exponentiell hastighet problemstorlek minskning vilket ungefär innebär att om vi kan använda totalt minne N för att minska ett problem från storlek n till n/k, för k = (N/n).(1) i en fas, då kan vi lösa problemet i O (log log N/n n) faser. För att uppnå denna snabba minskning för grafanslutning använder vi en flerstegsalgoritm. Ett viktigt steg är ett noggrant konstruerat trunkerat program där varje nod sänder ut grannen på ett sätt som begränsar storleken på den resulterande grannen. Ett annat viktigt steg är slumpmässig ledare kontraktion, där vi väljer en mindre uppsättning ledare än många tidigare verk gör.
Även om vi inte studerar MPC-modellen i detta dokument vill vi lyfta fram Andonis senaste arbete, etc. REF som ger en randomiserad stegalgoritm för O(log D log log m/n n) i MPC för anslutna komponenter.
Parallel Graph Connectivity in Log Diameter Rounds
{'venue': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}