Flooding in $O(n\sqrt{\log{n}/k})$ on a $k$-smoothed adaptive dynamic graph

We have previously shown an $O(n^{2/3}\log{n}/k^{1/3})$ upper bound for flooding on $k$-smoothed connected dynamic graphs. However, our adversary was constrained to select the dynamic graph sequence $G_1,G_2,...$ without knowing the outcomes of $k$-smoothing. In this post we present [MPS20]'s work which extends this analysis to an adaptive adversary, i.e. one who can construct $G_r$ based on the previous outcomes of $k$-smoothing on $G_1,...,G_{r-1}$.

The intuitive idea is similar to what we have seen before:

• In the first $r$ rounds of flooding we are guaranteed to have $r$ nodes learn the flooded message.
• We then show that it is likely for some node in a support sequence to receive the message in the next $r$ rounds.
• If a node in the support sequence has the flooded message, then it is likely that our target node $u$ will receive the message within the next $r$ rounds.

However, since our adversary is adaptive we don't have the last bullet point because the adversary can see which nodes have the flooded message and can make it hard for $u$ to receive the message. The adaptive adversary can't do anything about the first two bullet points though since these are a consequence of the connectivity of $\mathcal{G}$ only.

To solve the issue of the last bullet point no longer being a valid strategy, we ask how likely it is for a smoothed edge to appear in between the set of $r$ nodes who know the message after the first $r$ rounds and $u$, since the adversary can't control this.

So consider the set $I$ of informed nodes from the first $r$ rounds of flooding. We know that $|I|=r$ by the connectivity of $\mathcal{G}$. Before we looked at the potential edge set $I\times S_l$ for a support sequence set $S_l$, but now we look at the potential edge set $I\times \{u\}$ where $u$ is our target node.

The probability that at least one edge from $I\times \{u\}$ is in the smoothed version of $\mathcal{G}$ is at least $c_1k|I\times \{u\}|/n^2 = c_1kr/n^2$. Therefore, the probability of no edge from $I\times \{u\}$ being in the smoothed version of $\mathcal{G}$ across $r$ rounds is at most $(1-c_1kr/n^2)\leq e^{-c_1r^2k/(n^2)}$ which is upper bounded by $1/n^2$ for $r=2n\sqrt{\log{n}/(c_1k)}$.

Thus the probability that $u$ does not receive the flooded message after $2n\sqrt{\log{n}/(c_1k)}$ rounds is at most $1/n^2$, which implies that $u$ will receive the flooded message with high probability. A union bound over all vertices in $\mathcal{G}$ gives us that flooding will complete in $O(n\cdot\sqrt{\log{n}/k})$ rounds with high probability.

Theorem: Given a dynamic graph $\mathcal{G}=(V,\mathcal{E})$ constructed by an adaptive adversary, some $1\leq k \leq n/16$, flooding completes in $O(n\sqrt{\log{n}/k})$ rounds with high probability on the $k$-smoothed version of $\mathcal{G}$.

[MPS20] Uri Meir, Ami Paz, and Gregory Schwartzman. “Models of Smooth-

ing in Dynamic Networks”. In: CoRR abs/2009.13006 (2020).

arXiv: 2009.13006. url: https://arxiv.org/abs/2009.13006.