Motiverad av det ökande behovet av att förstå algoritmiska grunder för distribuerade storskaliga grafberäkningar, studerar vi ett antal grundläggande grafproblem i en meddelande-passing modell för distribuerade datorer där k ≥ 2 maskiner gemensamt utför beräkningar på grafer med n noder (vanligtvis n k). Inmatningskurvan antas inledningsvis vara slumpmässigt partitionerad bland k-maskinerna, en gemensam implementation i många verkliga system. Kommunikation är punkt-till-punkt, och målet är att minimera antalet kommunikationsrundor i beräkningen. Vårt huvudresultat är en (nästan) optimal distribuerad randomiserad algoritm för grafanslutning. Vår algoritm körs i Õ (n/k 2 ) rundor (Õ notation döljer en polylog(n) faktor och en additiv polylog(n) term). Detta förbättras över den mest kända gränsen av Õ (n/k ) [Klauck et al., SODA 2015] och är optimal (upp till en polylogaritmisk faktor) mot bakgrund av en befintlig nedre gräns på ∂(n/k 2 ). Vår förbättrade algoritm använder en massa tekniker, inklusive linjär grafskissering, som visar sig användbara i utformningen av effektiva distribuerade grafalgoritmer. Med hjälp av konnektivitetsalgoritmen som byggsten presenterar vi sedan snabbt randomiserade algoritmer för beräkning av minsta spännvidd, (ungefärliga) min-cuts, och för många grafverifieringsproblem. Alla dessa algoritmer tar Õ (n/k 2 ) rundor och är optimala upp till polylogaritmiska faktorer. Vi visar också en nästan matchande lägre gräns för ds (n/k 2 ) rundor för många grafverifiering problem genom att utnyttja lägre gränser i slumpmässig-partition kommunikation komplexitet.
Pandurangan m.fl. REF visade O(n/k 2 )-runda algoritmer i k-maskin modellen för anslutning, MST, ungefärlig min-cut, och andra grafverifieringsproblem.
Fast Distributed Algorithms for Connectivity and MST in Large Graphs
{'venue': 'TOPC', 'journal': None, 'mag_field_of_study': ['Computer Science']}