Massively parallel algorithms for sparse graphs

Abstract

Most real-life graphs are large and sparse, consisting of billions of nodes connected by billions of edges. Single-machine computation for such graphs is often slow and inefficient. The modern approach is to deploy a fleet of machines that work on a given graph problem in parallel. The Massively Parallel Computation (MPC) model captures the strengths and limitations of such parallel systems and is a widely accepted theoretical framework for analyzing modern parallel algorithms. This thesis considers fundamental graph problems for uniformly sparse graphs in the MPC model, focusing on memory-optimal solutions. Computation is performed on arbitrarily many machines simultaneously while using roughly the same amount of memory that is needed to store the input itself.

We resolve open problems and advance the state of the art by developing novel deterministic algorithms for graph problems such as connectivity, vertex coloring, maximal matching, and maximal independent set. Our focus is on uniformly sparse graphs, technically known as lowarboricity graphs. These graph families form the setting for most known lower bounds in MPC, and designing memory-optimal algorithms for them is notoriously difficult.

Algorithm complexity is measured in communication rounds and is typically expressed as a function of the total number of nodes n or the diameter of the graph D. We establish the first O(log D)-round algorithm for connectivity, as well as the first O(log log n)- and O(log D)-round algorithms for 3-coloring, maximal matching, and maximal independent set on forest graphs. We also show that strengthening the MPC model, by allowing adaptive queries to a distributed data store, enables a constant-round O(alpha)-coloring algorithm for graphs with bounded arboricity alpha.

One major technical contribution of this thesis is a novel graph exploration technique called balanced exponentiation, on which many of our results rely. This technique has been developed into a parameterized, standalone tool that allows nodes to explore surrounding sparse regions of the graph without prior knowledge of their location, while incurring minimal memory overhead.

Useimmat tosielämän verkot ovat suuria ja harvoja, koostuen miljardeista solmuista, joita yhdistävät miljardit kaaret. Yksittäisen tietokoneen suorittama laskenta tällaisille verkoille on usein hidasta ja tehotonta. Nykyaikainen lähestymistapa on käyttää useita tietokoneita ratkaisemaan annettua verkko-ongelmaa rinnakkain. Massiivisen rinnakkaislaskennan (MPC) -malli on vakiintunut teoreettinen viitekehys modernien rinnakkaisalgoritmien analysointiin, kuvaten rinnakkaisjärjestelmien vahvuuksia ja rajoituksia. Tämä väitöskirja tarkastelee perustavanlaatuisia ongelmia MPC-mallissa, keskittyen muistioptimaalisiin ratkaisuihin tasaisen harvoissa verkoissa. Laskenta suoritetaan samanaikaisesti mielivaltaisella määrällä koneita, käyttäen suunnilleen yhtä paljon muistia kuin itse syötteen tallentamiseen tarvitaan.

Ratkaisemme avoimia ongelmia ja parannamme alan aiempia huipputuloksia uusilla deterministisillä algoritmeilla yhtenäisyydelle, väritykselle, maksimaaliselle pariutukselle sekä maksimaaliselle riippumattomalle joukolle. Keskitymme tasaisen harvoihin verkkoihin, jotka tunnetaan teknisesti matalan puumaisuuden verkkoina. Suurin osa tunnetuista alarajoista MPCmallissa on osoitettu juuri näissä verkoissa ja muistioptimaalisten algoritmien suunnittelu niille on tunnetusti haastavaa.

Algoritmien kompleksisuus mitataan kommunikaatiokierrosten kokonaismääränä ja se ilmaistaan tyypillisesti solmujen määrän n tai verkon halkaisijan D funktiona. Kehitämme ensimmäisen O(log D)-kierroksisen algoritmin yhtenäisyydelle sekä ensimmäiset O(log log n)- ja O(log D)-kierroksiset algoritmit 3-väritykselle, maksimaaliselle pariutukselle ja maksimaaliselle riippumattomalle joukolle metsäverkoissa. Vahvistamalla MPC-mallia siten, että adaptiiviset kyselyt hajautettuun tietokantaan ovat sallittuja, kehitämme vakiokierroksisen O(alfa)-väritysalgoritmin verkoille, joiden puumaisuus alfa on vakio.

Yksi tämän väitöskirjan merkittävimmistä teknisistä kontribuutioista on uusi verkon kartoitusmenetelmä, nimeltään tasapainotettu eksponointi, johon monet väitöskirjan tulokset perustuvat. Menetelmä on jalostettu erilliseksi parametrisoiduksi työkaluksi, jonka avulla solmut voivat kartoittaa niitä ympäröiviä verkon harvoja alueita ilman ennakkotietoa niiden sijainnista, aiheuttamatta merkittävää muistikuormaa.