The adversary's strategy is very similar to that for the $\Omega(n\log{k})$ lower bound. The adversary connects all free edges together so that we are left with the connected components $C_1, C_2, ..., C_l$. Then arbitrary representatives from each component: $v_1, v_2, ..., v_l$ are chosen and connected in a line. This graph $G_r$ for round $r$ will be the adversary's chosen graph. Our aim is to argue that any token forwarding algorithm for $k$-gossip has lower bound $\Omega(nk/\log{n})$ using $G_r$.
The first new concept is the idea of a half-empty configuration which is used to bound the progress made in each round.
Def 1: Given a sequence of nodes $v_1, v_2, ..., v_l$, we say that this sequence is half empty in round $r$ with respect to a sequence of tokens $t_1, t_2, ..., t_l$ if at the start of round $r$ we have for all $1\leq i, j \leq l, i\not= j$ that either $v_i$ is missing $t_j$ or $v_j$ is missing $t_i$.
Our proof strategy will be to show that the half-empty configurations must have small size, which limits the progress in each round to a small amount.
Lemma 1: If $m$ useful token exchanges occur in round $r$, then there exists a half-empty configuration of size at least $m/2 + 1$ at the start of round $r$ in $G_r$.
Note that a useful token exchange is one which occurs along a non-free edge.
proof. Since we have $m$ useful token exchanges which must occur along non-free edges, we know that there must be at least $m/2$ non-free edges since each non-free edge contributes at worst two useful token exchanges. By the construction of $G_r$, we have that a non-free edge must be between two nodes $(u, v)$ in different connected components in $G_r \setminus \{\text{non-free edges}\}$. Since we have at least $m/2$ non-free edges, we have at least $m/2 + 1$ connected components in $G_r \setminus \{\text{non-free edges}\}$.
Now we want to show that for any $u, v$ described above, we have two tokens $t_u$ and $t_v$ where either $u$ is missing $t_v$ or $v$ is missing $t_u$. Suppose for contradiction that $u$ knows $t_v$ and $v$ knows $t_u$ for any pair of tokens $(t_u, t_v)$. Then $(u, v)$ must be a free edge, which is a contradiction.
We can use this idea on every pair $(v_i, v_j)$ for $1\leq i < j \leq l$ to form a half-empty sequence of length $m/2 + 1$.
Lemma 2: If a sequence $v_1, v_2, ..., v_l$ of nodes is half-empty with respect to $t_1, t_2, ..., t_l$ at the start of round $r$, then $v_1, v_2, ..., v_l$ is half-empty with respect to $t_1, t_2, ..., t_l$ at the start of any round $r' < r$.
proof. Suppose for contradiction that in round $r' < r$, $v_1, v_2, ..., v_l$ is not half-empty with respect to $t_1, t_2, ..., t_l$. Then for some pair $(v_i, v_j)$ we must have that $v_i$ knows $t_j$ and $v_j$ knows $t_i$. If this is true in round $r'<r$, then it is still true in round $r$. A contradiction.
Now we prove that for a specific initial token distribution, the $\Omega(nk/\log{n})$ lower bound holds.
First note that if $k \leq c\log{n}$ for a constant $c$, then the bound is just $\Omega(cn\log{n}/\log{n})=\Omega(n)$, which is the lower bound for $k=1$ under our adversary's construction $G_r$. So we can assume that $k > c\log{n}$.
Theorem 1: From an initial token distribution in which each node has each token independently with probability $3/4$, any online token-forwarding algorithm will need $\Omega(kn/\log{n})$ rounds to complete with high probability against a strong adversary.
By the way, when we say with high probability (w.h.p), we mean with probability $\geq 1 - c/n^{\alpha}$ from constants $c, \alpha > 0$.
proof strategy. If we can get a lower bound $X$, on the number of tokens each node is missing w.h.p before the first round, and an upper bound $U$, on the number of useful token exchanges across each round, then we must have at least $nX/U$ rounds to complete $k$-gossip.
proof. We first get an upper bound on the number of useful token exchanges across each round. Naturally, if we can show that the largest half-empty sequence is small w.h.p, then we also have a small number of useful exchanges and thus missing tokens.
Let $E_l$ denote the event that there exists a half-empty configuration of size $l$ at the start of the first round. We upper bound the probability of $E_l$ occurring.
$$\mathbb{P}[E_l] \leq {n \choose l} \cdot \frac{k!}{(k-l)!}\cdot \left(\frac{1}{2}\right)^{{l \choose 2}} \leq n^l \cdot k^l \cdot 2^{-l(l-1)/2} \leq \frac{2^{2l\log_2{n}}}{2^{l(l-1)/2}}$$
i.e. we have ${n \choose l}$ ways to select $l$ nodes for a half-empty configuration, $\frac{k}{(k-l)!}$ ways to select the corresponding token sequence, and for each pair $(v_i, v_j)$ in the half-empty configuration a $\leq 1/2$ probability that $v_i$ is missing $t_j$ or $v_j$ is missing $t_i$.
If we let $l=5\log_2{n}$, then we get $\mathbb{P}[E_l] \leq 1/2^{(5/2)\log_2{n}(\log_2{n}-1)} = 1/n^{(5/2)(\log_2{n}-1)} \leq 1/n^2$. Note that if a half-empty configuration of size $l$ exists, then we also have half-empty configurations of size $1, 2, ..., l$. Thus $1-\mathbb{P}[E_l] = \mathbb{P}[]$we have probability at least $1-1/n^2$ that ... to be continued.
[Dut+11] Chinmoy Dutta et al. “Information Spreading in Dynamic Networks”. In: CoRR abs/1112.0384 (2011). arXiv: 1112.0384. url:
http://arxiv.org/abs/1112.0384.
No comments:
Post a Comment