Distributed Symmetry Breaking on Power Graphs via Sparsification

Loading...
Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis

Date

2023-06-12

Department

Major/Subject

Computer Science

Mcode

SCI3042

Degree programme

Master’s Programme in Computer, Communication and Information Sciences

Language

en

Pages

72+6

Series

Abstract

Symmetry breaking is a central theme in distributed graph algorithms. Classical symmetry breaking problems include maximal independent set (MIS), coloring and maximal matching. To compute a solution, nodes of the network must break their initial symmetry to take on different roles in the output. For instance, the maximal independent set problem requires nodes to select a subset of non-adjacent nodes, such that all excluded nodes have at least one neighbor in the set. We work in the CONGEST model of distributed computing, where the communication network is abstracted as a graph G. In CONGEST, nodes communicate with each other in synchronous rounds along the edges of the graph with O(log n)-bit messages. Local computation is free, while time is measured in the number of rounds. Classically, the problem instance is assumed to be identical to the communication network. This thesis considers symmetry breaking problems on power graphs G^k, k ≥ 1, where nodes are connected if their distance is at most k in G. The main contribution is a deterministic polylogarithmic-time algorithm for computing k-ruling sets of G^k. A beta-ruling set is a relaxation of the MIS problem, where the distance to the set is at most beta for all nodes, instead of 1. For k > 1, our algorithm improves the runtime exponentially compared to any previously known solutions. For randomized algorithms, we show that a maximal independent set of G^k can be computed in essentially the same time as an MIS of G. The second part of this thesis revisit the shattering framework [BEPS JACM'16], used to obtain the state-of-the-art MIS algorithms for G in CONGEST [Ghaffari SODA'19] and the LOCAL models [Ghaffari SODA'16]. We present novel approaches for the post-shattering phase, offering algorithmically and analytically simpler solutions while maintaining the same runtime as existing approaches.

Symmetrian murtaminen on keskeinen teema hajautetussa verkkolaskennassa. Ongelmia, joissa tarvitaan symmetrian murtamista ovat esimerkiksi maksimaalinen riippumaton joukko (MIS), väritys ja maksimaalinen paritus. Ongelman ratkaisussa keskenään samanlaiset solmut valitsevat eri rooleja, eli niiden täytyy murtaa symmetriaa. Esimerkiksi MIS on solmujen osajoukko, johon ei kuulu yhtään vierekkäistä solmua, mutta jossa jokaisella joukkoon kuulumattomalla solmulla on ainakin yksi naapuri. Työssä käytetään hajautetun laskennan CONGEST-mallia, jossa tietokoneiden verkkoa mallinnetaan graafina G. Verkon n solmua ovat prosessoreita, joilla on uniikki O(log n)-bittinen tunniste. Solmut kommunikoivat keskenään synkronoiduissa kierroksissa verkon kaaria pitkin. CONGEST-mallissa viestien koko on korkeintaan O(log n) bittiä. Prosessorien sisäinen laskenta on rajaamatonta. Algoritmin kompleksisuus mitataan käytettyjen kommunikaatiokierrosten määränä. Tyypillisesti CONGEST-mallissa annettu verkko-ongelma ratkaistaan identtisellä kommunikaatioverkolla. Tässä työssä ongelman verkko on kommunikaatioverkon potenssi G^k, jossa kaksi solmua on naapureita, jos niiden etäisyys G:ssä on korkeintaan k. Työn päätulos on deterministinen polylog n-aikainen algoritmi, joka laskee beta-hallitsevan joukon G^k:lle. Hallitseva joukko (ruling set) on riippumaton joukko, joka ei ole täysin maksimaalinen: etäisyys joukkoon on korkeintaan beta, toisin kuin yksi MIS:n tapauksessa. Tulos on eksponentiaalinen parannus edellisistä algoritmeista tähän ongelmaan. Toisena tuloksena näytän, että G^k:n maksimaalisen riippumatoman joukon laskemisen kompleksisuus on satunnaisalgoritmeille olennaisesti sama kuin alkuperäiselle verkolle G. Viimeinen kontribuutio liittyy hajautetun verkkolaskennan pirstoutumistekniikkaan (shattering technique) [BEPS JACM'16]. Tähän tekniikkaan perustuvat nopeimmat satunnaistetut MIS-algoritmit CONGEST- ja LOCAL-malleissa [Ghaffari SODA'19, Ghaffari SODA'16]. Esitän uusia ratkaisuja verkon pirstoutumisen jälkeiseen vaiheeseen. Ratkaisut ovat algoritmisesti ja analyyttisesti yksinkertaisempia ja niiden kompleksisuus on sama.

Description

Supervisor

Uitto, Jara

Thesis advisor

Maus, Yannic

Keywords

distributed algorithms, computational complexity theory, CONGEST model, independent set, ruling set, sparsification

Other note

Citation