Thesis Defense: Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks

Networks can change over time. Whether it is the Facebook network, where 'friendships' emerge or end, the internet, where computers connect or disconnect from the network, or the train network, where new lines can be created or canceled. This creates specific challenges for algorithms designed to either run or manage these 'dynamic' networks.

A distributed algorithm is an algorithm that runs on the network. Think of the internet: for computers to communicate through this network, the algorithm should be installed on both computers, and both computers won't necessarily have access to the same information. If the network is unstable, or is simply dynamic, the communication between them can drop at any point, and the algorithm should be robust to such changes. In this model, we look at two problems: the broadcast problem, where one computer tries to send a message to every single other computer on the network, and the majority problem, where initially each computer is given an opinion among k possible ones, and the goal is for every computer to know which opinion was originally the most popular one.

A dynamic graph algorithm is an algorithm that manages a dynamic network, or computes a property on it. Think of the network of webpages. You might want to rank all webpages from the most important one to the least (popular search engines call it the 'PageRank' algorithm). However, every day, new pages go online, while old pages go offline. You wouldn't want the algorithm to be run from scratch every night over all online webpages, as this would cost too much energy. Instead, you would like to have an algorithm that, once it has computed the rank of each webpage at a given time, be able to handle a few changes, and update its solution accordingly. In the dynamic graph algorithm model, we look at the minimum cut problem, where the goal is is divide the network into two subnetworks, such that the number of connections from one subnetwork to the other is minimized.