Startseite > Publikationen > Publikationen

Publikationen

Knollmann, Till;Scheideler, Christian:

A Self-Stabilizing Hashed Patricia Trie.

In: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer Lecture Notes in Computer Science LNCS, Band 11201 , 4. - 7. Nov. 2018, Springer

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.

Weblink

https://doi.org/10.1007/978-3-030-03232-6_1

Bibtex

@inproceedings{hniid=9778,
author = {Knollmann, Till and Scheideler, Christian},
title = {A Self-Stabilizing Hashed Patricia Trie},
booktitle = {Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)},
volume = {11201},
series = {Springer Lecture Notes in Computer Science LNCS},
publisher = {Springer},
month = {4~-~7~} # nov,
year = {2018},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/9778