Motiverade av det ökande behovet av snabb distribuerad bearbetning av storskaliga grafer som webbgrafen och olika sociala nätverk, studerar vi ett antal grundläggande grafproblem i meddelande-passing modellen, där vi har k maskiner som gemensamt utför beräkningar på en godtycklig n-node (vanligtvis n  på k) ingångsgraf. Grafen antas vara slumpmässigt partitionerad bland k ≥ 2 maskiner (en vanlig implementation i många verkliga system). Kommunikationen är punkt-till-punkt, och målet är att minimera tids komplexiteten, dvs. antalet kommunikationsrundor, för att lösa olika grundläggande grafproblem. Vi presenterar lägre gränser som kvantifierar de grundläggande tidsbegränsningarna för att distributivt lösa grafproblem. Vi visar först en nedre gräns av  och (n/k) rundor för beräkning av ett spanning träd (ST) av inmatningskurvan. Detta resultat innebär också samma gräns för andra grundläggande problem som beräkning av ett minsta spännträd (MST), bredd först träd (BFS) och kortaste stigar träd (SPT). Vi visar även en lägre gräns för anslutning, ST-verifiering och andra * Division of Mathematics Sciences, Nanyang Technological University, Singapore 637371 & Centre for Quantum Technologies, Singapore 117543. E-post: hklauck@gmail.com. Detta arbete finansieras av Singapores utbildningsministerium (delvis genom Academic Research Fund Tier 3 MOE2012-T3-1-009) och av Singapores nationella forskningsstiftelse. † KTH Royal Institute of Technology, Sverige, och University of Vienna, Österrike E-post: danupon@gmail.com. Arbetet har utförts vid ICERM, Brown University, USA och Nanyang Technological University i Singapore. För att komplettera våra nedre gränser, ger vi också algoritmer för olika grundläggande grafproblem, t.ex. PageRank, MST, konnektivitet, ST-verifiering, kortaste vägar, skär, skiftnycklar, täcker problem, tätaste subgraf, subgraph isomorfism, hitta trianglar, etc. Vi visar att problem som PageRank, MST, konnektivitet och graftäckning kan lösas i Õ(n/k) tid (notationen Õ döljer polylog(n) faktorer och en additiv polylog(n) term); detta visar att man kan uppnå nästan linjär (i k) hastighet, medan för kortaste vägar, presenterar vi algoritmer som körs i Õ (n/ н k) tid (för (1 + )-faktor approximation) och i Õ(n/k) tid (för O(log n)-faktor approximation) respektive. Våra resultat är ett steg mot att förstå komplexiteten i att distributivt lösa storskaliga grafproblem.
I denna modell visar REF en låg gräns för att beräkna kortaste sökvägar, där k är antalet maskiner.
Distributed Computation of Large-scale Graph Problems
{'venue': None, 'journal': 'arXiv: Distributed, Parallel, and Cluster Computing', 'mag_field_of_study': ['Computer Science']}