$k$-gossip with smoothing

We have so far analysed gossip on connected dynamic graphs, however, we have not yet looked at this problem under smoothing. We use the analysis conducted by [cite1] and [cite2] as a blackbox to derive a $s$-smoothed upper bound for $k$-gossip.

Here we assume that each node in our dynamic graph is given as part of the input $n$ and $k$, we also assume there is some agreed upon ordering of the tokens. This leads to a very simple $O(nk)$ algorithm without smoothing.

Algorithm for each node:

• $i=1$
• For $i$ from $1$ to $k$ do
• For $n-1$ rounds broadcast the $i^{\text{th}}$ smallest token the node knows.

This works because of the connectivity of the dynamic graph ensuring that each round a node must learn a token. Because this protocol breaks up $k$-gossip into $k$ phases of flooding a single token, we can use results from smoothed flooding for $k$-gossip.

We know that flooding a token on a connected dynamic graph under $s$-smoothing against an oblivious adversary terminates within $O(n^{2/3}\log{n}/s^{1/3})$ with probability $1-\frac{1}{n}$. So instead of iterating $n-1$ times we can iterate $O(n^{2/3}\log{n}/s^{1/3})$ times.

Letting $F_i$ be the event that in phase $i$, flooding does not terminate in $O(n^{2/3}\log{n}/s^{1/3})$ round. Then $\mathbb{P}[F_i]=\frac{1}{n}$. The probability that any $F_i$ occurs for $1\leq i \leq k$ is then union bounded

$$\mathbb{P}[\bigcup_{i=1}^{k}{F_i}]\leq \sum_{i=1}^{k}{F_i}=\frac{k}{n}$$

Therefore, the probability that none of the phases fail is at least $1-\frac{k}{n}$. This is not with high probability since $k\leq n$. Thus we need to increase the upper bound for flooding so that the probability of success is at least $1-\frac{1}{n^2}$.

In flooding, we needed an edge between two sets, each of size $\geq r$, where $r$ is the number of rounds in one of the algorithm's phases. This happens with probability at least $c_1sr^2/n^2$ for constant $c_1$ and under $s$-smoothing. Over $r$ rounds, the probability of this not happening in any of the rounds is at most $(1-c_1sr^2/n^2)^r$. We can use the Chernoff bound for random Bernoulli variables to get the following upper bound $(1-c_1sr^2/n^2)^r \leq e^{-c_1r^3s/n^2}$.

We are union bounding twice: once over the $n$ vertices and once over the $k\leq n$ tokens. Therefore, we need flooding to fail with probability at most $1/n^3$. Therefore we need to pick a value for $r$ s.t.

$$e^{-c_1r^3s/n^2}\leq 1/n^3$$

solving this for $r$ yields that

$$r\geq n^{2/3}(3\ln{n})^{1/3}/(c_1s)^{1/3}$$

Result Oblivious: $k$-gossip terminates within $O(kn^{2/3}(\log{n}/s)^{1/3})$ rounds with probability at least $1-1/n$ against an oblivious adversary under $s$-smoothing.

We can extend this result to the case of an adaptive adversary. Here flooding requires $O(n\sqrt{\log{n}/s})$ rounds to terminate. In a previous blog post, I went over the reason why the probability of a helpful edge being added is at least $c_1sr/n^2$, which is required to occur at some point within $r$ rounds for an arbitrary node $v$ to receive the flooded message. Thus the probability that flooding fails is at most $(1-c_1sr/n^2)^{r}$. Using a Chernoff bound we can deduce that

$$(1-c_1sr/n^2)^{r}\leq e^{-c_1r^2s/n^2}$$

We want $e^{-c_1r^2s/n^2} \leq 1/n^3$ and so solving for $r$ we get

$$r\geq n\sqrt{3\ln{n}/c_1s}$$

Result Adaptive: $k$-gossip terminates within $O(kn\sqrt{\log{n}/s})$ rounds with probability at least $1-1/n$ against an oblivious adversary under $s$-smoothing.

Note that the adaptive result improves the $O(nk)$ upper bound, when $\sqrt{\log{n}/s}\leq 1$, which happens when $n\leq e^s$