Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures

C. Scheideler, A. Setzer, T.F. Strothmann, in: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015.

Download
Restricted 241-ScheidelerSetzerStrothmann2015.pdf 692.36 KB
Conference Paper | English
Abstract
Distributed applications are commonly based on overlay networks interconnecting their sites so that they can exchange information. For these overlay networks to preserve their functionality, they should be able to recover from various problems like membership changes or faults. Various self-stabilizing overlay networks have already been proposed in recent years, which have the advantage of being able to recover from any illegal state, but none of these networks can give any guarantees on its functionality while the recovery process is going on. We initiate research on overlay networks that are not only self-stabilizing but that also ensure that searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. We call this property monotonic searchability. We show that in general it is impossible to provide monotonic searchability if corrupted messages are present in the system, which justifies the restriction to system states without corrupted messages. Furthermore, we provide a self-stabilizing protocol for the line for which we can also show monotonic searchability. It turns out that even for the line it is non-trivial to achieve this property. Additionally, we extend our protocol to deal with node departures in terms of the Finite Departure Problem of Foreback et. al (SSS 2014). This makes our protocol even capable of handling node dynamics.
Publishing Year
Proceedings Title
Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)
forms.conference.field.series_title_volume.label
Leibniz International Proceedings in Informatics (LIPIcs)
LibreCat-ID
241

Cite this

Scheideler C, Setzer A, Strothmann TF. Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS). Leibniz International Proceedings in Informatics (LIPIcs). ; 2015. doi:10.4230/LIPIcs.OPODIS.2015.24
Scheideler, C., Setzer, A., & Strothmann, T. F. (2015). Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS). https://doi.org/10.4230/LIPIcs.OPODIS.2015.24
@inproceedings{Scheideler_Setzer_Strothmann_2015, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures}, DOI={10.4230/LIPIcs.OPODIS.2015.24}, booktitle={Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS)}, author={Scheideler, Christian and Setzer, Alexander and Strothmann, Thim Frederik}, year={2015}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
Scheideler, Christian, Alexander Setzer, and Thim Frederik Strothmann. “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures.” In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS). Leibniz International Proceedings in Informatics (LIPIcs), 2015. https://doi.org/10.4230/LIPIcs.OPODIS.2015.24.
C. Scheideler, A. Setzer, and T. F. Strothmann, “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures,” in Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015.
Scheideler, Christian, et al. “Towards Establishing Monotonic Searchability in Self-Stabilizing Data Structures.” Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), 2015, doi:10.4230/LIPIcs.OPODIS.2015.24.
Main File(s)
File Name
241-ScheidelerSetzerStrothmann2015.pdf 692.36 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T10:28:21Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar