We investigate the maintenance of overlay networks under massive churn where an adversary may churn a constant fraction an of nodes over the course of O(log(n)) rounds. In particular, the adversary has an almost up-to-date information of the network topology as it can observe an only slightly outdated topology that is at least 2 rounds old. Other than that, we only have the provably minimal restriction that new nodes can only join the network via nodes that have taken part in the network for at least one round. Our contributions are as follows: First, we show that it is impossible to maintain a connected topology if the adversary has up-to-date information about the nodes' connections. As our main result, we present an algorithm that constructs a new overlay — completely independent of all previous overlays — every 2 rounds. Furthermore, each node sends and receives only O(log^3(n)) messages in each round. As part of our solution, we propose the Linearized DeBruijn Swarm (LDS), a highly churn resistant overlay, which will be maintained by the algorithm. However, our approaches can be transferred to a variety of classical P2P topologies where nodes are mapped into the [0, 1)-interval.
Last, the @math framework presented in @cite_6 probably bears the greatest resemblance with our work. In @math the nodes maintain a logical overlay resembling a butterfly network. To ensure robustness each of the butterfly's virtual nodes is simulated by @math nodes. The key difference between our work and @math is the adversary's lateness. Just as @cite_2 @math assumes the adversary to be ( @math , @math )-late, but in return allows the churn to be as high as @math in @math rounds. However, other than @cite_2 @math allows the adversary to be immediate.
@cite_6 @cite_2
2885215273 2466856313
A Peer-to-Peer (P2P) network is a dynamic collection of nodes that connect with each other via virtual overlay links built upon an underlying network (usually, the Internet). Typical P2P networks are highly dynamic and can experience very heavy churn, i.e., a large number of nodes join leave the network every time step. We present an overlay framework called Sparse Robust Addressable Network (Spartan) that can tolerate heavy adversarial churn. We show that Spartan can be built efficiently in a fully distributed manner within O(log n) rounds. Furthermore, the Spartan overlay structure can be maintained, again, in a fully distributed manner despite adversarially controlled churn (i.e., nodes joining and leaving) and significant variation in the number of nodes. When the number of nodes in the network lies in [n, fn] for any fixed f > 1 the adversary can remove up to ?n nodes and add up to ? n nodes (for some small but fixed ? > 0) within any period of P rounds for some P ? O(log log n). Moreover, the adversary can add or remove nodes from the network at will and without any forewarning. Despite such uncertainty in the network, Spartan maintains ?(n log n) committees that are stable and addressable collections of ?(log n) nodes each. Any node that enters the network will be able to gain membership in one of these committees within O(1) rounds. The committees are also capable of performing sustained computation and passing messages between each other. Thus, any protocol designed for static networks can be simulated on Spartan with minimal overhead. This makes Spartan an ideal platform for developing applications. All our results hold with high probability. We present three robust overlay networks: First, we present a network that organizes the nodes into an expander and is resistant to even massive adversarial churn. Second, we develop a network based on the hypercube that maintains connectivity under adversarial DoS-attacks. For the DoS-attacks we use the notion of a Ω(log log n)-late adversary which only has access to topological information that is at least Ω(log log n) rounds old. Finally, we develop a network that combines both churn- and DoS-resistance. The networks gain their robustness through constant network reconfiguration, i.e., the topology of the networks changes constantly. Our reconfiguration algorithms are based on node sampling primitives for expanders and hypercubes that allow each node to sample a logarithmic number of nodes uniformly at random in O(log log n) communication rounds. These primitives are specific to overlay networks and their optimal runtime represents an exponential improvement over known techniques. Our results have a wide range of applications, for example in the area of scalable and robust peer-to-peer systems.