We adapt the spooling graph used by the oblivious adversary, to construct the adaptive spooling graph. The idea is the same as in the oblivious case: all informed nodes will be in the left star, and all uniformed in the right star. Since the adversary is adaptive, he can keep this property even with smoothing.
Def 1: We define the dynamic adversarial spooling graph $\mathcal{G}=(V,\mathcal{E})$ as follows.
For every round $r$, let the set of informed nodes be $I_r$, and $v_r$ the minimum uninformed vertex. Then $G_r=(V,\mathcal{E}(r))$ where
$$\mathcal{E}(r)=(I_r\setminus \{1\}) \times \{1\} \cup (\overline{I_r}\setminus v_r) \times \{v_r\} \cup \{\{1,v_r\}\}$$
We want to use this adaptive version of the spooling graph to argue that flooding must use some number of rounds $R$ to complete with probability at least $1/2$. Our strategy will be to bound the expected number of newly informed nodes per round and then use Markov's inequality to finish the proof.
Goal: To upper bound the value of $\mathbb{E}[I_r]$.
We know that at least one node, namely, $v_r$ will learn the flooded message in round $r$. However, the smoothed edges between informed nodes in the left star and uninformed nodes in the right star will cause more nodes to become informed.
We introduce the indicator variable $X_{u,r}$ where:
- $X_{u,r}=1$ if there is an edge between $u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}$ and a vertex in the right star.
- $X_{u,r}=0$ if there is no edge between $u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}$ and a vertex in the right star.
Then we have $\mathbb{E}[I_r] \leq |I_{r-1}| + \mathbb{E}[\sum_{u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}}{X_{u,r}}]+1$ since we may have two distinct edges between the left and right spools pointing to the same node in the right spool. By linearity of expectation
$$\mathbb{E}[I_r] \leq |I_{r-1}|+\sum_{u\in \overline{I_{r-1}}\setminus \{v_{r-1}\}}{\mathbb{E}[X_{u,r}]}+1$$
$$\leq |I_{r-1}| + c_2k(|\overline{I_{r-1}}|-1)|I_{r-1}|/n^2+1$$
$$\leq |I_{r-1}|\cdot(1+c_2k/n) + 1$$
We achieve the last inequality using the fact that $|I_{r-1}|\leq n$. (Don't understand this next part), but using the linearity of this term, we can write
$$\mathbb{E}[I_{r}]\leq \mathbb{E}[I_{r-1}]\cdot(1+c_2k/n) + 1$$
Now we have a recurrence which we want to upper bound. We let $\mathbb{E}[I_{r}]=A_{r}$ to abstract away from the exact meaning of the recurrence. So we have
$$A_{r+1}\leq A_{r}\cdot(1+c_2k/n) +1$$
Observe that $A_{r+1}\geq A_{r}+1$ because of connectivity of our dynamic graph. We split the analysis of $A_r$ into two cases.
Case 1: $A_r\leq n/c_2k$. Then $A_r\leq 1$ which means the additive term dominates the $A_{r}c_2k/n$ multiplicative term. Hence we have $A_{r}+1\leq A_{r+1}\leq A_{r} + 2$. Because $A_1=1$, we have $\Theta(n/k)$ iterations where stage $1$ applies.
Case 2: $A_r\geq n/c_2k$. Then $A_{r}c_2k/n \geq 1$, so the multiplicative term is larger than the additive term. Therefore we have $A_{r+1}\leq A_r(1+2c_2k/n)$ for $r\geq r_0$. Hence we can write
$$A_{r_0+r_1}\leq A_{r_0}(1+2c_2k/n)^{r_1}$$
where $r_0$ is the maximum $r$ such that $A_{r_0}\leq n/c_2k$. Using $A_{r_0}=\Theta(n/k)$ we have
$$A_{r_0+r_1}\leq \Theta(n/k)(1+2c_2k/n)^{r_1}$$
Letting $r_1=\alpha n\log{k}/k$, where $\alpha$ is small enough, we have a round $A_{r_0+r_1}\leq n/10$.
Then there exists a round, namely $r_0+r_1$, where the expectation is bounded by $n/10$, which means that flooding has not completed at this round in expectation. Now using Markov's inequality we get
$$\mathbb{P}[|I_{r_0+r_1}|\geq n] \leq \frac{\mathbb{E}[I_{r_0+r_1}]}{n}\leq 1/10$$
Hence $\mathbb{P}[|I_{r_0+r_1}|< n] \geq 9/10$, which implies a $k$-smoothed lower bound of $\Omega(n\log{k}/k)$ for flooding.
Theorem: Fix $0 < k \leq n/16$, not necessarily an integer. For any $k$-smoothed adaptive
dynamic graph, for the flooding process to succeed with probability at least $1/2$ it must run
for $\Omega(\min\{n, n\log{k}/k\})$ rounds.
No comments:
Post a Comment