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.
There has been extensive work on analyzing overlay networks under high adversarial churn. As already mentioned in the introduction, these works had a variety of different model assumptions. See @cite_6 for a comprehensive survey on previous results. In the following, we only concentrate on works closely related to our work.
@cite_6
2885215273
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.