Classifying local promise problems in directed cycles in the port numbering model

Thumbnail Image

Files

master_Lappi_Niilo_2025.pdf (1.46 MB)

URL

Journal Title

Journal ISSN

Volume Title

School of Science | Master's thesis
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

2025-07-31

Department

Major/Subject

Computer Science

Mcode

Degree programme

Master's Programme in Computer, Communication and Information Sciences

Language

en

Pages

44

Series

Abstract

Distributed computing is a field where interconnected computers collaborate. It has been studied, among others, through the computational Port Numbering model (PN model), where identical computer nodes each run the same algorithm and exchange messages with their neighbors in synchronized communication rounds. The nodes can perform unlimited computation between communication rounds. The number of rounds it takes for every node to halt processing is the running time of the algorithm. A connected research area is locally checkable labeling (LCL) problems, where a solution can be verified locally but not necessarily computed locally. Recently, LCL problems have been classified based on their locality in simple graph families, and this process has been automated. However, the fact that many LCL problems admit no solution in certain graphs is often implicitly ignored, obfuscating the classification. In this thesis, I initiate the systematic study of LCL promise problems, which are LCL problems with a promise that every input instance is graph-theoretically solvable. For example, the promise entails the 2-colorability of the input graph for a 2-coloring problem. I study the effects this promise has on the locality of LCL problems compared to the traditional promise-free setting. I classify LCL promise problems with inputs in directed cycles in the deterministic PN model. The classification is based on graph-theoretical solvability and locality under the promise of solvability. For problems with input alphabet Γ and output alphabet Σ, I present a complete classification of 50606 non-isomorphic problems, contained in the following cases: • |Γ| = 1 and 1 ≤ |Σ| ≤ 4, • |Γ| = 2 and 1 ≤ |Σ| ≤ 3, • |Γ| = 3 and 1 ≤ |Σ| ≤ 2, • |Γ| = 4 and 1 ≤ |Σ| ≤ 2. The classification surprisingly does not contain problems of super-constant locality, meaning every classified problem with graph-theoretically solvable problem instances either admits a constant-round PN algorithm or is impossible in the PN model. This raises a conjecture of the complete absence of problems in between.

Hajautettu laskenta on ala joka tutkii tietokoneiden yhteistyötä. Sitä on tutkittu laskennallisen porttinumerointimallin (PN-malli) avulla, jossa identtiset tietokonesolmut ajavat samaa algoritmia vaihtaen viestejä naapuriensa kanssa synkronoiduissa kommunikaatiokierroksissa. Solmut voivat suorittaa rajattomasti laskentaa kierrosten välillä, ja algoritmin ajoaika on kuluneiden kierrosten määrä kaikkien solmujen pysähdyttyä. Tähän liittyvä ala on paikallisesti tarkistettavat merkitsemisongelmat (LCL-ongelmat), joita ei välttämättä voida ratkaista paikallisesti, mutta ratkaisu voidaan tarkistaa paikallisesti. Hiljattain LCL-ongelmia on luokiteltu niiden paikallisuuden perusteella yksinkertaisissa verkkoperheissä, ja tämä prosessi on automatisoitu. Usein kuitenkin implisiittisesti jätetään huomiotta, että monet LCL-ongelmat eivät ole ratkaistavissa tietyissä verkoissa, mikä hämärtää luokittelua. Tässä työssä aloitan LCL-lupausongelmien järjestelmällisen tutkimuksen. Ne ovat LCL-ongelmia yhdistettynä lupaukseen, jonka mukaan syöte on verkkoteoreettisesti ratkaistavissa. Esimerkiksi 2-väritysongelmille lupaus sisältää syöteverkon 2-väritettävyyden. Tutkin tämän lupauksen vaikutuksia LCL-ongelmien paikallisuuteen verrattuna perinteiseen lupauksettomaan tapaukseen. Luokittelen syötteellisiä LCL-lupausongelmia suunnatuissa sykleissä, deterministisessä PN-mallissa. Luokittelu perustuu verkkoteoreettiseen ratkaistavuuteen ja paikallisuuteen ratkaistavuuslupauksen alla. Esitän täydellisen luokittelun 50606 epäisomorfisesta ongelmasta, joissa syöteaakkostolle Γ ja tulosteaakkostolle Σ pätee: • |Γ| = 1 ja 1 ≤ |Σ| ≤ 4, • |Γ| = 2 ja 1 ≤ |Σ| ≤ 3, • |Γ| = 3 ja 1 ≤ |Σ| ≤ 2, tai • |Γ| = 4 ja 1 ≤ |Σ| ≤ 2. Yllättäen vakioaikaista vaikeammat ongelmat puuttuvat luokittelusta, eli jokainen ongelma jolla on verkkoteoreettisesti ratkaistavissa olevia instansseja, on joko ratkaistavissa vakiokierroksisella PN-algoritmilla tai on mahdoton ratkaista PN-mallissa. Tämän vuoksi esitän konjektuurin, jonka mukaan ongelmia ei ole luokkien välissä.

Description

Supervisor

Suomela, Jukka

Thesis advisor

Lievonen, Henrik

Keywords

distributed algorithms, locally checkable labeling problems, promise problems, port numbering model, LOCAL model, graph problems

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202508196430

Collections

[dipl] Perustieteiden korkeakoulu / SCI