Automated classification of distributed graph problems

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorSuomela, Jukka
dc.contributor.authorTereshchenko, Aleksandr
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.supervisorSuomela, Jukka
dc.date.accessioned2021-05-23T17:12:16Z
dc.date.available2021-05-23T17:12:16Z
dc.date.issued2021-05-17
dc.description.abstractThe field of distributed computing and distributed algorithms is a well-established and quickly developing area of theoretical computer science. Similar to the study of traditional centralized algorithms, many researchers are particularly interested in understanding the complexity of distributed problems. In particular, over the last decade, the research community has had a series of breakthroughs in understanding the complexity landscape of locally checkable labeling problems (LCLs), which is one of the most significant and well-studied problem families in distributed computing. As more and more individual LCL problems have been understood, people started to investigate whether it was possible to automate the process. This led to a discovery of a whole range of so-called meta-algorithms. These are centralized algorithms that take a distributed LCL problem as their input and return information about its complexity as an output. Furthermore, many of the meta-algorithms turned out to be practical and were subsequently implemented as computer programs that can tell something useful about the complexities of LCL problems. The problem, however, is that these meta-algorithms are not currently used by the research community. This causes the scholars to solve the same problems that have been solved before. The reason for the failure to adopt the meta-algorithms is the fact that their implementations use different formalisms, which makes it inconvenient to use them in everyday work. The goal of the thesis is to resolve this problem and develop a solution that would unify the numerous meta-algorithms making it possible to benefit from them all while using only a single tool. In this work, I have developed a unified system that encapsulates most of the existing meta-algorithms, providing a unified interface to its users. I also implemented a Web interface to make the tool even more accessible for the community. Furthermore, I critically analyze the solution and propose ideas for its further improvement.en
dc.format.extent76
dc.format.mimetypeapplication/pdfen
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/107680
dc.identifier.urnURN:NBN:fi:aalto-202105236941
dc.language.isoenen
dc.programmeMaster's Programme in Computer, Communication and Information Sciencesfi
dc.programme.majorComputer Sciencefi
dc.programme.mcodeSCI3042fi
dc.subject.keyworddistributed algorithmsen
dc.subject.keyworddistributed computingen
dc.subject.keywordlocally checkable labeling problemsen
dc.subject.keywordround eliminationen
dc.subject.keywordgraph algorithmsen
dc.titleAutomated classification of distributed graph problemsen
dc.typeG2 Pro gradu, diplomityöfi
dc.type.ontasotMaster's thesisen
dc.type.ontasotDiplomityöfi
local.aalto.electroniconlyyes
local.aalto.openaccessyes

Files

Original bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
master_Tereshchenko_Aleksandr_2021.pdf
Size:
1.2 MB
Format:
Adobe Portable Document Format