Bi-Weekly Talk: Always be Two Steps Ahead of Your Enemy

Mittwoch, 20.03.2019, 10.30 Uhr

Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9u10

Vortragender: 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.