Dynamic Connectivity, Hopsets, and Byzantine Agreement

Abstract

Graphs are important and useful mathematical representations that can be used to model different objects in various research disciplines. For example, graphs are used for representing structures of chemical compounds in mathematical chemistry, representing phylogenetic trees in evolutionary biology, the small world concepts in social networks, and topology of a computer network. There are several properties on a graph for us to study, such as connectivity, reachability and distances. In this thesis, we study three fun algorithmic challenges and apply graph algorithms and data structures to improve them.

The first challenge is to design a data structure that solves the fully dynamic graph connectivity problem. For any sequence of edge insertions and deletions to a graph, our data structure performs updates in amortized randomized O(logn(loglogn)²) time, improving Thorup’s result by a O(loglogn) factor for the first time since 2000. Our result leaves a small O((loglogn)²) gap to the Ω(logn) lower bound given by Pătrașcu and Demaine in 2006.

The second topic we study includes various structures on graphs concerning distances and reachability, such as spanners, emulators, hopsets and shortcutting sets. A (β,ϵ)-hopset is a set of weighted edges added to an undirected weighted graph so that distances between any pair of vertices can then be (1+ϵ)-approximated using a path with at most β edges (hops). We applied Thorup and Zwick’s sublinear additive emulator construction to build a hopset. The construction, parameterized by k > 0, has an optimal tradeoff between the hopset size $O(n^{1+frac{1}{2^{k+1}-1}})$, the hop bound β = O(k/ϵ)^(k), and the approximation ratio (1+ϵ). This optimal tradeoff is established by the work of Abboud, Bodwin, and Pettie.

A shortcutting set is a reachability-preserving set of directed edges whose addition to a directed unweighted graph reduces the diameter. We show that there is a Ω(n^(1/6)) diameter lower bound on any shortcutting set of O(n) size. The lower bound techniques can also be applied to undirected weighted graphs. In particular, we provide a + Ω(n^(1/11)) additive distortion lower bound for O(n)-size spanners and a + Ω(n^(1/18)) additive distortion lower bound for O(n)-size emulators.

The third problem we solve is the asynchronous Byzantine agreement problem. In distributed computing, reaching consensus among all n processes is a challenging task, especially when a subset of processes are secretly corrupted and malicious behavior may occur. We provide a protocol that solves Byzantine agreement in an asynchronous distributed network model under perhaps the most challenging assumptions. Although we assume a fully-connected authenticated network ensuring that once a message is sent it will be delivered, the protocol has to work against a full-information (no cryptography for hiding information) and adaptive (corrupting processes over time) adversary. Most Byzantine agreement protocols are developed under weaker adversary models. We propose the first polynomial time protocol that allows up to ⌊(n−1)/4⌋ faulty processes, improving King and Saia’s 2013 result from (1.14×10⁻⁹)n faulty processes. Unlike the first two topics in this thesis, the asynchronous Byzantine agreement problem is not obviously related to graphs. But interestingly, one building block in our protocol is a fractional matching algorithm with a continuous Lipschitz guarantee.