Towards a universal approach for the finite departure problem in overlay networks

A fundamental problem for overlay networks is to safely exclude leaving nodes, i.e., nodes requesting to leave the network are excluded without affecting connectivity. There are numerous studies for safe node exclusion if the overlay is in a well-defined state, but almost no formal results for the self-stabilizing case. We study this problem in two variants: the Finite Departure Problem (FDP) and the Finite Sleep Problem (FSP). In the FDP leaving nodes have to irrevocably decide when it is safe to leave the network, whereas in the FSP, this leaving decision does not have to be final: the nodes may resume computation when woken up by an incoming message. We present self-stabilizing protocols for both problems that can be combined with a large class of overlay networks in order to guarantee safe exclusion for leaving nodes from any initial state while operating normal for staying nodes. 1