On Stabilizing Departures in Overlay Networks

A fundamental problem for peer-to-peer systems is to maintain connectivity while nodes are leaving, i.e., the nodes requesting to leave the peer-to-peer system are excluded from the overlay network without affecting its connectivity. There are a number of studies for safe node exclusion if the overlay is in a well-defined state initially. Surprisingly, the problem is not formally studied yet for the case in which the overlay network is in an arbitrary initial state, i.e., when looking for a self-stabilizing solution for excluding leaving nodes. We study this problem in two variants: the Finite Departure Problem ( \(\mathcal{FDP}\) ) and the Finite Sleep Problem ( \(\mathcal{FSP}\) ). In the \(\mathcal{FDP}\) the leaving nodes have to irrevocably decide when it is safe to leave the network, whereas in the \(\mathcal{FSP}\), this leaving decision does not have to be final: the nodes may resume computation if necessary. We show that there is no self-stabilizing distributed algorithm for the \(\mathcal{FDP}\), even in a synchronous message passing model. To allow a solution, we introduce an oracle called \(\mathcal{NIDEC}\) and show that it is sufficient even for the asynchronous message passing model by proposing an algorithm that can solve the \(\mathcal{FDP}\) using \(\mathcal{NIDEC}\). We also show that a solution to the \(\mathcal{FSP}\) does not require an oracle.