Public defence in Computer Science, M.Sc. Mélanie Cambus

Title of the thesis: Distributed computing in dynamic and faulty networks: distributed graph algorithms and multidimensional agreement 

Thesis defender: Mélanie Cambus
Opponent: Professor John Augustine, Indian Institute of Technology Madras (IIT), India
Custos: Assistant Professor Jara Uitto, Aalto University School of Science

Distributed computing enables multiple devices to solve complex problems collaboratively by breaking work across a network of computers without a central controller. Graph model such networks as nodes (computers) that are interconnected by edges (connections), allowing the design of efficient solutions for large-scale tasks. 

In the first part of this thesis, we address two critical challenges in very large networks. The first one is correlation clustering, a fundamental question in data mining, where one aims at grouping similar data points and separating dissimilar ones. We designed a single-pass algorithm that computes a (3+eps)-approximation of an optimum clustering in the semi-streaming model. The second one is the 2-ruling set problem which is fundamental for data organization and network management. It consists in finding a subset of independent nodes where every node outside has at least two neighbors within it, ensuring connectivity during network disruptions. We designed an algorithm that computes a 2-ruling set in a constant number of rounds in Congested Clique and linear space MPC, which also adapts into a single-pass semi-streaming algorithm. 

The second part of the thesis addresses the critical issue of multidimensional approximate agreement in faulty networks, consisting in approximately agreeing on a common vector even when some devices act maliciously or disconnect. In many real-world systems, some computers in a network may behave unpredictably or adversarially. We propose a new measure of approximation for fault-tolerant algorithms and study the trade-off between approximation of aggregation vectors and known validity conditions commonly used in the context of fault-tolerant algorithms. We also propose new algorithms that theoretically optimize this trade-off for different aggregation vectors and give very promising results when used for different federated learning models. 

The results of this study have broad implications for a wide range of fields, including data analysis, network management, and fault-tolerant systems. By improving the efficiency, scalability and robustness of distributed graph algorithms, this research offers scalable solutions for large datasets and enhances the reliability of models trained in a distributed manner.

Thesis available for public display 7 days prior to the defence at Aaltodoc.