This paper considers standard T-interval dynamic networks, where the N nodes in the network proceed in lock-step rounds, and where the topology of the network can change arbitrarily from round to round, as determined by an adversary. The adversary promises that in every T consecutive rounds, the T (potentially different) topologies in those T rounds contain a common connected subgraph that spans all nodes. Within such a context, we propose novel algorithms for solving some fundamental distributed computing problems such as Count/Consensus/Max. Our algorithms are the first algorithms whose complexities do not contain an Ømega(N) term, under constant T values. Previous sublinear algorithms require significantly larger T values.

We consider standard T-interval dynamic networks, under the synchronous timing model and the broadcast CONGEST model. In a T-interval dynamic network, the set of nodes is always fixed and there are no node failures. The edges in the network are always undirected, but the set of edges in the topology may change arbitrarily from round to round, as determined by some adversary and subject to the following constraint: For every T consecutive rounds, the topologies in those rounds must contain a common connected spanning subgraph. Let Hr to be the maximum (in terms of number of edges) such subgraph for round r through r+T-1. We define the backbone diameter d of a T-interval dynamic network to be the maximum diameter of all such Hr's, for r ≥ 1. We use n to denote the number of nodes in the network.

This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel $$\varOmega (d + \text{ poly }(m))$$ lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial $$\varOmega (d)$$ lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a $$\text{ poly }(m)$$ term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider that communication complexity problem with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain “non-critical” information about the problem instance that they are solving.

In a sybil attack, an adversary creates many fake identities/nodes and have them join the system. Computational puzzles have long been investigated as a possible sybil defense: nodes that fail to solve the puzzle in time will no longer be accepted by other nodes. However, a malicious node can behave in such a way that it is accepted by some honest nodes but not other honest nodes. This results in different honest nodes having different views on which set of nodes constitute the system. Such view divergence, unfortunately, breaks the overarching assumption required by many existing security protocols. Partly spurred by the growing popularity of Bitcoin, researchers have recently formalized the above view divergence problem and proposed interesting solutions (which we call view reconciliation protocols). All existing view reconciliation protocols so far have a similar Θ(N) time complexity, with N being the number of honest nodes in the system. As this paper's main contribution, we propose a novel view reconciliation protocol whose time complexity is only Θ(ln N/ln ln N). To achieve such an exponential improvement, we aggressively exploit randomization. The hidden constant factor in the asymptotic complexity of our protocol, however, is considerably larger than in previous protocols. Concrete numerical comparisons show that our protocol is more suitable for large-scale systems, while existing protocols are better for smaller-scale systems.

In a sybil attack, an adversary creates a large number of fake identities/nodes and have them join the system. Computational puzzles have long been investigated as a possible sybil defense: If a node fails to solve the puzzle in a timely fashion, it will no longer be accepted by other nodes. However, it is still possible for a malicious node to behave in such a way that it is accepted by some honest nodes but not other honest nodes. This results in different honest nodes having different views on which set of nodes should form the system. Such view divergence, unfortunately, breaks the overarching assumption required by many existing security protocols. Partly spurred by the growing popularity of Bitcoin, researchers have recently formalized the above view divergence problem and proposed interesting solutions (which we call view reconciliation protocols). For example, in CRYPTO 2015, Andrychowicz and Dziembowski proposed a view reconciliation protocol with Θ(N) time complexity, with N being the number of honest nodes in the system. All existing view reconciliation protocols so far have a similar Θ(N) time complexity. As this paper's main contribution, we propose a novel view reconciliation protocol with a time complexity of only Θ([ln N/ln ln N]). To achieve such an exponential improvement, we aggressively exploit randomization.

For dynamic networks with unknown diameter , we prove novel lower bounds on the time complexity of a range of basic distributed computing problems. Together with trivial upper bounds under dynamic networks with known diameter for these problems, our lower bounds show that the complexities of all these problems are sensitive to whether the diameter is known to the protocol beforehand: Not knowing the diameter increases the time complexities by a large poly( N ) factor as compared to when the diameter is known, resulting in an exponential gap. Our lower bounds are obtained via communication complexity arguments and by reducing from the two-party D isjointness CP problem. We further prove that sometimes this large poly( N ) cost can be completely avoided if the protocol is given a good estimate on N . In other words, having such an estimate makes some problems no longer sensitive to unknown diameter.

This paper considers several closely-related problems in synchronous dynamic networks with oblivious adversaries, and proves novel Omega(d + poly(m)) lower bounds on their time complexity (in rounds). Here d is the dynamic diameter of the dynamic network and m is the total number of nodes. Before this work, the only known lower bounds on these problems under oblivious adversaries were the trivial Omega(d) lower bounds. Our novel lower bounds are hence the first non-trivial lower bounds and also the first lower bounds with a poly(m) term. Our proof relies on a novel reduction from a certain two-party communication complexity problem. Our central proof technique is unique in the sense that we consider the communication complexity with a special leaker. The leaker helps Alice and Bob in the two-party problem, by disclosing to Alice and Bob certain "non-critical" information about the problem instance that they are solving.

For dynamic networks with unknown diameter, we prove novel lower bounds on the time complexity of a range of basic distributed computing problems. Together with trivial upper bounds under dynamic networks with known diameter for these problems, our lower bounds show that the complexities of all these problems are sensitive to whether the diameter is known to the protocol beforehand: Not knowing the diameter increases the time complexities by a large poly(N) factor as compared to when the diameter is known, resulting in an exponential gap. Here N is the number of nodes in the network. Our lower bounds are obtained via communication complexity arguments and by reducing from the two-party DisjointnessCP problem. We further prove that sometimes this large poly(N) cost can be completely avoided if the protocol is given a good estimate of N. In other words, having such an estimate makes some problems no longer sensitive to unknown diameter.