---
_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. <i>Proceedings of the 20th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS)</i>. Vol 11201. Lecture Notes
    of Computer Science. Springer, Cham; 2018. doi:<a href="https://doi.org/10.1007/978-3-030-03232-6_1">10.1007/978-3-030-03232-6_1</a>'
  apa: 'Knollmann, T., &#38; Scheideler, C. (2018). A Self-Stabilizing Hashed Patricia
    Trie. In T. Izumi &#38; P. Kuznetsov (Eds.), <i>Proceedings of the 20th International
    Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>
    (Vol. 11201). Tokyo: Springer, Cham. <a href="https://doi.org/10.1007/978-3-030-03232-6_1">https://doi.org/10.1007/978-3-030-03232-6_1</a>'
  bibtex: '@inproceedings{Knollmann_Scheideler_2018, series={Lecture Notes of Computer
    Science}, title={A Self-Stabilizing Hashed Patricia Trie}, volume={11201}, DOI={<a
    href="https://doi.org/10.1007/978-3-030-03232-6_1">10.1007/978-3-030-03232-6_1</a>},
    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 <i>Proceedings of the 20th International Symposium on Stabilization,
    Safety, and Security of Distributed Systems (SSS)</i>, edited by Taisuke Izumi
    and Petr Kuznetsov, Vol. 11201. Lecture Notes of Computer Science. Springer, Cham,
    2018. <a href="https://doi.org/10.1007/978-3-030-03232-6_1">https://doi.org/10.1007/978-3-030-03232-6_1</a>.
  ieee: T. Knollmann and C. Scheideler, “A Self-Stabilizing Hashed Patricia Trie,”
    in <i>Proceedings of the 20th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)</i>, Tokyo, 2018, vol. 11201.
  mla: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
    Trie.” <i>Proceedings of the 20th International Symposium on Stabilization, Safety,
    and Security of Distributed Systems (SSS)</i>, edited by Taisuke Izumi and Petr
    Kuznetsov, vol. 11201, Springer, Cham, 2018, doi:<a href="https://doi.org/10.1007/978-3-030-03232-6_1">10.1007/978-3-030-03232-6_1</a>.
  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'
...