Fighting erosion in dynamic large-scale overlay networks

Overlay management protocols have been introduced to guarantee overlay network connectivity in dynamic large-scale peer-to-peer systems. Some of these protocols have been specifically designed to avoid the partitioning of the overlay in large clusters (network breakage) despite massive node failures and the continuous arrivals/departures of nodes (churn). In this paper we identify a second effect connected to churn, namely network erosion. We show how erosion affects overlay network connectivity and point out that even a strongly connected overlay network, when exposed to continuous churn, can be disgregated. More specifically the consequences of erosion are shown, through an experimental study, in the context of overlay management protocols based on the view-exchange technique. We finally propose a connection recovery mechanism to be endowed at each node which is able to collaboratively detect node isolation and the presence of small clusters. This mechanism is shown to be effective in reducing the erosion of an overlay network exposed to continuous churn and to quickly recover its connectivity during stability periods.