TY - GEN AB - Bei dem betrachteten Speicherproblem werden Daten mit verschiedenen Zugriffswahrscheinlichkeiten auf Speicher mit verschiedenen Bandbreiten und Kapazitäten aufgeteilt, dabei sind Replikate erlaubt. Es wird die nach Zugriffswahrscheinlichkeit gewichtete kleinste Bandbreite der Daten maximiert. Wir zeigen, dass sowohl das diskrete Speicherproblem, bei dem die Bandbreite der Speicher jeweils gleichmäßig auf die dort abgelegten Daten aufgeteilt wird, als auch das kontinuierliche Speicherproblem, bei dem die Bandbreite der Speicher beliebig auf abgelegte Daten verteilt werden darf, NP-schwer ist. Es können also, wenn P ̸ = NP, keine effizienten Algorithmen für eine optimale Lösung existieren. Stattdessen zeigen wir jeweils einen 1/2-Approximationsalgorithmus. AU - Decking, Leo ID - 48430 TI - Zuweisung verteilter Speicher unter Maximierung der minimalen gewichteten Bandbreite ER - TY - GEN AU - Nickel, Alexander ID - 49494 TI - Entwicklung und Analyse von Formeln zur Abschätzung der Renderingzeit eines Frames ER - TY - GEN AU - Telaprolu, Vipasyan ID - 49493 TI - Reconstruction of 3D Surfels from Neural Radiance Fields ER - TY - GEN AU - Friemel, Jonas ID - 49492 TI - Shape Reconfiguration by Hybrid Programmable Matter ER - TY - GEN AU - Beckendorf, Björn ID - 52317 TI - Self-Stabilizing Skip-Graph with Growth-bounded Metric ER - TY - GEN AU - Roopa, Rajanna ID - 30152 TI - Evaluation of Algorithms for the Node Capacitated Clique ER - TY - GEN AU - Korzeczek, Sebastian ID - 30198 TI - Aufarbeitung und lmplementierung von DAG-Rider ER - TY - GEN AU - Nachtigall, Marcel ID - 30199 TI - Hybrid Routing in Three Dimensions ER - TY - JOUR AU - Feldmann, Michael AU - Padalkin, Andreas AU - Scheideler, Christian AU - Dolev, Shlomi ID - 31060 IS - 4 JF - J. Comput. Biol. TI - Coordinating Amoebots via Reconfigurable Circuits VL - 29 ER - TY - GEN AU - Hillebrandt, Henning ID - 31947 TI - Verteiltes Berechnen kompakter Routingtabellen in Unit Disk Graphen ER - TY - CONF AU - Padalkin, Andreas AU - Scheideler, Christian AU - Warner, Daniel ED - Ouldridge, Thomas E. ED - Wickham, Shelley F. J. ID - 32602 SN - 1868-8969 T2 - 28th International Conference on DNA Computing and Molecular Programming (DNA 28) TI - The Structural Power of Reconfigurable Circuits in the Amoebot Model VL - 238 ER - TY - CONF AU - Kostitsyna, Irina AU - Scheideler, Christian AU - Warner, Daniel ED - Ouldridge, Thomas E. ED - Wickham, Shelley F. J. ID - 32603 SN - 1868-8969 T2 - 28th International Conference on DNA Computing and Molecular Programming (DNA 28) TI - Fault-Tolerant Shape Formation in the Amoebot Model VL - 238 ER - TY - CONF AU - Daymude, Joshua J. AU - Richa, Andréa W. AU - Scheideler, Christian ED - Aspnes, James ED - Michail, Othon ID - 33230 T2 - 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference TI - Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems VL - 221 ER - TY - CONF AU - Götte, Thorsten AU - Scheideler, Christian ED - Agrawal, Kunal ED - Lee, I-Ting Angelina ID - 33240 T2 - SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022 TI - Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion ER - TY - CONF AU - Kostitsyna, Irina AU - Scheideler, Christian AU - Warner, Daniel ED - Aspnes, James ED - Michail, Othon ID - 30987 SN - 1868-8969 T2 - 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) TI - Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model VL - 221 ER - TY - CONF AU - Aguiliera, Marcos AU - Richa, Andréa W. AU - Schwarzmann, Alexander A. AU - Panconesi, Alessandro AU - Scheideler, Christian AU - Woelfel, Philipp ED - Milani, Alessia ED - Woelfel, Philipp ID - 33967 T2 - PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022 TI - 2022 Edsger W. Dijkstra Prize in Distributed Computing ER - TY - GEN ED - Scheideler, Christian ID - 33968 SN - 978-3-95977-255-6 TI - 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA VL - 246 ER - TY - THES AU - Kolb, Christina ID - 30239 TI - Competitive Routing in Hybrid Communications Networks and Message efficient SetCover in AdHoc Networks 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 - THES AU - Hinnenthal, Kristian ID - 24887 TI - Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter ER -