A Self-Stabilizing Hashed Patricia Trie

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

Download
No fulltext has been uploaded. References only!
Conference Paper
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
Journal Title
Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
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: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS).; 2018.
Knollmann, T., & Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia Trie. In Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Tokyo.
@inbook{Knollmann_Scheideler_2018, title={A Self-Stabilizing Hashed Patricia Trie}, booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, author={Knollmann, Till and Scheideler, Christian}, year={2018}}
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), 2018.
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.
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). N.p., 2018. Print.
frontdoor.tabs.publications.cited_by
This publication cites the following data publications:

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar