Bi-Weekly Talk: Always be Two Steps Ahead of Your Enemy
Wednesday, March 20, 2019, 10:30am
Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10
Speaker: Vipin Ravindran Vijayalakshmi
Always be Two Steps Ahead of Your Enemy
We investigate the maintenance of overlay networks under massive churn where an adversary may churn a constant fraction alpha*n 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 adversary has up-to-date information about the nodes' connections. As our main result 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 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.