Distributed computing in dynamic and faulty networks: distributed graph algorithms and multidimensional agreement

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.