Latency, Conductance, and The Role of Connectivity in Graph Problems
COM1 Level 3
MR1, COM1-03-19
Abstract:
In this thesis, we study how the connectivity of the underlying network graph affects a network's performance. We consider various aspects of graph connectivity determined by the structure of the graph and the distribution of latencies over the graph edges. Edge latency represents the time delay in sending a message from one node to another. We study several graph problems namely leader election, information dissemination and minimum weight spanning tree (MST) construction in various different communication models and show that the time and message complexities required to solve these problems do in fact depend on the connectivity of the given graph as well as the distribution of latencies over the edges of the network or a combination of both.
Firstly, we look at the problem of randomized leader election in synchronous distributed networks (where all edges have unit latency) with a special focus on the message complexity. We provide an algorithm that solves the implicit version of leader election (where non-leader nodes need not be aware of the identity of the leader) in any general network with $O(\sqrt{n} \log^{7/2} n \cdot t_{mix})$ messages and in $O(t_{mix}\log^2 n)$ time, where $n$ is the number of nodes and $t_{mix}$ refers to the mixing time of a random walk in the network graph $G$. For several classes of well-connected networks that have a large conductance or alternatively small mixing times, e.g., expanders, hypercubes, \etc, the above result implies extremely efficient (sublinear running time and messages) leader election algorithms. Correspondingly, we show that any substantial improvement is not possible over our algorithm, by presenting an almost matching lower bound for randomized leader election. We show that $\Omega(\sqrt{n}/\phi^{3/4})$ messages are needed for any leader election algorithm that succeeds with probability at least $1-o(1)$, where $\phi$ refers to the conductance of a graph. To the best of our knowledge, this is the first work that shows a dependence between the time and message complexity to solve leader election and the connectivity of the graph $G$, which is often characterized by the graph's conductance $\phi$. Apart from the $\Omega(m)$ bound in [Kutten et al., J.ACM 2015] (where $m$ denotes the number of edges of the graph), this work also provides one of the first non-trivial lower bounds for leader election in general networks.
Next, we consider the classical problem of information dissemination: one (or more) nodes in a network have some information that they want to distribute to the remainder of the network. Here, we study the cost of information dissemination in networks where edges have arbitrary latencies. We first generalize the idea of conductance to weighted graphs (where weights correspond to latencies) by defining $\phi_*$ to be the ``critical weighted conductance'' and $\ell_*$ to be the ``critical latency''. One goal here is to argue that $\phi_*$ characterizes the connectivity of graphs with latencies in much the same way that conductance characterizes the connectivity of unit latency unweighted graphs. We give near tight lower and upper bounds on the problem of information dissemination, up to polylogarithmic factors. Specifically, we show that in a graph with latency diameter $D$ and maximum degree $\Delta$, there exists an algorithm that achieves information dissemination in $O(\min((D+\Delta)\log^3{n}, (\ell_*/\phi_*)\log n)$ time; and any information dissemination algorithm requires at least $\Omega(\min(D+\Delta, \ell_*/\phi_*))$ time in the worst case.
Lastly, we consider the problem of determining the minimum weight spanning tree (or MST) on graphs, where each edge has an associated weight (using which the MST is determined), a latency value (which may or may not be equivalent to the weight) and a capacity value $c$ that determines the communication throughput over that edge (in this case, the rate at which messages can be sent). Depending on how the edge latencies relate to the edge weights, we provide several tight bounds on the time required to construct an MST. When edge weights exactly correspond with the latencies, we show that, perhaps interestingly, the bottleneck parameter in determining the running time of an algorithm is the total weight $W$ of the constructed MST (rather than the total number of nodes $n$, as in the standard \textsf{CONGEST} model). That is, we show a tight bound of $\tilde{\Theta}(D + \sqrt{W/c})$, where $D$ refers to the latency diameter of the graph, $W$ refers to the total weight of the constructed MST and edges have capacity $c$. When there is no correlation between the latencies and the weights, we show that unlike the sublinear time algorithms in the standard \textsf{CONGEST} model, on small diameter graphs, the best time complexity that can be achieved is $\tilde{\Theta}(D+n/c)$. However, if we restrict all edges to have equal latency $\ell$ and capacity $c$, while having possibly different weights, we give an algorithm that constructs an MST in $\tilde{O}(D + \sqrt{n\ell/c})$ time. In each case, we provide nearly matching upper and lower bounds.