Abstract

Large-scale dynamic distributed systems such as peer-to-peer (P2P) systems impose a set of diverse requirements on the churn management strategies. Current P2P solutions do commonly only address a subset of these requirements. Thus, there are a number of trade-offs and constraints that remain open. For instance, low-degree networks are often criticized in the literature for becoming a collection of unconnected subsets of nodes under targeted attacks. However, if a small fraction of nodes in a large-degree network is deleted, then the whole network suffers and often collapses from these collective failures. Additionally, the trade-off between the retransmission's frequency of KEEPALIVE messages, the number of generated control overhead, and the failure detection time is a highly challenging issue in dynamic distributed systems like P2P. This paper proposes a churn-resistant strategy designed on top of a highly reliable overlay network \cite{HiPeer-NCA}, with degree $2\Delta+2$, where $\Delta$ is the degree of a De Bruijn digraph \cite{De_Bruijn}. We show that when each node in the network periodically retransmits only one KEEPALIVE message to one of its neighbor in the network, any node's failure can be detected within an optimal timeout value $\mathit{Tout = \frac{AVG}{2} + 4 \times VAR,}$ where $\mathit{AVG}$ is the observed average round-trip time and $\mathit{VAR}$ is the observed mean variance of that time. As a major contribution, we demonstrate that even in failure situation the lookup of any available resource is achieved with the lowest possible maintenance overhead $O(1)$ along the shortest path of length $D_{CMR} = \log_{\Delta}(N(\Delta-1)+\Delta) - 1$ with $N$ as the maximal number of nodes in the network.