Massively parallel algorithms for sparse graphs

Thumbnail Image

Files

isbn9789526430812.pdf (2.02 MB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2026-04-10
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2026

Department

Tietotekniikan laitos
Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

70 + app. 105

Series

Aalto University publication series Doctoral Theses, 82/2026

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.

Description

Supervising professor

Uitto, Jara, Assist. Prof., Aalto University, Department of Computer Science, Finland

Keywords

massively parallel computation model, uniformly sparse graphs, connectivity, graph coloring, maximal matching, maximal independent set, massiivisen rinnakkaislaskennan malli, tasaisen harvat verkot, yhtenäisyys, verkon väritys, maksimaalinen pariutus, maksimaalinen riippumaton joukko

Other note

Parts

  • [Publication 1]: Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential Speedup Over Locality in MPC with Optimal Memory. In International Symposium on Distributed Computing (DISC) 2022 (also in Journal of Distributed Computing, February 2025), Volume 246, 9:1-9:21, Augusta, USA, October 2022.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202212076781
    DOI: 10.4230/LIPIcs.DISC.2022.9 View at publisher
  • [Publication 2]: Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Optimal Deterministic Massively Parallel Connectivity on Forests. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2023, pages 2589-2631, Florence, Italy, January 2023.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202312117182
    DOI: 10.1137/1.9781611977554.ch99 View at publisher
  • [Publication 3]: Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto. Conditionally Optimal Parallel Coloring of Forests. In International Symposium on Distributed Computing (DISC) 2023, Volume 281, 23:1-23:20, L’Aquila, Italy, October 2023.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202311296980
    DOI: 10.4230/LIPIcs.DISC.2023.23 View at publisher
  • [Publication 4]: Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto. Adaptive Massively Parallel Coloring in Sparse Graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 2024, pages 508-518, Nantes, France, June 2024.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202408285979
    DOI: 10.1145/3662158.3662821 View at publisher

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-64-3081-2

Collections

[diss] Perustieteiden korkeakoulu / SCI