Designing and finding very fast distributed algorithms for bounded-degree graphs

Thumbnail Image

Files

isbn9789526420776.pdf (565.01 KB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Doctoral thesis (article-based) | Defence date: 2024-10-25
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

2024

Department

Tietotekniikan laitos
Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

54 + app. 98

Series

Aalto University publication series DOCTORAL THESES, 219/2024

Abstract

Distributed computing studies models where computation is split between multiple interconnected entities which can communicate with each other to achieve a common goal. In this thesis we look at the setting where the communication network is sparse, i.e., it has a bounded degree. We first study a family of problems that can be characterized by a fact that their solutions can be locally checked for correctness. This rich family is called locally checkable labeling (LCL) problems and contains, for example, the problems of computing proper colorings, maximal independent set, maximal matching and orientation problems. The aim is to completely characterize these LCL problems in a given network topology and be able to automatically synthesize an asymptotically optimal algorithm given any LCL problem. We have achieved a complete characterization and synthesis for the following graph families: paths, cycles and regular rooted trees and a partial characterization for regular undirected trees. The results are complemented by unified implementations of all classifiers for asymptotic round complexity. Some of the results are using a newly discovered connection to automata theory while others use a novel concept of certificates of solvability. In the second part of the thesis we focus on a specific problem of sparse matrix multiplication in a setting of low-bandwidth communication. We show that in the case of uniformly sparse matrices where each row and column has at most d non-zeroes we can break the quadratic barrier with respect to d and obtain a faster algorithm. One of the techniques used is to iteratively find regions that are locally dense and use more efficient dense multiplication algorithms for computing those parts.

Description

Supervising professor

Suomela, Jukka, Assoc. Prof., Aalto University, Department of Computer Science, Finland

Thesis advisor

Suomela, Jukka, Assoc. Prof., Aalto University, Department of Computer Science, Finland

Keywords

distributed algorithms, locally checkable labeling, matrix multiplication, locality, distributed computational complexity, algorithm synthesis, congested clique, low-bandwidth model

Other note

Parts

  • [Publication 1]: Yi-Jun Chang, Jan Studen´y, Jukka Suomela. Distributed graph problems through an automata-theoretic lens. Theoretical Computer Science, 951 113710, January 2023.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202303152438
    DOI: 10.1016/j.tcs.2023.113710 View at publisher
  • [Publication 2]: Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studen´y, Jukka Suomela, Aleksandr Tereshchenko. Locally checkable problems in rooted trees. Distributed Computing, 36(3) 277–311, September 2023.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202308114717
    DOI: 10.1007/s00446-022-00435-9 View at publisher
  • [Publication 3]: Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studen´y, Jukka Suomela. Efficient classification of locally checkable problems in regular trees. 36th International Symposium on Distributed Computing, DISC 2022, October 25–27, 2022, Augusta, Georgia, USA, 246 8:1–8:19, October 2022.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202211096452
    DOI: 10.4230/LIPIcs.DISC.2022.8 View at publisher
  • [Publication 4]: Chetan Gupta, Juho Hirvonen, Janne H Korhonen, Jan Studen´y, Jukka Suomela. Sparse Matrix Multiplication in the Low-Bandwidth Model. SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11–14, 2022, 435–444, July 2022.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202209075405
    DOI: 10.1145/3490148.3538575 View at publisher

Citation

Permanent link to this item

https://urn.fi/URN:ISBN:978-952-64-2077-6

Collections

[diss] Perustieteiden korkeakoulu / SCI