Götte, Thorsten
Thorsten
Götte
Vijayalakshmi, Vipin Ravindran
Vipin Ravindran
Vijayalakshmi
Scheideler, Christian
Christian
Scheideler
Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary
IEEE
2019
2019-01-24T18:53:11Z
2019-01-26T16:09:39Z
conference
https://ris.uni-paderborn.de/record/6976
https://ris.uni-paderborn.de/record/6976.json
638020 bytes
application/pdf
We investigate the maintenance of overlay networks under massive churn, i.e.
nodes joining and leaving the network. We assume an adversary that may churn a
constant fraction $\alpha n$ of nodes over the course of $\mathcal{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. Further, we show that our restriction concerning the join
is also necessary. 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 $\mathcal{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.