@inproceedings{4411,
  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.}},
  author       = {{Knollmann, Till and Scheideler, Christian}},
  booktitle    = {{Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}},
  editor       = {{Izumi, Taisuke and Kuznetsov, Petr}},
  keywords     = {{Self-Stabilizing, Prefix Search, Distributed Data Structure}},
  location     = {{Tokyo}},
  publisher    = {{Springer, Cham}},
  title        = {{{A Self-Stabilizing Hashed Patricia Trie}}},
  doi          = {{10.1007/978-3-030-03232-6_1}},
  volume       = {{11201}},
  year         = {{2018}},
}