Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Digitale Infotage für Schüler*innen, 7.-11. Februar, 15-19 Uhr, Anmeldungen unter go.upb.de/infotage2022

Thorsten Götte

Kontakt
Publikationen

Theorie verteilter Systeme

Wissenschaftlicher Mitarbeiter

Telefon:
+49 5251 60-6704
Fax:
+49 5251 60-6697
Büro:
F2.323
Besucher:
Fürstenallee 11

Liste im Research Information System öffnen

2021

Beep-And-Sleep: Message and Energy Efficient Set Cover

T. Götte, C. Kolb, C. Scheideler, J. Werthmann, in: Algorithms for Sensor Systems (ALGOSENSORS '21), 2021

Time-Optimal Construction of Overlays

T. Götte, K. Hinnenthal, C. Scheideler, J. Werthmann, in: Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21), ACM, 2021

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$.

The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation

J. Castenow, T. Götte, T. Knollmann, F. Meyer auf der Heide, in: Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021, Springer, 2021, pp. 289-304

2019

Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary

T. Götte, V.R. Vijayalakshmi, C. Scheideler, in: Proceedings of the 2019 IEEE 33rd International Parallel and Distributed Processing Symposium (IPDPS '19), IEEE, 2019

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.

Faster Construction of Overlay Networks

T. Götte, K. Hinnenthal, C. Scheideler, in: Structural Information and Communication Complexity, 2019

A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory

M. Feldmann, T. Götte, C. Scheideler, in: Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2019, pp. 149-164

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).

2018

On Underlay-Aware Self-Stabilizing Overlay Networks

T. Götte, C. Scheideler, A. Setzer, in: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018), Springer, 2018, pp. 50-64

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.

2017

Self-Stabilizing Spanners for Tree Metrics

T. Götte, Masterarbeit, Universität Paderborn, 2017

2015

Covering and Bridging im selbstorganisierenden Partikelsystem Amoebabot

T. Götte, Bachelorarbeit, Universität Paderborn, 2015

Liste im Research Information System öffnen

Die Universität der Informationsgesellschaft