Paper Info
Title
Always be Two Steps Ahead of Your Enemy
Abstract
We investigate the maintenance of overlay networks under massive churn where an adversary may churn a constant fraction αn of nodes over the course of O(logn) 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> 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.
Year
DOI
Venue
2018
10.1109/IPDPS.2019.00114
2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
Keywords
Field
DocType
Peer to peer computing, Robustness , Overlay networks,Network topology
Discrete mathematics,Binary logarithm,Swarm behaviour,Computer science,Network topology,Adversary,Overlay,Overlay network,Distributed computing
Journal
Volume
ISSN
ISBN
abs/1810.07077
1530-2075
978-1-7281-1247-3
Citations 
PageRank 
References 
0
0.34
8
Authors
3
Name
Order
Citations
PageRank
Thorsten Götte101.01
Vipin Ravindran Vijayalakshmi200.34
Christian Scheideler31729152.71