Relays: a new approach for the finite departure problem in overlay networks
From MaRDI portal
Publication:6165841
DOI10.1007/978-3-030-03232-6_16zbMATH Open1519.68010arXiv1809.05013OpenAlexW2891058864MaRDI QIDQ6165841FDOQ6165841
Authors: Christian Scheideler, Alexander Setzer 
Publication date: 2 August 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1809.05013
Recommendations
- Towards a universal approach for the finite departure problem in overlay networks
- Towards a universal approach for the finite departure problem in overlay networks
- On Stabilizing Departures in Overlay Networks
- A survey on relay placement with runtime and approximation guarantees
- Exact approaches for network design problems with relays
- Trajectory-based multi-hop relay deployment in wireless networks
- Improved approximation algorithms for single-tiered relay placement
Network design and communication in computer systems (68M10) Distributed systems (68M14) Network protocols (68M12)
Cited In (4)
This page was built for publication: Relays: a new approach for the finite departure problem in overlay networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165841)
