Models of Smoothing in Dynamic Networks

Dinitz et al.show a tight bound of $\tilde{\Theta}(n^{2/3}/k^{1/3})$ for the problem of flooding in a dynamic networks with noise $k$. That is, as $k$ decreases, flooding becomes harder, but only up to $\tilde{\Theta}(n^{2/3})$ for a constant $k$. However, when there is no noise at all, a linear, in $n$, number of rounds is required. That is, there is a curious gap between just a tiny amount of noise and no noise at all, which stands in sharp contrast with the smooth change in the flooding time as a function of $k$, when $k$ ranges from $1$ and to $\Omega(n)$. One may wonder if there is a natural way to extend the model presented by Dinitz et al.to bridge this gap.

The results of Dinitz et al.assume an oblivious adversary. That is, the evolution of the network must be decided by the adversary in advance, without taking into account the noise added by the smoothing process. It is natural to ask what is the power of an adaptive adversary compared to an oblivious one. As smoothed analysis aims to be the middle ground between worst-case and average-case analysis, it is very natural to consider the effect of noise on the strongest possible adversary, i.e., an adaptive adversary.

The type of noise considered by Dinitz et al.remains constant between rounds, regardless of the topology or the actions of the adversary, which corresponds to “background noise” in the network. However, it is very natural to consider cases where the amount of noise itself changes over time. More specifically, if we think of a noise as an artifact of the changes the adversary performs to the system, and thus, it is natural to expect different amounts of noise if the adversary performs a single change, or changes the whole topology of the graph. Hence, a natural model of noise in a network is one where the added noise is proportional to the amount of change attempted by the adversary, that is, $k$ is proportional to the Hamming distance between the current graph and the next one. A different, natural definition of a changes-dependent noise, is where the noise occurs only in the changing edges, and not all the graph.

Analysing our new models of smoothing require a new and more global techniques. While we adopt the results of [8] for changes in a single round, our models introduce new technical challenges, as they require multiple-round based analysis.

The main technical challenge for proving upper bounds comes from the fact that one cannot even guarantee that noise occurs at every round, and when it does — the amount of noise is not fixed through the execution of the whole algorithm. This requires us to conduct a much more global analysis, taking into account sequences of rounds with a varying amount of noise, instead of analyzing a single round at a time. In several cases, the static diameter $D$ appears as a parameter in our results and analysis: in our model, the adversary can force change-free rounds where no noise occurs, in which case flooding happens on a static graph.

In an attempt to study the exact limitations of our noise models, we present specifically crafted lower bound networks for each model. Note that in many models our adversary is adaptive, potentially making it much stronger. This makes our lower bound more strategy-based, and not merely a fixed instance of a dynamic graph. We revise the original flooding lower bound of Dinitz et al., in order to make it more applicable to other models. We present a more detailed and rigorous proof, that indeed implies tight bounds in most of our models, and specifically, when considering adaptive adversaries.

Let $U_{i}$ denote the set of vertices that have been flooded at time $i$. Using merely the fact that the graph is connected at all times, and assuming the flooding process is not over, we know that at each round a new vertex receives the message, implying $\left|U_{i+1}\right|\geq\left|U_{i}\right|+1$. Hence, $\left|U_{r}\right|\geq r$ (with probability $1$).

We denote by $V_{i}$ the set of vertices from which $v$ can receive the message within the last $i$ rounds ($R-i+1,\dots,R$). Formally, fix the sequence of graphs chosen by the oblivious adversary, and apply the random noise on these graphs to attain the last $r$ graphs of our smoothed dynamic graph. Define $V_{0}=\left\{v\right\}$, and for $i>0$, define $V_{i}$ as the union of $V_{i-1}$ with the neighbors of it in $G_{R-i+1}$. That is, $V_{i}$ is defined analogously to $U_{i}$ but with the opposite order of graphs. We point out that we are dealing with a stochastic process: each $V_{i}$ is a random variable that depends on the noise in the last $i$ rounds. Still, the connectivity guarantees that $\left|V_{i+1}\right|\geq\left|V_{i}\right|+1$. Therefore, we have $\left|V_{r}\right|\geq r$ (with probability $1$).²²2Note that here we strongly rely on the obliviousness of the adversary: with an adaptive adversary, one cannot define $V_{r}$ properly before the end of the execution of the algorithm, as the adversary’s choices were not yet made. The case of an adaptive adversary is discussed in the next section.

The above processes define two randomly chosen sets, $U_{r}$ and $V_{r}$, each of size at least $r$. If $U_{r}\cap V_{r}\neq\emptyset$, then we are done as $v$ is guaranteed to receive the message even if we ignore the middle rounds. Otherwise, we consider the set $S=U_{r}\times V_{r}$ of potential edges, and show that one of them belongs to our smoothed dynamic graph in at least one of the middle graphs, with probability at least $1-n^{-2}$, for the right value of $r$.

Let us consider separately the two cases: $k\geq 1$ (note that non-integer $k$ was not handled before), and the case $0<k<1$.

In this case, we essentially claim the following: we are guaranteed to have either $\lfloor k\rfloor$ noise or $\lceil k\rceil$ at each and every round. Applying Lemma 2.3 for each such round, the probability of not adding any edge from $S$ is at most

where the inequality follows from $\lfloor k\rfloor\geq k/2$ and $\left|S\right|=\left|U_{r}\right|\cdot\left|V_{r}\right|\geq r^{2}$. Thus, the probability of not adding any edge from $S$ in any of these $r$ noisy rounds is at most

which is upper bounded by $n^{-2}$, whenever $r\geq n^{2/3}\cdot\left[(4\log n)/(c_{1}k)\right]^{1/3}$.

Note that here we can no longer use $\lfloor k\rfloor\geq k/2$, and so we turn to a somewhat more global analysis which guarantees that “enough” rounds produce a (single) noisy edge: at each round we essentially add a noisy edge with probability $k<1$, and otherwise do nothing. Since we have $r$ rounds, and in each of them noise occurs independently, we can use a standard Chernoff bound to say that with all but probability at most $e^{-0.4kr}$, we have $(k/10)r$ rounds in which a noisy edge was added.³³3The expectation over all rounds is $kr$ noisy edges. We later bound this term. For each of the $(k/10)r$ rounds we again apply Lemma 2.3 to claim that no edge from $S$ was added, with probability at most

where the inequality follows again from $\left|S\right|=\left|U_{r}\right|\cdot\left|V_{r}\right|\geq r^{2}$. Thus, the probability of not adding any edge from $S$ in any of these $(k/10)r$ noisy rounds is upper bounded by

which is upper bounded by $1/(2n^{2})$ whenever $r\geq n^{2/3}\cdot\left[(10\log n)/(c_{1}k)\right]^{1/3}$.

Recalling that we only deal with the case $k\geq c\cdot\log n/n$, choosing the constant $c$ according to the constant $c_{1}$, we also get $r\geq 10\log n/k$. This allows us to bound the error of the Chernoff inequality: $e^{-0.4kr}\leq e^{-3\log n}\leq 1/(2n^{2})$. Union bounding on both possible errors, we know that with probability at least $1-n^{-2}$ the vertex $v$ is informed after $3r$ rounds.

To conclude, we use $r=n^{2/3}\cdot\left[(10\log n)/(c_{1}k)\right]^{1/3}$. For any value $k\geq c\cdot\log n/n$, and for any realization of $U_{r}$ and $V_{r}$, the message has been passed to $V_{r}$ within the $r$ middle rounds, with probability at least $1-n^{-2}$. So $v$ received the message after $R=3r$ rounds with the same probability. Taking a union bound over all the vertices implies that $R$ rounds are enough to flood to the whole network with probability at least $1-1/n$.

We also show a matching lower bound, restructuring the proof of the lower bound in [8]. We note that their proof actually states a lower bound of $\Omega\left(min\left\{n/k,n^{2/3}/k^{1/3}\right\}\right)$ that apply to any $k<n/16$ (and is indeed tight for $k<O(\sqrt{n})$). We restructure the analysis of the lower bound to fit the different constructions given in the following sections, as follows.

First, we consider the first $R$ rounds, for some parameter $R$, and show inductively that the following two main claims continue to hold for every round $i<R$ with very high probability.

• •

  Some pre-defined set of vertices stays uninformed

• •

  Given the above, the expected number of informed vertices in total does not grow rapidly.

The growth (in the expected number of informed vertices) has a multiplicative-additive progression, potentially becoming an exponential growth (with a small exponential).

We choose $R$ such that the expected number of informed vertices is upper bounded by $\delta n$, and use Markov inequality to show that with high probability the flooding is not yet over after $R$ rounds. We then apply a union bound over all the inductive steps, where each has a small probability to fail the inductive argument. Altogether, we show that with high probability, the flooding is not over after $R$ rounds.

In Appendix A, we use an argument along those lines in order to prove the following extensions of the lower bound from [8] to non-integer values and to fractional values (where $k<1$).

In particular, whenever $k=O(\sqrt{n})$, the dominant term is $\Omega(n^{2/3}/k^{1/3})$, matching the upper bound (up to logarithmic factors).

Note that if $v\in U_{r}$, then we are done. Otherwise, we consider the set $S=U_{r}\times\left\{v\right\}$ of potential edges, and show that one of them belongs to our smoothed dynamic graph in at least one of the intermediate graphs, with high probability. We use the fact that for $0<k<1$ the assertion is trivial, and analyse the case of $k\geq 1$.

In this case, as before, we apply Lemma 2.3 for each round in this phase, and conclude that the probability of not adding any edge from $S$ is at most

where the inequality follows from $\lfloor k\rfloor\geq k/2$ and $\left|S\right|=\left|U_{r}\right|$. Thus, the probability of not adding any edge from $S$ in any of these $r$ noisy rounds is upper bounded by

which is upper bounded by $n^{-2}$, for $r=2n\cdot\sqrt{\log n/(c_{1}k)}$.

Using this value for $r$, for any value $k\geq 1$, and realization of $U_{r}$, the message has been passed to $v$ with probability at least $1-n^{-2}$, within the whole $R=2r$ rounds of phase one and two. A union bound over all vertices $v\neq u$ implies that $R$ rounds are enough to flood to the whole network with probability at least $1-1/n$.

When $k$ is a constant, the above result is tight, which we prove by adjusting the oblivious dynamic network from Theorem 3.3 to use the adversary’s adaptivity, as follows. The basic structure of the hard instance for flooding is achieved by roughly splitting the graph into informed and uninformed vertices. In order to ensure low diameter, all the uninformed vertices are connected as a star, centered at a changing uninformed vertex called a head, which in turn connects them to a star composed of the informed vertices. The key idea in the analysis of this process, is that the head at each round should not become informed via noisy edges at an earlier round, as in this case it will immediately propagate the message to all the uninformed vertices, completing the flooding. An oblivious adversary picks a sequence of heads at the beginning of the process, and this invariant is kept since the probability of any of the selected heads to get informed too early is low. However, after roughly $n^{2/3}$ rounds, the probability that a selected head is informed becomes too high. An adaptive adversary, on the other hand, can continue crafting a hard instance graph for a linear number of rounds — in each round, the adversary knows which vertices are uninformed and can pick one of them as the new head, thus overcoming this obstacle.

As we are promised a static diameter of at most $D$, we know that if the networks does not change for $D$ steps consecutively, the flooding is guaranteed to finish successfully. Therefore, we can assume that within the $r$ middle rounds, once every $D$ rounds, we have a round where changes happen, and therefore potential noise might occur. This overall guarantees us $r/D$ such rounds, where in each of them noise occurs independently with probability at least $\epsilon$ (that correspond to the amount of noise if only a single change was made). We apply a standard Chernoff bound to say that with all but probability at most $e^{-0.4\epsilon r/D}$, we have $\epsilon r/(10D)$ rounds in which at least one noisy edge was added.⁴⁴4The expectation over all rounds is at least $\epsilon r/D$ rounds with noisy edges. We later bound this term. We write $t_{i}$ for the amount of noise at each such round, for which we know $1\leq t_{i}\leq n/16$, using the premise. Now, one can safely apply Lemma 2.3 with $S$ for each such round, to upper bound the probability of not adding any such potential edge:

where the inequality simply follows from $t_{i}\geq 1$ and $\left|S\right|\geq r^{2}$. Thus, the probability of not adding any edge from $S$ in any of the $\epsilon r/(10D)$ noisy rounds is upper bounded by

which is upper bounded by $1/(2n^{2})$, whenever $r\geq 20n^{2/3}\cdot\left[D\log n/(c_{1}\epsilon)\right]^{1/3}$.

We now recall assuming that $n\geq c\cdot D\log n/\epsilon$, using the right constant $c$ (as function of the constant $c_{1}$). For this case, we also get $r\geq 10D\log n/\epsilon$, for which the case of too few noisy rounds is bounded by $e^{-0.4\epsilon r/D}\leq e^{-3log(n)}\leq 1/(2n^{2})$.

By union bound we get the following: using $r=20n^{2/3}\cdot\left[D\log n/(c_{1}\epsilon)\right]^{1/3}$, for any $D\geq c\cdot\epsilon n/\log n$, and any realization of $U_{r},V_{r}$, the message has been passed to $V_{r}$ within the $r$ middle rounds with probability at least $1-n^{-2}$, and so after $R=3r$ rounds, $v$ received the message with the same probability. Using union bound over all vertices in the network, we conclude see that $R$ rounds suffice for flooding with probability at least $1-1/n$.

Adjusting the same argument for an adaptive network, using only two phases (same as Theorem 3.5), would give an upper bound of $O(n\cdot\sqrt{D\log n/\epsilon})$, which in this case does not improve upon the trivial $O(n)$ promised by connectivity alone.

We continue to show that this is tight, and in the proportional noise model, the changes in the network can be so subtle that they would invoke little noise and the flooding would barely speed up at all, asymptotically. We show the following lower bound, and note that the graph sequence constructed in the proof has constant $D$, where it is hardest to manipulate.

In the current, adaptive model, the spooling graph no longer stands as a slow-flooding graph. Changing the center of the uninformed star takes $\Omega(n)$ edge changes in early rounds, and the proportional noise invoked by these changes would be devastating (e.g., for $\epsilon=\Omega(1)$).

Instead, in the following proof, the adversary relies on its adaptivity in order to maintain control over the network. This is done using a sequence of graphs that require only $O(1)$ changes at each round.