Towards a Universal Approach for the Finite Departure Problem in Overlay Networks

A. Koutsopoulos, C. Scheideler, T.F. Strothmann, in:, Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2015.

Download
Restricted 242-KSS-SSS2015.pdf 532.79 KB
Conference Paper | English
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. There are a number of studies for safe node exclusion if the overlay is in a well-defined state, but almost no formal results are known 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 (FDP) and the Finite Sleep Problem (FSP). In the FDP the 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 are the first to present a self-stabilizing protocol for the FDP and the FSP that can be combined with a large class of overlay maintenance protocols so that these are then guaranteed to safely exclude leaving nodes from the system from any initial state while operating as specified for the staying nodes. In order to formally define the properties these overlay maintenance protocols have to satisfy, we identify four basic primitives for manipulating edges in an overlay network that might be of independent interest.
Publishing Year
Proceedings Title
Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Page
201-216
LibreCat-ID

Cite this

Koutsopoulos A, Scheideler C, Strothmann TF. Towards a Universal Approach for the Finite Departure Problem in Overlay Networks. In: Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Lecture Notes in Computer Science.; 2015. doi:10.1007/978-3-319-21741-3_14.
Koutsopoulos, A., Scheideler, C., & Strothmann, T. F. (2015). Towards a Universal Approach for the Finite Departure Problem in Overlay Networks. In Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). http://doi.org/10.1007/978-3-319-21741-3_14
@inbook{Koutsopoulos_Scheideler_Strothmann_2015, series={Lecture Notes in Computer Science}, title={Towards a Universal Approach for the Finite Departure Problem in Overlay Networks}, DOI={10.1007/978-3-319-21741-3_14}, booktitle={Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, author={Koutsopoulos, Andreas and Scheideler, Christian and Strothmann, Thim Frederik}, year={2015}, collection={Lecture Notes in Computer Science}}
Koutsopoulos, Andreas, Christian Scheideler, and Thim Frederik Strothmann. “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks.” In Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Lecture Notes in Computer Science, 2015. doi:10.1007/978-3-319-21741-3_14.
A. Koutsopoulos, C. Scheideler, and T. F. Strothmann, “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks,” in Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2015.
Koutsopoulos, Andreas, Christian Scheideler, and Thim Frederik Strothmann. “Towards a Universal Approach for the Finite Departure Problem in Overlay Networks.” Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). N.p., 2015. Web. Lecture Notes in Computer Science.
Main File(s)
File Name
242-KSS-SSS2015.pdf 532.79 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T09:59:32Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar