A Self-Stabilizing Hashed Patricia Trie

T. Knollmann, C. Scheideler, arXiv:1809.04923 (2018).

No fulltext has been uploaded. References only!
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

Cite this

Knollmann T, Scheideler C. A Self-Stabilizing Hashed Patricia Trie. arXiv:180904923. 2018.
Knollmann, T., & Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia Trie. arXiv:1809.04923.
@article{Knollmann_Scheideler_2018, title={A Self-Stabilizing Hashed Patricia Trie}, journal={arXiv:1809.04923}, author={Knollmann, Till and Scheideler, Christian}, year={2018}}
Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” arXiv:1809.04923, 2018.
T. Knollmann and C. Scheideler, “A Self-Stabilizing Hashed Patricia Trie,” arXiv:1809.04923. 2018.
Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” arXiv:1809.04923 2018: n. pag. Print.
Link(s) to Main File(s)
Access Level
Restricted Closed Access
This publication cites the following data publications:


Marked Publications

Open Data LibreCat

Search this title in

Google Scholar