  A fundamental problem for overlay networks is to safely exclude leaving
nodes, i.e., the nodes requesting to leave the overlay network are excluded
from it without affecting its connectivity. To rigorously study self-tabilizing
solutions to this problem, the Finite Departure Problem (FDP) has been proposed
[12]. In the FDP we are given a network of processes in an arbitrary state, and
the goal is to eventually arrive at (and stay in) a state in which all leaving
processes irrevocably decided to leave the system while for all
weakly-connected components in the initial overlay network, all staying
processes in that component will still form a weakly connected component. In
the standard interconnection model, the FDP is known to be unsolvable by local
control protocols, so oracles have been investigated that allow the problem to
be solved [12]. To avoid the use of oracles, we introduce a new interconnection
model based on relays. Despite the relay model appearing to be rather
restrictive, we show that it is universal, i.e., it is possible to transform
any weakly-connected topology into any other weakly-connected topology, which
is important for being a useful interconnection model for overlay networks.
Apart from this, our model allows processes to grant and revoke access rights,
which is why we believe it to be of interest beyond the scope of this paper. We
show how to implement the relay layer in a self-stabilizing way and identify
properties protocols need to satisfy so that the relay layer can recover while
serving protocol requests.
