@inproceedings{13652, author = {{Hinnenthal, Kristian and Scheideler, Christian and Struijs, Martijn}}, booktitle = {{33rd International Symposium on Distributed Computing (DISC 2019)}}, title = {{{Fast Distributed Algorithms for LP-Type Problems of Low Dimension}}}, doi = {{10.4230/LIPICS.DISC.2019.23}}, year = {{2019}}, } @inproceedings{27051, author = {{Augustine, John and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp}}, booktitle = {{Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020}}, editor = {{Chawla, Shuchi}}, pages = {{1280--1299}}, publisher = {{SIAM}}, title = {{{Shortest Paths in a Hybrid Network Model}}}, doi = {{10.1137/1.9781611975994.78}}, year = {{2020}}, } @article{17808, author = {{Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian and Strothmann, Thim}}, journal = {{Nat. Comput.}}, number = {{2}}, pages = {{375--390}}, title = {{{Forming tile shapes with simple robots}}}, doi = {{10.1007/s11047-019-09774-2}}, volume = {{19}}, year = {{2020}}, } @inproceedings{20755, abstract = {{We consider the problem of computing shortest paths in \emph{hybrid networks}, in which nodes can make use of different communication modes. For example, mobile phones may use ad-hoc connections via Bluetooth or Wi-Fi in addition to the cellular network to solve tasks more efficiently. Like in this case, the different communication modes may differ considerably in range, bandwidth, and flexibility. We build upon the model of Augustine et al. [SODA '20], which captures these differences by a \emph{local} and a \emph{global} mode. Specifically, the local edges model a fixed communication network in which $O(1)$ messages of size $O(\log n)$ can be sent over every edge in each synchronous round. The global edges form a clique, but nodes are only allowed to send and receive a total of at most $O(\log n)$ messages over global edges, which restricts the nodes to use these edges only very sparsely. We demonstrate the power of hybrid networks by presenting algorithms to compute Single-Source Shortest Paths and the diameter very efficiently in \emph{sparse graphs}. Specifically, we present exact $O(\log n)$ time algorithms for cactus graphs (i.e., graphs in which each edge is contained in at most one cycle), and $3$-approximations for graphs that have at most $n + O(n^{1/3})$ edges and arboricity $O(\log n)$. For these graph classes, our algorithms provide exponentially faster solutions than the best known algorithms for general graphs in this model. Beyond shortest paths, we also provide a variety of useful tools and techniques for hybrid networks, which may be of independent interest. }}, author = {{Feldmann, Michael and Hinnenthal, Kristian and Scheideler, Christian}}, booktitle = {{Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS)}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, title = {{{Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs}}}, doi = {{10.4230/LIPIcs.OPODIS.2020.31}}, year = {{2020}}, } @article{16902, abstract = {{The maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. This paper presents a survey of state-of-the-art algorithms to design and repair overlay networks in a distributed manner. In particular, we discuss basic algorithmic primitives to preserve connectivity, review algorithms for the fundamental problem of graph linearization, and then survey self-stabilizing algorithms for metric and scalable topologies. We also identify open problems and avenues for future research. }}, author = {{Feldmann, Michael and Scheideler, Christian and Schmid, Stefan}}, journal = {{ACM Computing Surveys}}, publisher = {{ACM}}, title = {{{Survey on Algorithms for Self-Stabilizing Overlay Networks}}}, doi = {{10.1145/3397190}}, year = {{2020}}, } @inproceedings{16903, abstract = {{We consider the clock synchronization problem in the (discrete) beeping model: Given a network of $n$ nodes with each node having a clock value $\delta(v) \in \{0,\ldots T-1\}$, the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume \emph{arbitrary activations} for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to $\{0,\ldots,T-1\}$). We give an asymptotically optimal algorithm that runs in $4D + \Bigl\lfloor \frac{D}{\lfloor T/4 \rfloor} \Bigr \rfloor \cdot (T \mod 4) = O(D)$ rounds, where $D$ is the diameter of the network. Once all nodes are in sync, they beep at the same round every $T$ rounds. The algorithm drastically improves on the $O(T D)$-bound of \cite{firefly_sync} (where $T$ is required to be at least $4n$, so the bound is no better than $O(nD)$). Our algorithm is very simple as nodes only have to maintain $3$ bits in addition to the $\lceil \log T \rceil$ bits needed to maintain the clock. Furthermore we investigate the complexity of \emph{self-stabilizing} solutions for the clock synchronization problem: We first show lower bounds of $\Omega(\max\{T,n\})$ rounds on the runtime and $\Omega(\log(\max\{T,n\}))$ bits of memory required for any such protocol. Afterwards we present a protocol that runs in $O(\max\{T,n\})$ rounds using at most $O(\log(\max\{T,n\}))$ bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.}}, author = {{Feldmann, Michael and Khazraei, Ardalan and Scheideler, Christian}}, booktitle = {{Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}}, publisher = {{ACM}}, title = {{{Time- and Space-Optimal Discrete Clock Synchronization in the Beeping Model}}}, doi = {{10.1145/3350755.3400246}}, year = {{2020}}, } @inproceedings{15169, author = {{Castenow, Jannik and Kolb, Christina and Scheideler, Christian}}, booktitle = {{Proceedings of the 21st International Conference on Distributed Computing and Networking (ICDCN)}}, location = {{Kolkata, Indien}}, publisher = {{ACM}}, title = {{{A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks}}}, year = {{2020}}, } @inproceedings{16346, author = {{Daymude, Joshua J. and Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Scheideler, Christian and Richa, Andréa W.}}, booktitle = {{Proceedings of the 21st International Conference on Distributed Computing and Networking}}, isbn = {{9781450377515}}, title = {{{Convex Hull Formation for Programmable Matter}}}, doi = {{10.1145/3369740.3372916}}, year = {{2020}}, } @inproceedings{25105, author = {{Dolev, Shlomi and Prasadh Narayanan, Ram and Scheideler, Christian and Schindelhauer, Christian}}, booktitle = {{NANOCOM '21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021}}, editor = {{Galluccio, Laura and Mitra, Urbashi and Magarini, Maurizio and Abada, Sergi and Taynnan Barros, Michael and Krishnaswamy, Bhuvana}}, pages = {{30:1--30:2}}, publisher = {{ACM}}, title = {{{Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization}}}, doi = {{10.1145/3477206.3477471}}, year = {{2021}}, } @inproceedings{28917, author = {{Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and Dolev, Shlomi}}, booktitle = {{Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, (SSS) 2021, Virtual Event, November 17-20, 2021, Proceedings}}, editor = {{Johnen, Colette and Michael Schiller, Elad and Schmid, Stefan}}, pages = {{484--488}}, publisher = {{Springer}}, title = {{{Coordinating Amoebots via Reconfigurable Circuits}}}, doi = {{10.1007/978-3-030-91081-5\_34}}, volume = {{13046}}, year = {{2021}}, } @inproceedings{27048, author = {{Dolev, Shlomi and Prasadh Narayanan, Ram and Scheideler, Christian and Schindelhauer, Christian}}, booktitle = {{NANOCOM '21: The Eighth Annual ACM International Conference on Nanoscale Computing and Communication, Virtual Event, Italy, September 7 - 9, 2021}}, editor = {{Galluccio, Laura and Mitra, Urbashi and Magarini, Maurizio and Abada, Sergi and Taynnan Barros, Michael and Krishnaswamy, Bhuvana}}, pages = {{30:1--30:2}}, publisher = {{ACM}}, title = {{{Logarithmic Time MIMO Based Self-Stabilizing Clock Synchronization}}}, doi = {{10.1145/3477206.3477471}}, year = {{2021}}, } @inproceedings{27050, author = {{J. Daymude, Joshua and W. Richa, Andrea and Scheideler, Christian}}, booktitle = {{35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference)}}, editor = {{Gilbert, Seth}}, pages = {{20:1--20:19}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, title = {{{The Canonical Amoebot Model: Algorithms and Concurrency Control}}}, doi = {{10.4230/LIPIcs.DISC.2021.20}}, volume = {{209}}, year = {{2021}}, } @inproceedings{22283, abstract = {{ We show how to construct an overlay network of constant degree and diameter $O(\log n)$ in time $O(\log n)$ starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of and establish new connections by sending node identifiers. If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only $O(\log n)$ messages in each round in time $O(\log n)$, w.h.p., which beats the currently best $O(\log^{3/2} n)$ time algorithm of [Götte et al., SIROCCO'19]. Since the problem cannot be solved faster than by using pointer jumping for $O(\log n)$ rounds (which would even require each node to communicate $\Omega(n)$ bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX'14]. Additionally, we show how our algorithm can be used to efficiently solve graph problems in \emph{hybrid networks} [Augustine et al., SODA'20]. Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the \emph{initial} edges is unrestricted. In contrast, only polylogarithmically many messages can be communicated over edges that have been established throughout an algorithm's execution. For an (undirected) graph $G$ with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in time $O(\log n)$, w.h.p. Furthermore, we show how to compute an MIS in time $O(\log d + \log \log n)$, w.h.p., where $d$ is the initial degree of $G$.}}, author = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21)}}, editor = {{Censor-Hillel, Keren}}, location = {{Virtual}}, publisher = {{ACM}}, title = {{{Time-Optimal Construction of Overlays}}}, doi = {{10.1145/3465084.3467932}}, year = {{2021}}, } @inproceedings{30217, author = {{Coy, Sam and Czumaj, Artur and Feldmann, Michael and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp and Struijs, Martijn}}, booktitle = {{25th International Conference on Principles of Distributed Systems, OPODIS 2021, December 13-15, 2021, Strasbourg, France}}, editor = {{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia}}, pages = {{11:1–11:23}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, title = {{{Near-Shortest Path Routing in Hybrid Communication Networks}}}, doi = {{10.4230/LIPIcs.OPODIS.2021.11}}, volume = {{217}}, year = {{2021}}, } @inbook{26888, author = {{Götte, Thorsten and Kolb, Christina and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{Algorithms for Sensor Systems (ALGOSENSORS '21)}}, issn = {{0302-9743}}, location = {{Lisbon, Portgual}}, title = {{{Beep-And-Sleep: Message and Energy Efficient Set Cover}}}, doi = {{10.1007/978-3-030-89240-1_7}}, year = {{2021}}, } @article{31060, author = {{Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and Dolev, Shlomi}}, journal = {{J. Comput. Biol.}}, number = {{4}}, pages = {{317–343}}, title = {{{Coordinating Amoebots via Reconfigurable Circuits}}}, doi = {{10.1089/cmb.2021.0363}}, volume = {{29}}, year = {{2022}}, } @inproceedings{32602, author = {{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}}, booktitle = {{28th International Conference on DNA Computing and Molecular Programming (DNA 28)}}, editor = {{Ouldridge, Thomas E. and Wickham, Shelley F. J.}}, isbn = {{978-3-95977-253-2}}, issn = {{1868-8969}}, pages = {{8:1–8:22}}, publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}}, title = {{{The Structural Power of Reconfigurable Circuits in the Amoebot Model}}}, doi = {{10.4230/LIPIcs.DNA.28.8}}, volume = {{238}}, year = {{2022}}, } @inproceedings{32603, author = {{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel}}, booktitle = {{28th International Conference on DNA Computing and Molecular Programming (DNA 28)}}, editor = {{Ouldridge, Thomas E. and Wickham, Shelley F. J.}}, isbn = {{978-3-95977-253-2}}, issn = {{1868-8969}}, pages = {{9:1–9:22}}, publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}}, title = {{{Fault-Tolerant Shape Formation in the Amoebot Model}}}, doi = {{10.4230/LIPIcs.DNA.28.9}}, volume = {{238}}, year = {{2022}}, } @inproceedings{33230, author = {{Daymude, Joshua J. and Richa, Andréa W. and Scheideler, Christian}}, booktitle = {{1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference}}, editor = {{Aspnes, James and Michail, Othon}}, pages = {{12:1–12:19}}, publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}}, title = {{{Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems}}}, doi = {{10.4230/LIPIcs.SAND.2022.12}}, volume = {{221}}, year = {{2022}}, } @inproceedings{33240, author = {{Götte, Thorsten and Scheideler, Christian}}, booktitle = {{SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022}}, editor = {{Agrawal, Kunal and Lee, I-Ting Angelina}}, pages = {{99–101}}, publisher = {{ACM}}, title = {{{Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion}}}, doi = {{10.1145/3490148.3538556}}, year = {{2022}}, } @inproceedings{30987, author = {{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel}}, booktitle = {{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}}, editor = {{Aspnes, James and Michail, Othon}}, isbn = {{978-3-95977-224-2}}, issn = {{1868-8969}}, pages = {{23:1–23:3}}, publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}}, title = {{{Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model}}}, doi = {{10.4230/LIPIcs.SAND.2022.23}}, volume = {{221}}, year = {{2022}}, } @inproceedings{33967, author = {{Aguiliera, Marcos and Richa, Andréa W. and Schwarzmann, Alexander A. and Panconesi, Alessandro and Scheideler, Christian and Woelfel, Philipp}}, booktitle = {{PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022}}, editor = {{Milani, Alessia and Woelfel, Philipp}}, pages = {{1}}, publisher = {{ACM}}, title = {{{2022 Edsger W. Dijkstra Prize in Distributed Computing}}}, doi = {{10.1145/3519270.3538411}}, year = {{2022}}, } @article{21096, abstract = {{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.}}, author = {{Knollmann, Till and Scheideler, Christian}}, issn = {{0890-5401}}, journal = {{Information and Computation}}, title = {{{A self-stabilizing Hashed Patricia Trie}}}, doi = {{10.1016/j.ic.2021.104697}}, year = {{2022}}, } @article{43109, author = {{Götte, Thorsten and Kolb, Christina and Scheideler, Christian and Werthmann, Julian}}, journal = {{Theor. Comput. Sci.}}, pages = {{113756}}, title = {{{Beep-and-Sleep: Message and Energy Efficient Set Cover}}}, doi = {{10.1016/j.tcs.2023.113756}}, volume = {{950}}, year = {{2023}}, } @inproceedings{45188, author = {{Werthmann, Julian and Scheideler, Christian and Coy, Sam and Czumaj, Artur and Schneider, Philipp}}, title = {{{Routing Schemes for Hybrid Communication Networks}}}, doi = {{10.48550/ARXIV.2210.05333}}, year = {{2023}}, } @inproceedings{45193, author = {{Dou, Jinfeng and Götte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC '23)}}, location = {{Orlando, USA}}, title = {{{Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs}}}, year = {{2023}}, } @article{45192, author = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}}, journal = {{Distributed Computing}}, title = {{{Time-Optimal Construction of Overlays}}}, doi = {{https://doi.org/10.1007/s00446-023-00442-4}}, year = {{2023}}, } @inbook{45875, author = {{Götte, Thorsten and Knollmann, Till and Meyer auf der Heide, Friedhelm and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{On-The-Fly Computing -- Individualized IT-services in dynamic markets}}, editor = {{Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}}, pages = {{1----20}}, publisher = {{Heinz Nixdorf Institut, Universität Paderborn}}, title = {{{Capabilities and Limitations of Local Strategies in Dynamic Networks}}}, doi = {{10.5281/zenodo.8060372}}, volume = {{412}}, year = {{2023}}, } @inbook{45891, author = {{Blömer, Johannes and Eidens, Fabian and Jager, Tibor and Niehues, David and Scheideler, Christian}}, booktitle = {{On-The-Fly Computing -- Individualized IT-services in dynamic markets}}, editor = {{Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}}, pages = {{145--164}}, publisher = {{Heinz Nixdorf Institut, Universität Paderborn}}, title = {{{Robustness and Security}}}, doi = {{10.5281/zenodo.8068629}}, volume = {{412}}, year = {{2023}}, }