@inproceedings{59268, author = {{Dou, Jinfeng and Götte, Thorsten and Hillebrandt, Henning and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)}}, editor = {{Meka, Raghu}}, isbn = {{978-3-95977-361-4}}, issn = {{1868-8969}}, pages = {{45:1–45:26}}, publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}}, title = {{{Distributed and Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs}}}, doi = {{10.4230/LIPIcs.ITCS.2025.45}}, volume = {{325}}, year = {{2025}}, } @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}}, } @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}}, } @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}}, } @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{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}}, } @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}}, } @inproceedings{26986, author = {{Castenow, Jannik and Götte, Thorsten and Knollmann, Till and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021}}, editor = {{Johnen, C. and Schiller, E.M. and Schmid, S.}}, location = {{Online}}, pages = {{289--304 }}, publisher = {{Springer}}, title = {{{The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation}}}, doi = {{10.1007/978-3-030-91081-5_19}}, volume = {{13046}}, year = {{2021}}, } @inproceedings{6976, abstract = {{We investigate the maintenance of overlay networks under massive churn, i.e. nodes joining and leaving the network. We assume an adversary that may churn a constant fraction $\alpha n$ of nodes over the course of $\mathcal{O}(\log n)$ rounds. In particular, the adversary has an almost up-to-date information of the network topology as it can observe an only slightly outdated topology that is at least $2$ rounds old. Other than that, we only have the provably minimal restriction that new nodes can only join the network via nodes that have taken part in the network for at least one round. Our contributions are as follows: First, we show that it is impossible to maintain a connected topology if adversary has up-to-date information about the nodes' connections. Further, we show that our restriction concerning the join is also necessary. As our main result present an algorithm that constructs a new overlay- completely independent of all previous overlays - every $2$ rounds. Furthermore, each node sends and receives only $\mathcal{O}(\log^3 n)$ messages each round. As part of our solution we propose the Linearized DeBruijn Swarm (LDS), a highly churn resistant overlay, which will be maintained by the algorithm. However, our approaches can be transferred to a variety of classical P2P Topologies where nodes are mapped into the $[0,1)$-interval.}}, author = {{Götte, Thorsten and Vijayalakshmi, Vipin Ravindran and Scheideler, Christian}}, booktitle = {{Proceedings of the 2019 IEEE 33rd International Parallel and Distributed Processing Symposium (IPDPS '19)}}, location = {{Rio de Janeiro, Brazil}}, publisher = {{IEEE}}, title = {{{Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary}}}, year = {{2019}}, } @inproceedings{12944, author = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian}}, booktitle = {{Structural Information and Communication Complexity}}, title = {{{Faster Construction of Overlay Networks}}}, doi = {{10.1007/978-3-030-24922-9_18}}, year = {{2019}}, } @inproceedings{13182, abstract = {{We consider congestion control in peer-to-peer distributed systems. The problem can be reduced to the following scenario: Consider a set $V$ of $n$ peers (called \emph{clients} in this paper) that want to send messages to a fixed common peer (called \emph{server} in this paper). We assume that each client $v \in V$ sends a message with probability $p(v) \in [0,1)$ and the server has a capacity of $\sigma \in \mathbb{N}$, i.e., it can recieve at most $\sigma$ messages per round and excess messages are dropped. The server can modify these probabilities when clients send messages. Ideally, we wish to converge to a state with $\sum p(v) = \sigma$ and $p(v) = p(w)$ for all $v,w \in V$. We propose a \emph{loosely} self-stabilizing protocol with a slightly relaxed legitimate state. Our protocol lets the system converge from \emph{any} initial state to a state where $\sum p(v) \in \left[\sigma \pm \epsilon\right]$ and $|p(v)-p(w)| \in O(\frac{1}{n})$. This property is then maintained for $\Omega(n^{\mathfrak{c}})$ rounds in expectation. In particular, the initial client probabilities and server variables are not necessarily well-defined, i.e., they may have arbitrary values. Our protocol uses only $O(W + \log n)$ bits of memory where $W$ is length of node identifiers, making it very lightweight. Finally we state a lower bound on the convergence time an see that our protocol performs asymptotically optimal (up to some polylogarithmic factor). }}, author = {{Feldmann, Michael and Götte, Thorsten and Scheideler, Christian}}, booktitle = {{Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}}, pages = {{149--164}}, publisher = {{Springer, Cham}}, title = {{{A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory}}}, doi = {{https://doi.org/10.1007/978-3-030-34992-9_13}}, year = {{2019}}, } @inproceedings{5222, abstract = {{We present a self-stabilizing protocol for an overlay network that constructs the Minimum Spanning Tree (MST) for an underlay that is modeled by a weighted tree. The weight of an overlay edge between two nodes is the weighted length of their shortest path in the tree. We rigorously prove that our protocol works correctly under asynchronous and non-FIFO message delivery. Further, the protocol stabilizes after O(N^2) asynchronous rounds where N is the number of nodes in the overlay. }}, author = {{Götte, Thorsten and Scheideler, Christian and Setzer, Alexander}}, booktitle = {{Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)}}, location = {{Tokyo, Japan}}, pages = {{50--64}}, publisher = {{Springer}}, title = {{{On Underlay-Aware Self-Stabilizing Overlay Networks}}}, volume = {{11201}}, year = {{2018}}, } @misc{701, author = {{Götte, Thorsten}}, publisher = {{Universität Paderborn}}, title = {{{Self-Stabilizing Spanners for Tree Metrics}}}, year = {{2017}}, } @misc{18003, author = {{Götte, Thorsten}}, publisher = {{Universität Paderborn}}, title = {{{Covering and Bridging im selbstorganisierenden Partikelsystem Amoebabot}}}, year = {{2015}}, }