A Self-Stabilizing Hashed Patricia Trie

T. Knollmann, C. Scheideler, in:, T. Izumi, P. Kuznetsov (Eds.), Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2018.

Download
Restricted ASelf-stabilizingHashedPatrici.pdf 500.00 KB
Conference Paper | English
Editor
;
Abstract
While a lot of research in distributed computing has covered solutions for self-stabilizing computing and topologies, there is far less work on self-stabilization for distributed data structures. Considering crashing peers in peer-to-peer networks, it should not be taken for granted that a distributed data structure remains intact. In this work, we present a self-stabilizing protocol for a distributed data structure called the hashed Patricia Trie (Kniesburges and Scheideler WALCOM'11) that enables efficient prefix search on a set of keys. The data structure has a wide area of applications including string matching problems while offering low overhead and efficient operations when embedded on top of a distributed hash table. Especially, longest prefix matching for $x$ can be done in $\mathcal{O}(\log |x|)$ hash table read accesses. We show how to maintain the structure in a self-stabilizing way. Our protocol assures low overhead in a legal state and a total (asymptotically optimal) memory demand of $\Theta(d)$ bits, where $d$ is the number of bits needed for storing all keys.
Publishing Year
Proceedings Title
Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Volume
11201
Conference
20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Conference Location
Tokyo
Conference Date
2018-11-04 – 2018-11-07
LibreCat-ID

Cite this

Knollmann T, Scheideler C. A Self-Stabilizing Hashed Patricia Trie. In: Izumi T, Kuznetsov P, eds. Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS).Vol 11201. Lecture Notes of Computer Science. Springer, Cham; 2018. doi:10.1007/978-3-030-03232-6_1.
Knollmann, T., & Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia Trie. In T. Izumi & P. Kuznetsov (Eds.), Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (Vol. 11201). Tokyo: Springer, Cham. http://doi.org/10.1007/978-3-030-03232-6_1
@inbook{Knollmann_Scheideler_2018, series={Lecture Notes of Computer Science}, title={A Self-Stabilizing Hashed Patricia Trie}, volume={11201}, DOI={10.1007/978-3-030-03232-6_1}, booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Knollmann, Till and Scheideler, Christian}, editor={Izumi, Taisuke and Kuznetsov, PetrEditors}, year={2018}, collection={Lecture Notes of Computer Science}}
Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” In Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), edited by Taisuke Izumi and Petr Kuznetsov, Vol. 11201. Lecture Notes of Computer Science. Springer, Cham, 2018. doi:10.1007/978-3-030-03232-6_1.
T. Knollmann and C. Scheideler, “A Self-Stabilizing Hashed Patricia Trie,” in Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Tokyo, 2018, vol. 11201.
Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Ed. Taisuke Izumi and Petr Kuznetsov. Vol. 11201. Springer, Cham, 2018. Web. Lecture Notes of Computer Science.
Main File(s)
File Name
ASelf-stabilizingHashedPatrici.pdf 500.00 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-11-02T14:38:37Z


Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1809.04923

Search this title in

Google Scholar