---
_id: '4411'
abstract:
- lang: eng
text: "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."
author:
- first_name: Till
full_name: Knollmann, Till
id: '39241'
last_name: Knollmann
orcid: 0000-0003-2014-4696
- first_name: Christian
full_name: Scheideler, Christian
id: '20792'
last_name: Scheideler
citation:
ama: 'Knollmann T, Scheideler C. A Self-Stabilizing Hashed Patricia Trie. In: Izumi
T, Kuznetsov P, eds. Proceedings of the 20th International Symposium on Stabilization,
Safety, and Security of Distributed Systems (SSS). Vol 11201. Lecture Notes
of Computer Science. Springer, Cham; 2018. doi:10.1007/978-3-030-03232-6_1'
apa: 'Knollmann, T., & Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia
Trie. In T. Izumi & P. Kuznetsov (Eds.), Proceedings of the 20th International
Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
(Vol. 11201). Tokyo: Springer, Cham. https://doi.org/10.1007/978-3-030-03232-6_1'
bibtex: '@inproceedings{Knollmann_Scheideler_2018, series={Lecture Notes of Computer
Science}, title={A Self-Stabilizing Hashed Patricia Trie}, volume={11201}, DOI={10.1007/978-3-030-03232-6_1},
booktitle={Proceedings of the 20th International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Knollmann,
Till and Scheideler, Christian}, editor={Izumi, Taisuke and Kuznetsov, PetrEditors},
year={2018}, collection={Lecture Notes of Computer Science} }'
chicago: 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), edited by Taisuke Izumi
and Petr Kuznetsov, Vol. 11201. Lecture Notes of Computer Science. Springer, Cham,
2018. https://doi.org/10.1007/978-3-030-03232-6_1.
ieee: 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, vol. 11201.
mla: 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), edited by Taisuke Izumi and Petr
Kuznetsov, vol. 11201, Springer, Cham, 2018, doi:10.1007/978-3-030-03232-6_1.
short: 'T. Knollmann, C. Scheideler, in: T. Izumi, P. Kuznetsov (Eds.), Proceedings
of the 20th International Symposium on Stabilization, Safety, and Security of
Distributed Systems (SSS), Springer, Cham, 2018.'
conference:
end_date: 2018-11-07
location: Tokyo
name: 20th International Symposium on Stabilization, Safety, and Security of Distributed
Systems (SSS)
start_date: 2018-11-04
date_created: 2018-09-17T13:12:18Z
date_updated: 2022-01-06T07:01:02Z
ddc:
- '000'
department:
- _id: '63'
- _id: '79'
doi: 10.1007/978-3-030-03232-6_1
editor:
- first_name: Taisuke
full_name: Izumi, Taisuke
last_name: Izumi
- first_name: Petr
full_name: Kuznetsov, Petr
last_name: Kuznetsov
external_id:
arxiv:
- '1809.04923'
file:
- access_level: closed
content_type: application/pdf
creator: ups
date_created: 2018-11-02T14:38:37Z
date_updated: 2018-11-02T14:38:37Z
file_id: '5277'
file_name: ASelf-stabilizingHashedPatrici.pdf
file_size: 500005
relation: main_file
success: 1
file_date_updated: 2018-11-02T14:38:37Z
has_accepted_license: '1'
intvolume: ' 11201'
keyword:
- Self-Stabilizing
- Prefix Search
- Distributed Data Structure
language:
- iso: eng
project:
- _id: '1'
name: SFB 901
- _id: '2'
name: SFB 901 - Project Area A
- _id: '5'
name: SFB 901 - Subproject A1
publication: Proceedings of the 20th International Symposium on Stabilization, Safety,
and Security of Distributed Systems (SSS)
publisher: Springer, Cham
series_title: Lecture Notes of Computer Science
status: public
title: A Self-Stabilizing Hashed Patricia Trie
type: conference
user_id: '39241'
volume: 11201
year: '2018'
...