---
res:
bibo_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.\r\nConsidering crashing peers in peer-to-peer networks, it should
not be taken for granted that a distributed data structure remains intact.\r\nIn
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.\r\nThe 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.\r\nEspecially,
longest prefix matching for $x$ can be done in $\\mathcal{O}(\\log |x|)$ hash
table read accesses.\r\nWe show how to maintain the structure in a self-stabilizing
way.\r\nOur 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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Till
foaf_name: Knollmann, Till
foaf_surname: Knollmann
foaf_workInfoHomepage: http://www.librecat.org/personId=39241
orcid: 0000-0003-2014-4696
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
bibo_doi: 10.1007/978-3-030-03232-6_1
bibo_volume: 11201
dct_date: 2018^xs_gYear
dct_language: eng
dct_publisher: Springer, Cham@
dct_subject:
- Self-Stabilizing
- Prefix Search
- Distributed Data Structure
dct_title: A Self-Stabilizing Hashed Patricia Trie@
...