TY - JOUR AU - Castenow, Jannik AU - Kling, Peter AU - Knollmann, Till AU - Meyer auf der Heide, Friedhelm ID - 29843 JF - Information and Computation KW - Computational Theory and Mathematics KW - Computer Science Applications KW - Information Systems KW - Theoretical Computer Science SN - 0890-5401 TI - A Discrete and Continuous Study of the Max-Chain-Formation Problem ER - TY - JOUR AB - 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. AU - Knollmann, Till AU - Scheideler, Christian ID - 21096 JF - Information and Computation SN - 0890-5401 TI - A self-stabilizing Hashed Patricia Trie ER - TY - JOUR AU - Czumaj, Artur AU - Meyer auf der Heide, Friedhelm AU - Stemann, Volker ID - 16565 JF - Information and Computation SN - 0890-5401 TI - Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures ER - TY - JOUR AU - Dietzfelbinger, M. AU - Meyer auf der Heide, Friedhelm ID - 16729 JF - Information and Computation SN - 0890-5401 TI - An Optimal Parallel Dictionary ER - TY - JOUR AU - Babai, László AU - Just, Bettina AU - Meyer auf der Heide, Friedhelm ID - 16763 JF - Information and Computation SN - 0890-5401 TI - On the limits of computations with the floor function ER -