--- _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. Information and Computation. Published online 2022. doi:10.1016/j.ic.2022.104877 apa: Castenow, J., Kling, P., Knollmann, T., & Meyer auf der Heide, F. (2022). A Discrete and Continuous Study of the Max-Chain-Formation Problem. Information and Computation, Article 104877. https://doi.org/10.1016/j.ic.2022.104877 bibtex: '@article{Castenow_Kling_Knollmann_Meyer auf der Heide_2022, title={A Discrete and Continuous Study of the Max-Chain-Formation Problem}, DOI={10.1016/j.ic.2022.104877}, 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.” Information and Computation, 2022. https://doi.org/10.1016/j.ic.2022.104877. ieee: 'J. Castenow, P. Kling, T. Knollmann, and F. Meyer auf der Heide, “A Discrete and Continuous Study of the Max-Chain-Formation Problem,” Information and Computation, Art. no. 104877, 2022, doi: 10.1016/j.ic.2022.104877.' mla: Castenow, Jannik, et al. “A Discrete and Continuous Study of the Max-Chain-Formation Problem.” Information and Computation, 104877, Elsevier BV, 2022, doi:10.1016/j.ic.2022.104877. 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. Information and Computation. Published online 2022. doi:10.1016/j.ic.2021.104697 apa: Knollmann, T., & Scheideler, C. (2022). A self-stabilizing Hashed Patricia Trie. Information and Computation, Article 104697. https://doi.org/10.1016/j.ic.2021.104697 bibtex: '@article{Knollmann_Scheideler_2022, title={A self-stabilizing Hashed Patricia Trie}, DOI={10.1016/j.ic.2021.104697}, 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.” Information and Computation, 2022. https://doi.org/10.1016/j.ic.2021.104697. ieee: 'T. Knollmann and C. Scheideler, “A self-stabilizing Hashed Patricia Trie,” Information and Computation, Art. no. 104697, 2022, doi: 10.1016/j.ic.2021.104697.' mla: Knollmann, Till, and Christian Scheideler. “A Self-Stabilizing Hashed Patricia Trie.” Information and Computation, 104697, 2022, doi:10.1016/j.ic.2021.104697. 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. Information and Computation. 1997:103-120. doi:10.1006/inco.1997.2642' apa: 'Czumaj, A., Meyer auf der Heide, F., & Stemann, V. (1997). Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures. Information and Computation, 103–120. https://doi.org/10.1006/inco.1997.2642' bibtex: '@article{Czumaj_Meyer auf der Heide_Stemann_1997, title={Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures}, DOI={10.1006/inco.1997.2642}, 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.” Information and Computation, 1997, 103–20. https://doi.org/10.1006/inco.1997.2642.' ieee: 'A. Czumaj, F. Meyer auf der Heide, and V. Stemann, “Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures,” Information and Computation, pp. 103–120, 1997.' mla: 'Czumaj, Artur, et al. “Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures.” Information and Computation, 1997, pp. 103–20, doi:10.1006/inco.1997.2642.' 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. Information and Computation. 1993:196-217. doi:10.1006/inco.1993.1007 apa: Dietzfelbinger, M., & Meyer auf der Heide, F. (1993). An Optimal Parallel Dictionary. Information and Computation, 196–217. https://doi.org/10.1006/inco.1993.1007 bibtex: '@article{Dietzfelbinger_Meyer auf der Heide_1993, title={An Optimal Parallel Dictionary}, DOI={10.1006/inco.1993.1007}, 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.” Information and Computation, 1993, 196–217. https://doi.org/10.1006/inco.1993.1007. ieee: M. Dietzfelbinger and F. Meyer auf der Heide, “An Optimal Parallel Dictionary,” Information and Computation, pp. 196–217, 1993. mla: Dietzfelbinger, M., and Friedhelm Meyer auf der Heide. “An Optimal Parallel Dictionary.” Information and Computation, 1993, pp. 196–217, doi:10.1006/inco.1993.1007. 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. Information and Computation. 1988:99-107. doi:10.1016/0890-5401(88)90031-4 apa: Babai, L., Just, B., & Meyer auf der Heide, F. (1988). On the limits of computations with the floor function. Information and Computation, 99–107. https://doi.org/10.1016/0890-5401(88)90031-4 bibtex: '@article{Babai_Just_Meyer auf der Heide_1988, title={On the limits of computations with the floor function}, DOI={10.1016/0890-5401(88)90031-4}, 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.” Information and Computation, 1988, 99–107. https://doi.org/10.1016/0890-5401(88)90031-4. ieee: L. Babai, B. Just, and F. Meyer auf der Heide, “On the limits of computations with the floor function,” Information and Computation, pp. 99–107, 1988. mla: Babai, László, et al. “On the Limits of Computations with the Floor Function.” Information and Computation, 1988, pp. 99–107, doi:10.1016/0890-5401(88)90031-4. 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' ...