SOME NEW RESULTS FOR DISTRIBUTED ALGORITHMS IN DYNAMIC NETWORKS

Abstract

This thesis study distributed algorithms in dynamic networks. Different than static networks, the topologies of dynamic networks can change from time to time. The first contribution of this thesis is proving several novel lower bounds on the time complexities of several fundamental problems in dynamic networks with oblivious adversaries. Our proofs for these lower bounds rely on a novel reduction from a two-party communication complexity problem with a special entity we call the leaker. Our second contribution explores the power of randomization in general distributed algorithms in dynamic networks with adaptive adversaries. All the earlier contributions are for robust dynamic networks whose topologies remain connected and undirected in all rounds. Our third contribution relaxes this assumption, and study shaky dynamic networks, whose topologies may be disconnected and/or directed in some rounds.