--- res: bibo_abstract: - "We investigate the maintenance of overlay networks under massive churn, i.e.\r\nnodes joining and leaving the network. We assume an adversary that may churn a\r\nconstant fraction $\\alpha n$ of nodes over the course of $\\mathcal{O}(\\log n)$\r\nrounds. In particular, the adversary has an almost up-to-date information of\r\nthe network topology as it can observe an only slightly outdated topology that\r\nis at least $2$ rounds old. Other than that, we only have the provably minimal\r\nrestriction that new nodes can only join the network via nodes that have taken\r\npart in the network for at least one round.\r\n Our contributions are as follows: First, we show that it is impossible to\r\nmaintain a connected topology if adversary has up-to-date information about the\r\nnodes' connections. Further, we show that our restriction concerning the join\r\nis also necessary. As our main result present an algorithm that constructs a\r\nnew overlay- completely independent of all previous overlays - every $2$\r\nrounds. Furthermore, each node sends and receives only $\\mathcal{O}(\\log^3 n)$\r\nmessages each round. As part of our solution we propose the Linearized DeBruijn\r\nSwarm (LDS), a highly churn resistant overlay, which will be maintained by the\r\nalgorithm. However, our approaches can be transferred to a variety of classical\r\nP2P Topologies where nodes are mapped into the $[0,1)$-interval.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: Thorsten foaf_name: Götte, Thorsten foaf_surname: Götte foaf_workInfoHomepage: http://www.librecat.org/personId=34727 - foaf_Person: foaf_givenName: Vipin Ravindran foaf_name: Vijayalakshmi, Vipin Ravindran foaf_surname: Vijayalakshmi - foaf_Person: foaf_givenName: Christian foaf_name: Scheideler, Christian foaf_surname: Scheideler foaf_workInfoHomepage: http://www.librecat.org/personId=20792 dct_date: 2019^xs_gYear dct_language: eng dct_publisher: IEEE@ dct_title: Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary@ ...