aalto1 untyped-item.component.html
Distributed computing in dynamic and faulty networks: distributed graph algorithms and multidimensional agreement
Loading...
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Doctoral thesis (article-based)
| Defence date: 2025-10-02
Electronic archive copy is available via Aalto Thesis Database.
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
Major/Subject
Mcode
Degree programme
Language
en
Pages
72 + app. 117
Series
Aalto University publication series Doctoral Theses, 158/2025
Abstract
The study of distributed graph algorithms is central in both theoretical and applied computer science research, from solving large-scale graph problems via parallel computation models to designing fault-tolerant protocols in networks. Graphs can be dataset abstractions or even representations of communication topologies in computer networks.
A graph algorithm is a set of instructions ran by a computer where the goal is to solve a problem on a graph. When the algorithm is distributed, the set of instructions runs simultaneously on each computer of a network, producing a global outcome. Electing a leader or finding a shortest path are problems that often arise when the graph is an abstraction of the communication network in between computers. On the other hand, finding an independent set or computing a clustering of a graph are problems that do not necessarily impose the use of distributed graph algorithms; however, when the graphs studied are very large, using distributed algorithms provides scalability.
In this thesis, we propose distributed graph algorithms in both of those settings. We first designed distributed algorithms for solving the 2-ruling set problem and the correlation clustering problem on very large graphs, using parallel and dynamic computation models and the classic randomized greedy MIS algorithm. We then designed and analyzed algorithms for agreement in faulty networks, where the problem is simply for computers in a basic network to agree, when some computers in the network can have adversarial behavior.
Description
Supervising professor
Uitto, Jara, Asst. Prof., Aalto University, Department of Computer Science FinlandOther note
Parts
- [Publication 1]: Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, Jara Uitto. A (3 + ε))-Approximate Correlation Clustering Algorithm in Dynamic Streams. TheoretiCS, Volume 4, Article 6, 1-19, February 2025.
DOI: 10.1137/1.9781611977912.101 View at publisher
- [Publication 2]: Mélanie Cambus, Fabian Kuhn, Shreyas Pai, Jara Uitto. Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem. In 37th International Symposium on Distributed Computing (DISC), Volume 281, pp. 11:1-11:12, October 2023.
Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202311297016DOI: 10.4230/LIPIcs.DISC.2023.11 View at publisher
- [Publication 3]: Mélanie Cambus, Darya Melnyk. Improved Solutions for Multidimensional Approximate Agreement via Centroid Computation. Submitted to a conference, February 2025.
DOI: 10.48550/arXiv.2306.12741 View at publisher
- [Publication 4]: Mélanie Cambus, Darya Melnyk, Tijana Milentijevi´c, Stefan Schmid. Centroid Approximation for Byzantine-Tolerant Federated Learning. Submitted to a conference, February 2025
- [Publication 5]: Mélanie Cambus, Darya Melnyk, Tijana Milentijevi´c, Stefan Schmid. Approximate Agreement Algorithms for Byzantine Collaborative Learning. Submitted to a conference, February 2025.
DOI: 10.1145/3694906.3743343 View at publisher