---
_id: '29843'
article_number: '104877'
author:
- first_name: Jannik
  full_name: Castenow, Jannik
  id: '38705'
  last_name: Castenow
- first_name: Peter
  full_name: Kling, Peter
  last_name: Kling
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: Castenow J, Kling P, Knollmann T, Meyer auf der Heide F. A Discrete and Continuous
    Study of the Max-Chain-Formation Problem. <i>Information and Computation</i>.
    Published online 2022. doi:<a href="https://doi.org/10.1016/j.ic.2022.104877">10.1016/j.ic.2022.104877</a>
  apa: Castenow, J., Kling, P., Knollmann, T., &#38; Meyer auf der Heide, F. (2022).
    A Discrete and Continuous Study of the Max-Chain-Formation Problem. <i>Information
    and Computation</i>, Article 104877. <a href="https://doi.org/10.1016/j.ic.2022.104877">https://doi.org/10.1016/j.ic.2022.104877</a>
  bibtex: '@article{Castenow_Kling_Knollmann_Meyer auf der Heide_2022, title={A Discrete
    and Continuous Study of the Max-Chain-Formation Problem}, DOI={<a href="https://doi.org/10.1016/j.ic.2022.104877">10.1016/j.ic.2022.104877</a>},
    number={104877}, journal={Information and Computation}, publisher={Elsevier BV},
    author={Castenow, Jannik and Kling, Peter and Knollmann, Till and Meyer auf der
    Heide, Friedhelm}, year={2022} }'
  chicago: Castenow, Jannik, Peter Kling, Till Knollmann, and Friedhelm Meyer auf
    der Heide. “A Discrete and Continuous Study of the Max-Chain-Formation Problem.”
    <i>Information and Computation</i>, 2022. <a href="https://doi.org/10.1016/j.ic.2022.104877">https://doi.org/10.1016/j.ic.2022.104877</a>.
  ieee: 'J. Castenow, P. Kling, T. Knollmann, and F. Meyer auf der Heide, “A Discrete
    and Continuous Study of the Max-Chain-Formation Problem,” <i>Information and Computation</i>,
    Art. no. 104877, 2022, doi: <a href="https://doi.org/10.1016/j.ic.2022.104877">10.1016/j.ic.2022.104877</a>.'
  mla: Castenow, Jannik, et al. “A Discrete and Continuous Study of the Max-Chain-Formation
    Problem.” <i>Information and Computation</i>, 104877, Elsevier BV, 2022, doi:<a
    href="https://doi.org/10.1016/j.ic.2022.104877">10.1016/j.ic.2022.104877</a>.
  short: J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide, Information
    and Computation (2022).
date_created: 2022-02-15T07:38:28Z
date_updated: 2022-02-15T07:41:00Z
department:
- _id: '63'
doi: 10.1016/j.ic.2022.104877
keyword:
- Computational Theory and Mathematics
- Computer Science Applications
- Information Systems
- Theoretical Computer Science
language:
- iso: eng
project:
- _id: '106'
  name: 'Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme'
publication: Information and Computation
publication_identifier:
  issn:
  - 0890-5401
publication_status: published
publisher: Elsevier BV
status: public
title: A Discrete and Continuous Study of the Max-Chain-Formation Problem
type: journal_article
user_id: '38705'
year: '2022'
...
---
_id: '21096'
abstract:
- lang: eng
  text: While many 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. However, when peers in peer-to-peer networks crash, a distributed
    data structure may not remain intact. 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 many applications 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 O(log |x|) hash table read accesses. We show
    how to maintain the structure in a self-stabilizing way, while assuring a low
    overhead in a legal state and an asymptotically optimal memory demand of O(d)
    bits, where d is the number of bits needed for storing all keys.
article_number: '104697'
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. <i>Information
    and Computation</i>. Published online 2022. doi:<a href="https://doi.org/10.1016/j.ic.2021.104697">10.1016/j.ic.2021.104697</a>
  apa: Knollmann, T., &#38; Scheideler, C. (2022). A self-stabilizing Hashed Patricia
    Trie. <i>Information and Computation</i>, Article 104697. <a href="https://doi.org/10.1016/j.ic.2021.104697">https://doi.org/10.1016/j.ic.2021.104697</a>
  bibtex: '@article{Knollmann_Scheideler_2022, title={A self-stabilizing Hashed Patricia
    Trie}, DOI={<a href="https://doi.org/10.1016/j.ic.2021.104697">10.1016/j.ic.2021.104697</a>},
    number={104697}, journal={Information and Computation}, author={Knollmann, Till
    and Scheideler, Christian}, year={2022} }'
  chicago: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
    Trie.” <i>Information and Computation</i>, 2022. <a href="https://doi.org/10.1016/j.ic.2021.104697">https://doi.org/10.1016/j.ic.2021.104697</a>.
  ieee: 'T. Knollmann and C. Scheideler, “A self-stabilizing Hashed Patricia Trie,”
    <i>Information and Computation</i>, Art. no. 104697, 2022, doi: <a href="https://doi.org/10.1016/j.ic.2021.104697">10.1016/j.ic.2021.104697</a>.'
  mla: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia
    Trie.” <i>Information and Computation</i>, 104697, 2022, doi:<a href="https://doi.org/10.1016/j.ic.2021.104697">10.1016/j.ic.2021.104697</a>.
  short: T. Knollmann, C. Scheideler, Information and Computation (2022).
date_created: 2021-01-29T09:39:40Z
date_updated: 2023-03-27T07:56:48Z
department:
- _id: '63'
- _id: '79'
doi: 10.1016/j.ic.2021.104697
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: Information and Computation
publication_identifier:
  issn:
  - 0890-5401
publication_status: published
status: public
title: A self-stabilizing Hashed Patricia Trie
type: journal_article
user_id: '15504'
year: '2022'
...
---
_id: '16565'
author:
- first_name: Artur
  full_name: Czumaj, Artur
  last_name: Czumaj
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Volker
  full_name: Stemann, Volker
  last_name: Stemann
citation:
  ama: 'Czumaj A, Meyer auf der Heide F, Stemann V. Simulating Shared Memory in Real
    Time: On the Computation Power of Reconfigurable Architectures. <i>Information
    and Computation</i>. 1997:103-120. doi:<a href="https://doi.org/10.1006/inco.1997.2642">10.1006/inco.1997.2642</a>'
  apa: 'Czumaj, A., Meyer auf der Heide, F., &#38; Stemann, V. (1997). Simulating
    Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures.
    <i>Information and Computation</i>, 103–120. <a href="https://doi.org/10.1006/inco.1997.2642">https://doi.org/10.1006/inco.1997.2642</a>'
  bibtex: '@article{Czumaj_Meyer auf der Heide_Stemann_1997, title={Simulating Shared
    Memory in Real Time: On the Computation Power of Reconfigurable Architectures},
    DOI={<a href="https://doi.org/10.1006/inco.1997.2642">10.1006/inco.1997.2642</a>},
    journal={Information and Computation}, author={Czumaj, Artur and Meyer auf der
    Heide, Friedhelm and Stemann, Volker}, year={1997}, pages={103–120} }'
  chicago: 'Czumaj, Artur, Friedhelm Meyer auf der Heide, and Volker Stemann. “Simulating
    Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures.”
    <i>Information and Computation</i>, 1997, 103–20. <a href="https://doi.org/10.1006/inco.1997.2642">https://doi.org/10.1006/inco.1997.2642</a>.'
  ieee: 'A. Czumaj, F. Meyer auf der Heide, and V. Stemann, “Simulating Shared Memory
    in Real Time: On the Computation Power of Reconfigurable Architectures,” <i>Information
    and Computation</i>, pp. 103–120, 1997.'
  mla: 'Czumaj, Artur, et al. “Simulating Shared Memory in Real Time: On the Computation
    Power of Reconfigurable Architectures.” <i>Information and Computation</i>, 1997,
    pp. 103–20, doi:<a href="https://doi.org/10.1006/inco.1997.2642">10.1006/inco.1997.2642</a>.'
  short: A. Czumaj, F. Meyer auf der Heide, V. Stemann, Information and Computation
    (1997) 103–120.
date_created: 2020-04-15T11:20:09Z
date_updated: 2022-01-06T06:52:52Z
department:
- _id: '63'
doi: 10.1006/inco.1997.2642
language:
- iso: eng
page: 103-120
publication: Information and Computation
publication_identifier:
  issn:
  - 0890-5401
publication_status: published
status: public
title: 'Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable
  Architectures'
type: journal_article
user_id: '15415'
year: '1997'
...
---
_id: '16729'
author:
- first_name: M.
  full_name: Dietzfelbinger, M.
  last_name: Dietzfelbinger
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: Dietzfelbinger M, Meyer auf der Heide F. An Optimal Parallel Dictionary. <i>Information
    and Computation</i>. 1993:196-217. doi:<a href="https://doi.org/10.1006/inco.1993.1007">10.1006/inco.1993.1007</a>
  apa: Dietzfelbinger, M., &#38; Meyer auf der Heide, F. (1993). An Optimal Parallel
    Dictionary. <i>Information and Computation</i>, 196–217. <a href="https://doi.org/10.1006/inco.1993.1007">https://doi.org/10.1006/inco.1993.1007</a>
  bibtex: '@article{Dietzfelbinger_Meyer auf der Heide_1993, title={An Optimal Parallel
    Dictionary}, DOI={<a href="https://doi.org/10.1006/inco.1993.1007">10.1006/inco.1993.1007</a>},
    journal={Information and Computation}, author={Dietzfelbinger, M. and Meyer auf
    der Heide, Friedhelm}, year={1993}, pages={196–217} }'
  chicago: Dietzfelbinger, M., and Friedhelm Meyer auf der Heide. “An Optimal Parallel
    Dictionary.” <i>Information and Computation</i>, 1993, 196–217. <a href="https://doi.org/10.1006/inco.1993.1007">https://doi.org/10.1006/inco.1993.1007</a>.
  ieee: M. Dietzfelbinger and F. Meyer auf der Heide, “An Optimal Parallel Dictionary,”
    <i>Information and Computation</i>, pp. 196–217, 1993.
  mla: Dietzfelbinger, M., and Friedhelm Meyer auf der Heide. “An Optimal Parallel
    Dictionary.” <i>Information and Computation</i>, 1993, pp. 196–217, doi:<a href="https://doi.org/10.1006/inco.1993.1007">10.1006/inco.1993.1007</a>.
  short: M. Dietzfelbinger, F. Meyer auf der Heide, Information and Computation (1993)
    196–217.
date_created: 2020-04-20T10:31:51Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1006/inco.1993.1007
language:
- iso: eng
page: 196-217
publication: Information and Computation
publication_identifier:
  issn:
  - 0890-5401
publication_status: published
status: public
title: An Optimal Parallel Dictionary
type: journal_article
user_id: '15415'
year: '1993'
...
---
_id: '16763'
author:
- first_name: László
  full_name: Babai, László
  last_name: Babai
- first_name: Bettina
  full_name: Just, Bettina
  last_name: Just
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: Babai L, Just B, Meyer auf der Heide F. On the limits of computations with
    the floor function. <i>Information and Computation</i>. 1988:99-107. doi:<a href="https://doi.org/10.1016/0890-5401(88)90031-4">10.1016/0890-5401(88)90031-4</a>
  apa: Babai, L., Just, B., &#38; Meyer auf der Heide, F. (1988). On the limits of
    computations with the floor function. <i>Information and Computation</i>, 99–107.
    <a href="https://doi.org/10.1016/0890-5401(88)90031-4">https://doi.org/10.1016/0890-5401(88)90031-4</a>
  bibtex: '@article{Babai_Just_Meyer auf der Heide_1988, title={On the limits of computations
    with the floor function}, DOI={<a href="https://doi.org/10.1016/0890-5401(88)90031-4">10.1016/0890-5401(88)90031-4</a>},
    journal={Information and Computation}, author={Babai, László and Just, Bettina
    and Meyer auf der Heide, Friedhelm}, year={1988}, pages={99–107} }'
  chicago: Babai, László, Bettina Just, and Friedhelm Meyer auf der Heide. “On the
    Limits of Computations with the Floor Function.” <i>Information and Computation</i>,
    1988, 99–107. <a href="https://doi.org/10.1016/0890-5401(88)90031-4">https://doi.org/10.1016/0890-5401(88)90031-4</a>.
  ieee: L. Babai, B. Just, and F. Meyer auf der Heide, “On the limits of computations
    with the floor function,” <i>Information and Computation</i>, pp. 99–107, 1988.
  mla: Babai, László, et al. “On the Limits of Computations with the Floor Function.”
    <i>Information and Computation</i>, 1988, pp. 99–107, doi:<a href="https://doi.org/10.1016/0890-5401(88)90031-4">10.1016/0890-5401(88)90031-4</a>.
  short: L. Babai, B. Just, F. Meyer auf der Heide, Information and Computation (1988)
    99–107.
date_created: 2020-04-21T08:50:17Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1016/0890-5401(88)90031-4
language:
- iso: eng
page: 99-107
publication: Information and Computation
publication_identifier:
  issn:
  - 0890-5401
publication_status: published
status: public
title: On the limits of computations with the floor function
type: journal_article
user_id: '15415'
year: '1988'
...