On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive Adversaries

Background. Understanding the power of randomization has long been a key goal in algorithms research. Over the years, researchers have obtained many interesting results on the power of randomization, such as in centralized algorithms (e.g., [25]), in parallel algorithms (e.g., [21]), and in algorithms in static networks (e.g., [7, 8, 10, 11, 22]). This paper aims to gain deeper insights into the power of randomization in general distributed algorithms in dynamic networks with adaptive adversaries. Dynamic networks  [4, 6, 19, 23] model communication networks whose topologies may change over time, and has been a growing research topic in distributed computing. While randomization has been used extensively to solve various specific problems in dynamic networks (e.g., [17, 19]), prior works have not focused on the power of randomization in general distributed algorithms in dynamic networks (i.e., to what extent randomized algorithms can outperform deterministic ones).

Our Setting. We consider a synchronous dynamic network with a fixed set of n nodes. The network topology in each round is some arbitrary connected and undirected graph as determined by an adaptive adversary, and we adopt the following commonly-used model  [16, 18, 26]: The adaptive adversary decides the round-r topology based on the algorithm’s coin flip outcomes so far (i.e., up to and including round r). The adaptive adversary does not see the coin flip outcomes in round \(r+1\) or later. We follow the communication model in [14, 26]: In each round, a node may choose to either send an \(O(\log n)\) size message (i.e., the broadcast \(\mathcal {CONGEST}\) model  [24]) or to receive. A message sent is received, by the end of that round, by all the receiving neighbors of the sender in that round. Each node has some input of arbitrary size and a unique id between 0 and \(n-1\). We consider general distributed computing problems modeled as some arbitrary function of the n input values (as an input vector). The output of the function is also a vector of length n, and node i should output the \((i+1)\)-th entry of that vector. There is no constraint on the output size. An algorithm in this paper always refers to some algorithm for solving some distributed computing problem as modeled in the above way. Note that many problems that are not typically defined as functions, such as computing a unique minimum spanning tree (of some input graph) and token dissemination  [9, 17], can nevertheless be modeled as a function. The time complexity is defined to be the number of rounds needed for all nodes to output. An algorithm P’s time complexity, denoted as \(\text{ tc}_P(n,d)\), corresponds to its time complexity under the worst-case scenario. Here the worst-case scenario consists of i) the worst-case input (vector), and ii) the worst-case adaptive adversary for generating dynamic networks with at most n nodes and at most d dynamic diameter. The dynamic diameter  [18] of a dynamic network, intuitively, is the minimum number of rounds needed for a node u to causally influence another node v, when considering the worst-case u and v in the dynamic network. Section 2 gives a full description of the model.

Randomness in Dynamic Networks. For any given deterministic algorithm, informally, let us call its corresponding worst-case scenario as a “bad” scenario. A “bad” scenario for one deterministic algorithm may very well not be a “bad” scenario for other deterministic algorithms. Since a randomized algorithm is a distribution of deterministic algorithms, intuitively, randomization potentially helps to better deal with all those “bad” scenarios. For algorithms in dynamic networks, a “bad” scenario consists of a “bad” input and a “bad” adaptive adversary.

For dealing with “bad” inputs in dynamic networks, it is not hard to see that randomization can help to reduce the time complexity exponentially. For example, consider the two-party communication complexity (CC) problem Equality  [20]. Let m be the size of the input, then Equality has a randomized CC of \(O(\log m)\) bits, and a deterministic CC of \(\varOmega (m)\) bits  [20]. Under our setting of dynamic networks with congestion, this exponential gap in the CC of Equality directly translates to an exponential gap in the time complexity.

A Quick Conjecture? For dealing with “bad” adaptive adversaries, on the other hand, one may quickly conjecture that randomness has limited power: On the surface, since the randomness in round r is already visible to the adaptive adversary when it chooses the round-r topology, such randomness offers no help for better dealing with the round-r topology. But a deeper look shows that the randomness in round r could potentially help the algorithm to better deal with round-\(r'\) (\(1\le r'< r\)) topologies: Consider an example algorithm that uses the first \(r-1\) rounds to flood a certain token in the network, where \(r-1\) can be smaller than the network’s dynamic diameter d. Let S be the set of nodes that have received the token by the end of round \(r-1\). In round r and later, the algorithm may want to estimate the size of S (e.g., to estimate whether the token has reached some constant fraction of the nodes). The adaptive adversary can influence S, by manipulating the topologies in the first \(r-1\) rounds. But by the end of round \(r-1\), the set S will be fixed—effectively, the adaptive adversary has now committed to S. The algorithm’s randomness in round r and later is independent of S. Thus for the remainder of the algorithm’s execution (i.e., the part starting from round r), S can be viewed as a “midway input”. The randomness in the remainder of the algorithm’s execution can potentially help to better deal with such “midway inputs”, and hence help indirectly to better deal with the adaptive adversary’s “bad” behavior in the first \(r-1\) rounds.

Given such possibility, it is unclear whether the earlier quick conjecture holds or whether it may even be wrong. Resolving this will be our goal.

Our Results for LV Algorithms. As our main novel result, we prove that the earlier conjecture does hold, subject to some mild conditions on the algorithm’s time complexity. (We will fully specify these mild conditions later.) As one will see later, proving this conjecture is far from trivial. We first need to expose the power of randomization for dealing with adaptive adversaries, and in particular, to properly isolate such power from the power of randomization for dealing with inputs. It is not immediately obvious how to do this since the same randomness may be used for dealing with both inputs and adaptive adversaries. To this end, we define a simple notion of prophetic adversary for determining the dynamic network. A prophetic adversary first sees (accurately predicts) all coin flip outcomes of a randomized algorithm in all rounds, and then decides the dynamic network (i.e., topologies in each round). This enables a prophetic adversary to always choose the worst-case dynamic network for the given coin flip outcomes. Hence the randomness in the algorithm can never help to better deal with dynamic networks generated by “bad” prophetic adversaries.

Now let us consider adaptive adversaries that generate dynamic networks with at most n nodes and at most d dynamic diameter. Let P be any Las Vegas (LV) algorithm whose time complexity (under the worst-case among all such adaptive adversaries) is \(\text{ tc}_P(n,d)= \varTheta (f(n) \cdot g(d))\), for some f(n) and g(d) where there exists some constant a such that \(\varOmega (1)\le f(n) \le O(n^a)\) and \(\varOmega (d) \le g(d) \le O(d^a)\).^{Footnote 1}\(^,\)^{Footnote 2} We prove (Theorem 1 and 2) that P can always be converted into another LV algorithm Q whose time complexity under worst-case prophetic adversaries is \(O(\text{ polylog }(n))\cdot \text{ tc}_P(n,d)\). This means that even when the adversary accurately predicts all randomness in Q, Q’s time complexity is still only \(O(\text{ polylog }(n)) \cdot \text{ tc}_P(n,d)\). In turn, the benefit of randomization (in P) for dealing with the adaptive adversaries is at most to reduce the complexity by a \(O(\text{ polylog }(n))\) factor. This proves the earlier conjecture affirmatively (under the previous mild conditions).

The more general version (Theorem 2) of our results actually hold for P as long as P’s time complexity is upper bounded by some polynomial — namely, as long as there exists some constant a such that \(\varOmega (1) \le \text{ tc}_P(n,n) \le O(n^a)\), and without any other constraints on \(\text{ tc}_P(n,d)\). Here for any given LV algorithm P, we can construct another LV algorithm Q whose time complexity under prophetic adversaries is \(O((d \log ^3 n) \times \text{ tc}_P(n, a'\log n))\) for some constant \(a'\). Hence in this more general case, our results imply that the power of randomization (in P) for dealing with adaptive adversaries is at most a \(O(d \log ^3 n)\) multiplicative factor when \(d \ge a' \log n\).

Finally, the above shows that for dealing with adaptive adversaries, the power of randomization is inherently limited. This suggests that if an algorithm is not using randomness for better dealing with the inputs, we should be able to derandomize it efficiently. The full version  [13] of this paper shows how this can be done for LV algorithms.

Our Results for MC Algorithms. We have also obtained similar results for Monte Carlo (MC) algorithms. We defer the details to the full version  [13] of this paper, and provide a summary here. Consider any constant \(\epsilon \in (0, 1-\delta )\) and any \(\delta \)-error Monte Carlo (MC) algorithm P such that \(\text{ tc}_P(n,d)=\varTheta (f(n)\cdot g(d))\), where there exists some constant a such that \(\varOmega (n)\le f(n) \le O(n^a)\) and \(\varOmega (d) \le g(d) \le O(d^a)\). Then we can always construct another \((\delta +\epsilon )\)-error MC algorithm Q for solving the same problem and whose time complexity under worst-case prophetic adversaries is \(O(\text{ polylog }(n))\cdot \text{ tc}_P(n,d)\). A more general version of this result holds for P as long as there exists some constant a such that \(\varOmega (1) \le \text{ tc}_P(n,n) \le O(n^a)\), and without any other constraints on \(\text{ tc}_P(n,d)\). In this more general version, our algorithm Q will have a time complexity of \(O((d \log ^3 n) \times \text{ tc}_P(n, a'\log n) + n\log ^2 n)\).

Our Techniques. To obtain Q from P, we essentially need to “derandomize” the part of P’s randomness used to deal with the adaptive adversaries. It turns out that such randomness is less amenable to typical derandomization methods such as pairwise independence, conditional expectation, or network decomposition. This motivated us to take a rather different route from prior derandomization efforts  [5, 7, 8, 10, 11, 21, 22, 25].

Specifically, we will have Q simulate the execution of P against some adaptive adversary \(\alpha ^{\epsilon , t}\) that we construct. (Namely, Q simulates both P and \(\alpha ^{\epsilon , t}\).) To work against prophetic adversaries, Q will perform the simulation by only doing simple floodings. We will carefully design \(\alpha ^{\epsilon , t}\) so that: i) Q can efficiently simulate the execution of P against \(\alpha ^{\epsilon , t}\) via simple floodings, ii) the dynamic networks generated by \(\alpha ^{\epsilon , t}\) will have \(O(\log n)\) dynamic diameter with at least \(1-\epsilon \) probability, and iii) there are some sufficient conditions, which can be efficiently checked in a distributed fashion, for guaranteeing the \(O(\log n)\) dynamic diameter. Next, a central difficulty in the simulation is that Q does not know the dynamic diameter of the dynamic network over which it runs, which will cause various problems in the floodings. While Q can naturally use the standard doubling-trick to guess the dynamic diameter, the challenge is that Q cannot easily tell whether the guess is correct. As a result, we will carefully reason about the properties of the simulation when the guess is wrong, and design Q correspondingly.

Other Types of Adversaries. The adaptive adversaries in this paper (also called strongly adaptive adversaries  [2, 9, 16, 18]) are not the only type of adversaries in dynamic networks. A more general notion is z-oblivious adversaries  [1], which can see all randomness up to and including round \(r-z\) when deciding the round-r topology. Prophetic adversaries and strongly adaptive adversaries correspond to z-oblivious adversaries with \(z=-\infty \) and \(z= 0\), respectively. Researchers have also considered 1-oblivious adversaries (also called weakly adaptive adversaries  [9, 12]) and \(\infty \)-oblivious adversaries (also called oblivious adversaries  [2, 3, 12]). The results in this paper are only for 0-oblivious adversaries, but our proofs are already non-trivial. The power of the algorithm’s randomization will likely increase as z increases. On the other hand, we suspect that our conjecture could potentially be extended to 1-oblivious adversaries — we leave this to future work.

Related Work. Randomization has been extensively used for solving various specific problems in dynamic networks (e.g., [17, 19]). However, prior works have not focused on the power of randomization in general distributed algorithms in dynamic networks. On the other hand, there have been many works on the power of randomization in other settings, and we discuss the most relevant ones in the following.

In centralized setting, an online algorithm processes a sequence of requests, one by one. In this context, an adaptive adversary generates the i-th request after seeing the algorithm’s behavior (and coin flips) on request 1 through \(i-1\). It is well-known  [5] that randomized online algorithms against adaptive adversaries can always be effectively derandomized. However, the measure of goodness for online algorithms is competitive ratio, and hence the derandomized algorithm can afford to have exponential computational complexity. In our distributed setting, adopting the techniques from [5] would require us to collect all the n input values to one node, which would result in unbounded time complexity (i.e., number of rounds) since the sizes of our inputs are not constrained. Due to these fundamental differences, our results and techniques are all quite different from  [5].

More recently, there have been a series of breakthrough results on derandomizing distributed algorithms in static networks  [7, 8, 10, 11, 15, 22]. These derandomization results are all for local algorithms, where the output (or the correctness of the output) of a node only depends on its small neighborhood instead of on the entire network. In fact, many of them consider algorithms with O(1) time complexity. Such a notion of local algorithms is perhaps no longer well-defined in dynamic networks, where a node’s neighborhood changes over time. In comparison to these works, this paper considers i) general distributed algorithms that are not necessarily local, and ii) dynamic networks instead of static networks. Also because of this, our results and techniques are all quite different. For example, some of the key methods used in [7, 8, 10, 11, 15, 22] include network decomposition and conditional expectations, while we mainly rely on a novel simulation against a novel adaptive adversary.

Dynamic Network and Adversary. We consider a synchronous network with a fixed set of n nodes, where the nodes proceed in lock-step rounds. Throughout this paper, we assume that n is publicly known and that \(n\ge 2\). All nodes start execution, simultaneously, from round 1. The nodes have unique ids from 0 through \(n-1\). Each node has some input value, and there is no constraint on the size of each input value. We will view the n input values as an input vector of length n. We consider general distributed computing problems where the n nodes aim to compute a certain function of the input vector. The output of the function is a vector of length n, where node i should output the \((i+1)\)-th entry in that vector. There is no constraint on the size of each output entry. An algorithm in this paper always refers to some algorithm for solving some problem that can be modeled as the above way.

The topology among the n nodes may change from round to round. Following [16, 18, 26], we assume that the topology is determined by some adaptive adversary. An adaptive adversary \(\tau \) is an infinite sequence of functions \(\tau _r(P, I, C_{[1:r]})\) for \(r \ge 1\). Here \(\tau _r\) takes as parameters the randomized algorithm P, the input vector I, and P’s coin flip outcomes \(C_{[1:r]}\) in round 1 (inclusive) to round r (inclusive). The function \(\tau _r\) then outputs some connected and undirected graph with n nodes, as the topology of the network in round r. There is no other constraint on the graph. We also call this infinite sequence of graphs (starting from round 1) as a dynamic network, and say that \(\tau \) is an adaptive adversary with n nodes. With a slight abuse of notation, we use \(\tau (P, I, C)\) to denote the dynamic network produced by \(\tau \), under algorithm P, input vector I, and P’s coin flip outcomes C across all rounds. (This is a slight abuse since \(\tau \) is not a function.) For any given dynamic network \(G = G_1 G_2 \ldots \) where \(G_r\) is the round-r topology of G, we define the special adaptive adversary \(\gamma ^G\) to be \(\gamma ^G_r(P, I, C_{[1:r]}) = G_r\) for all r, P, I, and \(C_{[1:r]}\). A prophetic adversary \(\psi \) is a function mapping the tuple (P, I, C) to a dynamic network \(H = \psi (P, I, C)\). Since \(\psi \) is a single function (instead of a sequence of functions), \(\psi \) can see all coin flip outcomes of P in all rounds (i.e., C), before deciding the topology in each round.

We follow the communication model in [14, 26]: In each round, a node may choose to either send an \(O(\log n)\) size message (i.e., the broadcast \(\mathcal {CONGEST}\) model  [24]) or to receive, as determined by the algorithm running on that node. A message sent in round r is received, by the end of round r, by all the receiving neighbors of the sender in round r.

Diameter. We adopt the standard notion of dynamic diameter  [18] (or diameter in short) for dynamic networks. Formally, we define \((u, r) \rightarrow (v, r+1)\) if either \(u=v\) or v is u’s neighbor in round r. Let the relation “\(\leadsto \)” be the transitive closure of “\(\rightarrow \)”. The diameter is defined as the smallest d such that \((u, r) \leadsto (v, r+d)\) holds for all u, v, and \(r\ge 1\). Trivially, the diameter of a dynamic network with n nodes is at most \(n-1\). Since the diameter is controlled by the adversary, it is not known to the algorithm beforehand. The diameter of an adaptive adversary \(\tau \) (prophetic adversary \(\psi \)) is the smallest d where the diameter of \(\tau (P, I, C)\) (\(\psi (P, I, C)\)) is at most d for all P, I, and C.

Time Complexity and Error. For the time complexity of an execution, we define the function \(\text{ tc }(P, I, \tau , C)\) to be the number of rounds needed for all nodes to output in P, when algorithm P runs with input vector I, adaptive adversary \(\tau \), and coin flip outcomes C. For the error of an execution, we define the binary function \(\text{ err }(P, I, \tau , C)\) to be 1 iff P’s output is wrong (on any node), when P runs with I, \(\tau \), and C.

In the following, \(\max _{\tau }\) will be taken over all adaptive adversaries \(\tau \) with at most n nodes and at most d diameter. Unless otherwise specified, an algorithm in this paper can be either a Las Vegas (LV) algorithm or a Monte Carlo (MC) algorithm. We define a randomized algorithm P’s time complexity against adaptive adversaries as \(\text{ tc}_P(n,d) = \max _I \max _{\tau } E_C[\text{ tc }(P, I, \tau , C)]\) if P is an LV algorithm, or \(\text{ tc}_P(n,d) = \max _I \max _{\tau } \max _C \text{ tc }(P, I, \tau , C)\) if P is an MC algorithm. We define an MC algorithm P’s error against adaptive adversaries as \(\text{ err}_P(n) = \max _I \max _d \max _{\tau } E_C[\text{ err }(P, I, \tau , C)]\).

We will need to reason about the properties of algorithm Q running against prophetic adversaries. Given Q’s coin flip outcomes C in all rounds, since prophetic adversaries always see C beforehand, the worst-case prophetic adversary can always choose the worst-case dynamic network H for such C. Hence if Q is an LV algorithm, we define its time complexity against prophetic adversaries to be \(\text{ tc}^*_Q(n,d) = \max _I E_C[\max _H \text{ tc }(Q, I, \gamma ^H, C)]\). Note that here \(\max _H\) is taken after C is given, and is taken over all dynamic networks with at most n nodes and at most d diameter. If Q is an MC algorithm, then its time complexity/error against prophetic adversaries will be \(\text{ tc}^*_Q(n,d) = \max _I \max _C \max _H \text{ tc }(Q, I, \gamma ^H, C)\) and \(\text{ err}^*_Q(n) = \max _I E_C [\max _d \max _{H} \text{ err }(Q, I, \gamma ^H, C)]\), respectively.

Conventions. All logarithms in this paper are base 2. We sometimes consider round 0 for convenience, where the algorithm does nothing and all nodes are receiving.

As mentioned in Sect. 1, given some arbitrary randomized algorithm P, we want to construct algorithm Q that simulates the execution of P against some novel adaptive adversary \(\alpha ^{\epsilon ,t}\). We want \(\alpha ^{\epsilon ,t}\) to have small diameter so that P’s time complexity (when running against \(\alpha ^{\epsilon ,t}\)) is small. Let H be the dynamic network over which Q runs. We further need Q to have good complexity and error guarantees, even if H is constructed by prophetic adversaries.

3.1 Intuition

Starting Point. Recall that in any given round r, an adaptive adversary knows whether each node in P will be sending or receiving in that round (since the adaptive adversary sees \(C_r\)), before the adversary decides the topology in that round. Let us consider the following trivial topology as a starting point. In this topology, all nodes that are sending in the round form a clique, and all nodes that are receiving in the round form a clique. Some of the sending nodes will be chosen as centers for that round. A center will be connected to all other nodes (including all other centers) directly. To simulate P for one round over such a topology, we only need to deliver the message sent by each center to each of the receiving nodes. To do so, for each center, Q will flood the message (sent by the center) in the dynamic network H. Such flooding will obviously still work even if H is generated by a prophetic adversary. It takes total \(d\cdot x\) rounds to simulate one round of P, where x is the number of centers and d is the diameter of H.

But there are several issues. Since only sending nodes can be centers and since a node may not always be sending in all rounds, we may be forced to keep switching the centers from round to round. This may then cause the (dynamic) diameter of the dynamic network to be large, despite the topology in each round having a small static diameter. One naive way to avoid this problem is to choose all sending nodes as centers. But doing so would result in too many centers, rendering the simulation inefficient. The following explains how we overcome these issues.

Choosing the Centers. Our design of \(\alpha ^{\epsilon ,t}\) uses only a logarithmic number of centers in each round. To obtain some intuition, consider any two consecutive rounds \(r-1\) and r, where \(r \ge 3\). We define \(A_r^{RS} = \{u\,\,|\,\, u\) receives (hence the superscript “\(^R\)”) in round \(r-1\) and sends (hence the superscript “\(^S\)”) in round \(r \}\). Here “sends”/“receives” refers to u sending/receiving in the execution of P against \(\alpha ^{\epsilon ,t}\). We similarly define the remaining three sets \(A_r^{SS}\), \(A_r^{SR}\), and \(A_r^{RR}\). We hope to choose the centers in such a way that for some small d (e.g., \(O(\log n)\)), we have \((u, r-1)\leadsto (v,r+d-1)\) for all u and v. We will soon see that it will be convenient to consider u’s in the 4 sets seperately.

For round r, we will first pick some (arbitrary) node \(w\in A_r^{RS}\) as a center. Such a center will ensure that for all \(u\in A_r^{RS}\) and all v, we have \((u,r-1)\rightarrow (w, r) \rightarrow (v, r+1)\). Similarly, we will pick some (arbitrary) node \(w\in A_r^{SS}\) as another center, to take care of \(u\in A_r^{SS}\). Next, for any \(u\in A_r^{SR}\), note that u must be in either \(A_{r-1}^{RS}\) or \(A_{r-1}^{SS}\). If we chose the centers in round \(r-1\) also according to the earlier rules, then such a u has already been taken care of as well.

The Trickier Case. The case for \(u\in A_r^{RR}\) is trickier. In fact, to get some intuition, consider a node u that continuously receives in round 1 through round d. We want to ensure that \((u,1)\leadsto (v, d+1)\) for all v. Let \(S_r\) be the set of nodes that are sending in round r and let \(W_r\) be the set of centers in round r, for \(1\le r\le d\). For all \(v\in \cup _r W_r\), we clearly have \((u,1)\leadsto (v, d+1)\). For all \(v\notin \cap _r S_r\), v must be receiving in some round \(i\in [1,d]\), and hence we have \((u,i)\rightarrow (v, i+1)\) and we are done.

The case for \(v\in (\cap _r S_r)\setminus (\cup _r W_r)\) is more complicated. Such a v has always been sending, but is never chosen as a center. Now consider such a v, and observe that if some center w in round r sends (again) in some round i where \(r+1\le i\le d\), then we must have \((u,1)\leadsto (w, r)\leadsto (w, i)\rightarrow (v, i+1)\leadsto (v, d+1)\). Based on this observation, we will want to choose \(W_r\) from \(S_r\) such that some node in \(W_r\) will send in some round \(i\ge r+1\). But whether a node sends in future rounds may depend on future coin flip outcomes of P, as well as the incoming messages in those rounds. An adaptive adversary (for P) does not have the incoming messages in future rounds. It is not supposed to see future coin flip outcomes either.

Our next observation is that the adaptive adversary in round r, before deciding the round-r topology, can actually determine the probability that a node u will be sending (again) in round \(r+1\), if the node u is currently already sending in round r. The reason is that u will not receive any incoming messages in round r, no matter what the topology is. Hence the probability is uniquely determined by u’s state at the beginning of round r. Now given such probabilities for all the nodes in \(S_r\), when choosing the centers, we will choose those nodes from \(S_r\) whose probabilities (of sending in round \(r+1\)) are at least 0.5, and we call such nodes as promising nodes. If we include logarithmic number of promising nodes in \(W_r\), then with good probability, there will exist some \(w \in W_r\) that sends in round \(r+1\). Due to some technicality, the number of promising nodes in \(W_r\) will actually need to increase with r, so that we can eventually take a union bound across even infinite number of rounds.

Finally, it is possible that we never have a sufficient number (i.e., logarithmic number) of promising nodes. In such a case, we will show that \((\cap _r S_r)\setminus (\cup _r W_r)\) will be empty with good probability.

3.2 Our Novel Adaptive Adversary \(\alpha ^{\epsilon ,t}\)

We now formally define \(\alpha ^{\epsilon ,t}\) for \(0< \epsilon < 1\) and \(t\ge 1\). The adaptive adversary \(\alpha ^{\epsilon ,t}\) always generates a clique as the topology for round r when \(r> t\). If \(r \le t\), then consider the given algorithm P, input vector I, and coin flip outcomes \(C_{[1:r]}\). Based on \(C_r\) and the state of P at the beginning of round r, \(\alpha ^{\epsilon ,t}\) can infer which nodes will be sending in round r, and which nodes are promising nodes. For all pairs of nodes u and v where either they are both sending in round r or they are both receiving in round r, the adversary \(\alpha ^{\epsilon ,t}\) adds an undirected edge between them. Next \(\alpha ^{\epsilon ,t}\) chooses up to \((2\log \frac{2r}{\epsilon }+3)\) nodes as centers for round r. For every center w and every node v, \(\alpha ^{\epsilon ,t}\) adds an edge between w and v, if there is not already such an edge.

The centers are chosen in the following way. First, among all the nodes that were receiving in round \(r-1\) and are sending in round r, if there are such nodes, choose the one with the smallest id as a center. Second, among all the nodes that were sending in round \(r-1\) and are again sending in round r, if there are such nodes, choose the one with the smallest id as a center. Third, among all the nodes that were centers in round \(r-1\) and are sending in round r, if there are such nodes, choose the one with the smallest id as a center. Finally, rank all the promising nodes in round r, by their ids from smallest to largest. Choose the first \(2\log \frac{2r}{\epsilon }\) nodes from this sequence as centers. If the sequence contains less than \(2\log \frac{2r}{\epsilon }\) nodes, choose all of them. Since these 4 criteria are not necessarily exclusive, a node may be chosen as a center multiple times.

One can easily verify that the topology generate by \(\alpha ^{\epsilon ,t}\) in each round is always connected. We will be able to eventually prove (see proof in the full version  [13] of this paper) that with probability at least \(1-\epsilon \), the dynamic network generated by the adversary \(\alpha ^{\epsilon ,t}\) has a diameter of at most \(8\log \frac{8tn}{\epsilon }\).

4.1 Pseudo-code and Intuition

Overview. Given any LV algorithm P, our algorithm Q (pseudo-code in Algorithm 1) will simulate the execution of P against \(\alpha ^{\epsilon ,t}\). (Effectively, Q will be simulating both P and the adversary \(\alpha ^{\epsilon ,t}\).) We will ensure that Q works even against prophetic adversaries. In the following, a simulated round refers to one

round of P in its simulated execution. Recall that in each simulated round, \(\alpha ^{\epsilon ,t}\) chooses \(O(\log \frac{r}{\epsilon })\) centers. For each center, Q will do a binary search (via logarithmic number of sequential floodings) to find the id of that center. For example, for the first center, Q will use a binary search to find the node with the smallest id, among all nodes that were receiving in the previous simulated round and are sending in the current simulated round. Next, for each center (which must be sending in P for the current simulated round), Q will determine the message it should send in P. Q will then flood this message, and then feed this message into all nodes that are receiving in P for the current simulated round.

Challenges and Our Solutions. A key difficulty in the above simulation is that Q does not know the diameter d of the dynamic network over which it runs. This means that Q does not know how long it takes for each flooding to complete. Of course, Q can naturally use the standard doubling-trick and maintains a guess \(d'\) for d. Recall that Q uses flooding i) for finding the centers via binary searches, and ii) for disseminating the messages of the centers. When \(d'<d\), obviously both steps can be incorrect. We need to design Q so that it can deal with such incorrect behavior.

As a starting point, for each binary search, we have a designated node (node 0) flood for \(d'\) rounds its result of the binary search. If a node does not see such flooding from node 0, or if its binary search result is different, it knows that something is wrong and flags itself. Next for each center in this list, if it is not flagged, it will flood the message (that it should send in P) for \(d'\) rounds. Again, whoever not seeing this flooding will flag itself. In our design, once a node gets flagged, it will not participate in any of the flooding or binary search any more (for the current \(d'\) value), but will nevertheless spend the corresponding number of rounds doing nothing, so that it remains “in sync” with the non-flagged nodes.

At this point, we have three possibilities: i) \(d'\ge d\) and no node gets flagged, ii) \(d' < d\) and no node gets flagged, iii) \(d' < d\) and some nodes get flagged. For the second case, because \(d' < d\), it is not immediately clear what guarantees the simulation can offer — for example, whether the binary search still finds the smallest id. Fortunately, we will be able to prove that as long as no node gets flagged, the simulation is still “correct”. Specifically, for disseminating the centers’ messages, it is obvious that if no node gets flagged, then all nodes must have received those messages, regardless of whether \(d' < d\). For the binary search part, we will be able to prove the following strong property: As long as the binary search returns the same value on all nodes (which is a necessary condition for no nodes being flagged), the result of the binary search must be correct, even if \(d' < d\). Putting these together, this means that the second case still corresponds to a proper execution of P against \(\alpha ^{\epsilon ,t}\).

The third case (i.e., \(d' < d\) and some nodes get flagged) is trickier. The challenge is that the non-flagged nodes may think everything is fine and then happily generate a potentially wrong output. To deal with this, our design first lets the flagged nodes send a special message — whoever receives this message will get flagged as well. For each simulated round of P, our algorithm Q will allocate exactly one dedicated round in Q to do this.

Next, as a key technical step, we will be able to prove that with such a mechanism, somewhat interestingly, those non-flagged nodes actually still constitute part of a valid execution of P against some prophetic adversary \(\psi \) (but not a valid execution of P against \(\alpha ^{\epsilon ,t}\)). Our proof will explicitly construct this prophetic adversary \(\psi \). Let G be the dynamic network generated by \(\psi \). We will prove that G’s topology is always connected in every round, while leveraging the fact that the topology of the dynamic network H (over which Q runs) is always connected. It is important to note that here we need to use a prophetic adversary (instead of an adaptive adversary) to generate G, since G depends on H, and since H is generated by some prophetic adversary.

To quickly summarize, we effectively have that i) if no node gets flagged, then Q must have properly simulated P’s execution against \(\alpha ^{\epsilon ,t}\), and ii) if some nodes get flagged, then Q (on the non-flagged nodes) must have properly simulated P’s execution against some prophetic adversary \(\psi \). Now since P is an LV algorithm, it will never have any error when running over any G, even if G is generated by a prophetic adversary. The reason is that G could also be generated by some adaptive adversary (e.g., by the adaptive adversary that always outputs G, regardless of P’s inputs and P’s coin flip outcomes), and P promises zero error under all adaptive adversaries. Thus the outputs of those non-flagged nodes will never be wrong, and can always be safely used. Of course, P’s time complexity guarantee will no longer hold when running against \(\psi \). But this will not cause any problem—if P takes too long to output, Q will increase \(d'\) and retry.

Using Fresh Coins. Finally, since we are using the doubling-trick to guess d already, we will use the same trick to guess the number of rounds needed for P to output. This will make our proof on Q a constructive proof, instead of an existential proof. It is worth mentioning that for each \(d'\) (the guess on d) and t (the guess on the number of simulated rounds needed for P to output), Q will simulate P using a fresh set of random coins. This is necessary because for a given set of coin flip outcomes, the adversary \(\alpha ^{\epsilon ,t}\) may happen to have large diameter, causing P to take too many rounds to output. Finally, for each pair of \(d'\) and t values, the simulation of P takes about \(d't\log t\) rounds. To make the guessing process efficient, we maintain a budget k that keeps doubling. For a given budget k, we simulate P for all (\(d'\), t) pairs where \(d't\log t \le k\) and that are constant factors apart from each other.

4.2 Final Results

Theorem 1 next states that Q’s output will never be wrong. Its proof (in the full version  [13] of this paper) mainly relies on the intuition in the previous section. The proof is involved, because it is not sufficient to just consider whether a node is flagged at a certain time point in each simulated round — we actually consider two separate time points in each simulated round.

Theorem 1

For any LV algorithm P, the output of Q (Algorithm 1) will never be wrong.

Theorem 2 next (see [13] for the proof) is our final result on Q’s time complexity, when Q runs against a prophetic adversary.

Theorem 2

Let Q be Algorithm 1, and let P be any LV algorithm where \(\varOmega (1)\le \text{ tc}_P(n,n) \le O(n^{a_1})\) for some constant \(a_1\).

• There exists constant \(a'\) (independent of n) such that for all d, we have \(\text{ tc}^*_Q(n,d) = \max _I E_C[\max _H \text{ tc }(Q, I, \gamma ^H, C)] = d\cdot O(\log ^3 n \times \text{ tc}_P(n, a'\log n))\), where \(\max _H\) is taken over all dynamic networks H with at most n nodes and at most d diameter.

• If  \(\text{ tc}_P(n,d)= \varTheta (f(n) \cdot g(d))\) for some f(n) and g(d) where there exists some constant \(a_2\) such that \(\varOmega (1)\le f(n) \le O(n^{a_2})\) and \(\varOmega (d) \le g(d) \le O(d^{a_2})\), then we have \(\text{ tc}^*_Q(n,d) = O(\text{ polylog }(n))\cdot \text{ tc}_P(n,d)\).