Automated classification of distributed graph problems

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Aleksandr Tereshchenko
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
The 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.
Suomela, Jukka
Thesis advisor
Suomela, Jukka
distributed algorithms, distributed computing, locally checkable labeling problems, round elimination, graph algorithms
Other note