TY - CONF
AB - 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$.
AU - Götte, Thorsten
AU - Hinnenthal, Kristian
AU - Scheideler, Christian
AU - Werthmann, Julian
ED - Censor-Hillel, Keren
ID - 22283
T2 - Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21)
TI - Time-Optimal Construction of Overlays
ER -
TY - CONF
AB - 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.
AU - Götte, Thorsten
AU - Vijayalakshmi, Vipin Ravindran
AU - Scheideler, Christian
ID - 6976
T2 - Proceedings of the 2019 IEEE 33rd International Parallel and Distributed Processing Symposium (IPDPS '19)
TI - Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary
ER -
TY - CONF
AB - 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).
AU - Feldmann, Michael
AU - Götte, Thorsten
AU - Scheideler, Christian
ID - 13182
T2 - Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
TI - A Loosely Self-stabilizing Protocol for Randomized Congestion Control with Logarithmic Memory
ER -
TY - CONF
AU - Götte, Thorsten
AU - Hinnenthal, Kristian
AU - Scheideler, Christian
ID - 12944
T2 - Structural Information and Communication Complexity
TI - Faster Construction of Overlay Networks
ER -
TY - CONF
AB - 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.
AU - Götte, Thorsten
AU - Scheideler, Christian
AU - Setzer, Alexander
ID - 5222
T2 - Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2018)
TI - On Underlay-Aware Self-Stabilizing Overlay Networks
VL - 11201
ER -
TY - GEN
AU - Götte, Thorsten
ID - 701
TI - Self-Stabilizing Spanners for Tree Metrics
ER -
TY - GEN
AU - Götte, Thorsten
ID - 18003
TI - Covering and Bridging im selbstorganisierenden Partikelsystem Amoebabot
ER -