Locally Checkable Labeling Problems in Rooted Trees in the Online-LOCAL Model of Computation
Loading...
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
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.
Author
Date
2022-03-21
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
59
Series
Abstract
There are many ways to classify algorithms. Online algorithms, for example, are algorithms that have to be able to handle input one element at a time. Offline algorithms, on the other hand, have access to the whole input. In the case of online graph algorithms, the structure of the underlying graph is fixed. The graph is revealed to the algorithm one node at a time. When a node is revealed, the algorithm has to decide its output for that node, and it cannot change its decision later. Another way to classify algorithms is to divide them into centralized and distributed algorithms. In the case of graph algorithms, a centralized algorithm is a completely separate entity from the graph. When the nodes (or edges) of the graph are active parties in the execution of the algorithm, the algorithm is called a distributed algorithm. One commonly used model of distributed computation is the LOCAL model. In the LOCAL model, all nodes are computing their own part of the result in parallel. The nodes only see their own local neighborhood and need to base their decision only on this local view. In this thesis, I introduce the online-LOCAL model, which combines the power of online graph algorithms and LOCAL algorithms. Like online graph algorithms, online-LOCAL algorithms need to react to nodes being revealed one at a time. Unlike online graph algorithms, online-LOCAL algorithms also get to see the local neighborhood around the nodes before needing to make their decisions. The online-LOCAL model is a very strong model of computation. In general, there are problems that are trivial in the online-LOCAL model, but difficult to solve with online graph algorithms and LOCAL algorithms. In this thesis, I restrict my attention to the class of problems known as locally checkable labeling problems. These are a broad class of problems for which a solution is valid if it looks valid in all local neighborhoods. In particular, I show that for locally checkable labeling problems in rooted regular trees, the online-LOCAL model is approximately as powerful as the LOCAL model.Algoritmeja voidaan luokitella monin eri perustein. Esimerkiksi online-algoritmit ovat algoritmeja, joiden pitää pystyä käsittelemään syötettä alkio kerrallaan. Niiden vastakohta on offline-algoritmit, joilla on pääsy koko syötteeseen. Online-verkkoalgoritmien tapauksessa verkon rakenne on kiinnitetty, mutta verkko paljastetaan algoritmille solmu kerrallaan. Solmun paljastuessa paljastuvat myös siitä lähtevät kaaret aiemmin paljastettuihin solmuihin. Algoritmin täytyy välittömästi päättää tuloste paljastetulle solmulle, eikä se voi enää myöhemmin muuttaa päätöstään. Toinen tapa luokitella algoritmeja on jakaa ne hajautettuihin ja keskitettyihin algoritmeihin. Verkkoalgoritmien tapauksessa keskitetty algoritmi on verkosta irrallinen toimija. Jos sen sijaan verkon solmut (tai kaaret) ovat aktiivisia toimijoita algoritmin suorituksessa, on kyseessä hajautettu algoritmi. Yksi paljon tutkittu hajautettujen algoritmien malli on LOCAL-malli. LOCAL-mallissa jokainen verkon solmu laskee samanaikaisesti oman osansa ratkaisusta. LOCAL-mallissa algoritmi näkee vain solmun välittömän lähiympäristön, jonka pohjalta algoritmin täytyy päättää ratkaisu solmulle. Tässä työssä esittelen online-LOCAL-mallin, joka yhdistää online-verkko- ja LOCAL-algoritmien tehokkuuden. Online-algoritmien tavoin online-LOCAL-algo\-ritmien täytyy pystyä ratkaisemaan ongelma solmu kerrallaan. Toisin kuin online-verkko\-algoritmit, online-LOCAL-algoritmit näkevät myös solmun lähiympäristön ennen kuin niiden pitää päättää tuloste solmulle. Online-LOCAL-malli on erittäin vahva laskennan malli. On olemassa ongelmia, jotka ratkeavat helposti online-LOCAL-mallissa, mutta joita ei pysty ratkaisemaan online- eikä LOCAL-algoritmeilla. Yleensä LOCAL-mallia tutkittaessa rajoittaudutaan kuitenkin paikallisesti tarkistettaviin merkitsemisongelmiin. Ne ovat verkko-ongelmia, joille ratkaisu on kelvollinen, mikäli se näyttää kelvolliselta kaikkien solmujen lähiympäristöissä. Tässä työssä osoitan, että online-LOCAL-malli on vain hieman vahvempi kuin LOCAL-malli, kun tarkastelu rajoitetaan paikallisesti tarkistettaviin merkitsemisongelmiin säännöllisissä juurellisissa puissa.Description
Supervisor
Suomela, JukkaThesis advisor
Melnyk, DaryaKeywords
online graph algorithms, distributed algorithms, locally checkable labeling problems, LOCAL model, online-LOCAL model
