[Din+15] present an algorithm which runs in $O(n^{2/3}\log{n}/k^{1/3})$ rounds with high probability on a $k$-smoothed dynamic graph.
At the core of their argument is the concept of a support sequence, i.e. a temporally connected subgraph across some number of rounds. The motivation being that if any node in the support sequence receives the flooded message, then it is likely to later be propagated to the target node in the support sequence. In essence a support sequence is just a "fat" target the flooded message needs to hit for $u$ to get the message within some bounded number of rounds dependent on the size of the support sequence. We use this to show that each node receives the flooded message with high probability.
Def 1: Fix integers $t$ and $l$ s.t. $1\leq l < t$, a dynamic graph $\mathcal{G}=(V, \mathcal{E})$, and a target node $u\in V$. A $(t,l)$-support sequence for $u$ in $\mathcal{G}$ is a sequence $S_0,S_1,...,S_l$ such that
- $S_0=\{u\}$,
- for every $i\in [0,l]$ we have $S_i \subseteq V$,
- for every $i\in [1,l]$ we have $S_{i-1}\subset S_i$ and $S_i\setminus S_{i-1}=\{v\}$ for some $v\in V$ such that $v$ is adjacent to at least one node of $S_{i-1}$ in $G_{t-i}$.
Since we are interested in connected dynamic graphs, it seems reasonable that any such dynamic graph has a $(t,l)$-support sequence.
Lemma 1: Given a connected dynamic graph $\mathcal{G}=(V,\mathcal{E})$, some node $u\in V$ and rounds $t$ and $l$ such that $1\leq l < t$, there exists a $(t,l)$-support sequence for $u$ in $\mathcal{G}$.
proof. We can construct such a support sequence inductively as follows. Let $S_0=\{u\}$. Now suppose we have validly constructed $S_0,...,S_i$. We define $S_{i+1}=S_i \cup \{v\}$, where $\{x,v\}\in \mathcal{E}(t-i)$ and $v\in V\setminus S_i$ and $x\in S_i$. Since $\mathcal{G}$ is connected, such a node $v$ must exist, otherwise $S_i$ would be disconnected from the rest of the graph.
Suppose we have a connected dynamic graph $\mathcal{G}$, from lemma 1, there exists a $(t,l)$-support sequence $S_0,...,S_l$ for a target node $u$ in $\mathcal{G}$. If some $v\in S_l$ receives the flooded message in round $t-l$, then we are certain that $u$ will receive the flooded message no later than round $t$. However, since $\mathcal{G}$ will be smoothed, it is possible for our support sequence to get "messed up". We want to show that this is unlikely. Take the following example support sequence.
Here we let $v_i=S_i\setminus S_{i-1}$ and let $v_0=u$. An edge between nodes $v_i$ and $v_j$ for $j<i$ indicates that $\{v_i, v_j\}\in\mathcal{E}(t-i)$. Suppose $v_7$ begins with the flooded message. Node $u$ will receive the message if a $\{v_7,u\}$-journey exists after $k$-smoothing. What is the probability of this in general? We will use a handy lemma that we showed in a previous blog post.
Handy Dandy Lemma: There exists constant $c_2 > 0$ such that the following holds. Consider any graph $G = (V, E)\in\text{allowed}(\mathcal{G}_{\text{conn}})$. Consider also any nonempty set $S \subseteq E$ of edges in the graph and smoothing value $k \leq n/16$. Then with probability at most $c_2k|S| /n^2$, the $k$-smoothed graph of $G$ removes an edge from $S$.
So let's say that $v_i$ has the message, and that $N(v_i)=\{v_j\text{ }|\text{ }\{v_i,v_j\}\in\mathcal{E}(t-i)\text{ and }j<i\}$ is the neighborhood of $v_i$ in $G_{t-i}$. For the message not to proceed in the support sequence, then all $|N(v_i)|$ edges need to be removed by smoothing. Using the handy dandy lemma we know that the probability that $v_i$ can't pass its message on to any $N(v_i)$ is at most $(c_2k/n^2)^{|N(v_i)|}\leq c_2k/n^2$. We can then take a union bound over the up to $l$ rounds needed for the message to reach the target node $u$. This gives us a probability of at most $c_2kl/n^2$ for $u$ not receiving the flooded message.
If we choose $l=n^{2/3}/k^{1/3}$, we get $c_2 k^{2/3}/n^{4/3}\leq 1/4$, which holds for sufficiently large $n$ and $k\leq n$. Thus the probability that $u$ receives the flooded message is at least $3/4$. This gives us the following lemma.
Lemma 2: Fix a connected dynamic graph $\mathcal{G}=(V,\mathcal{E})$ and any $(t,l)$-support sequence $S_0,...,S_l$ where $S_0=\{u\}$. If any $v\in S_l$ receives the flooded message by round $t-l$, then $u$ receives the flooded message with probability at least $3/4$.
Lemma 2 assumes that a node in the support sequence set $S_l$ already has the flooded message by round $t-l$. However, we don't know that this is the case so let's bound the probability of that happening.
We know that in round $l=n^{2/3}/k^{1/3}$ at least $l$ nodes know the message because of the connectivity of $\mathcal{G}$. Thus we have $l|S_l|$ possible edges between nodes that know the message and nodes in $S_l$. The probability that any of these edges are present in a round $r\geq l$ is at least $c_1kl|S_l|/n^2$. If any of these edges are present from rounds $l$ to $t-l$, then $S_l$ receives the flooded message by round $t-l$. Thus we have a probability of at most $(1-c_1kl|S_l|/n^2)^{t-2l}$ that none of these edges are present in all rounds from $l$ to $l-t$.
Choosing $t=\alpha n^{2/3}/k^{1/3}$ for $\alpha \geq 3$, we have probability at most
$$(1-c_1k^{1/3}|S_l|/n^{2/3})^{(\alpha-2)n^{2/3}k^{1/3}}\leq e^{-c_1(\alpha-2)}$$
which for a suitable choice of the constant $\alpha$ is at most $1/4$.
So if either the flooded message does not reach $S_l$ by round $t-l$ or the message does not reach its target in the support structure, $u$, then $u$ will not receive the message. So $u$ does not receive the message with probability at most $1/4 + 1/4 = 1/2$. This gives us the following key result.
Lemma 3: Fix a connected dynamic graph $\mathcal{G}=(V,\mathcal{E})$, any node $u\in V$, and a consecutive interval of $\alpha n^{2/3}/k^{1/3}$ rounds, where $\alpha\geq 3$ is a constant. For $k\leq n/16$, node $u$ receives the flooded message in the $k$-smoothed graph of $\mathcal{G}$ with probability at least $1/2$.
Now that we know each node has a constant probability of receiving the flooded message after $\alpha n^{2/3}/k^{1/3}$ rounds, we can give a high probability guarantee that every node receives the flooded message over a larger round interval.
If we repeat lemma 3 $\Theta(\log{n})$ times, we get that node $u$ does not receive the flooded message with probability at most $2^{-\log{n}}$, and thus it will receive the message with probability at least $1-\frac{1}{2^{\log{n}}}$, i.e. with high probability since $2^{\log{n}}=O(n)$.
Theorem 1: For any connected dynamic graph $\mathcal{G}$ and smoothing value $k\leq n/16$, flooding completes in $O(n^{2/3}\log{n}/k^{1/3})$ rounds on the $k$-smoothed version of $\mathcal{G}$ with high probability.
[Din+15] Michael Dinitz et al. “Smoothed Analysis of Dynamic Networks”.
In: Proceedings of the 29th International Symposium on Distributed
Computing - Volume 9363. DISC 2015. Tokyo, Japan: Springer-
Verlag, 2015, pp. 513–527. isbn: 9783662486528. doi: 10.1007/
978- 3- 662- 48653- 5_34. url: https://doi.org/10.1007/978-3-662-48653-5_34.
No comments:
Post a Comment