Beep-and-Sleep: Message and Energy Efficient Set Cover - Götte, Thorsten; Kolb, Christina; Scheideler, Christian; Werthmann, Julian (Theor. Comput. Sci.)

Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs - Dou, Jinfeng; Götte, Thorsten; Hillebrandt, Henning; Scheideler, Christian; Werthmann, Julian (Proc. of the 42nd ACM Symposium on Principles of Distributed Computing (PODC '23))

Time-Optimal Construction of Overlays - Götte, Thorsten; Hinnenthal, Kristian; Scheideler, Christian; Werthmann, Julian (Distributed Computing)

Capabilities and Limitations of Local Strategies in Dynamic Networks - Götte, Thorsten; Knollmann, Till; Meyer auf der Heide, Friedhelm; Scheideler, Christian; Werthmann, Julian (On-The-Fly Computing -- Individualized IT-services in dynamic markets)

Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion - Götte, Thorsten; Scheideler, Christian (SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022)

Time-Optimal Construction of Overlays - Götte, Thorsten; Hinnenthal, Kristian; Scheideler, Christian; Werthmann, Julian (Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21))
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 $Ω(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 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 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$.

Beep-And-Sleep: Message and Energy Efficient Set Cover - Götte, Thorsten; Kolb, Christina; Scheideler, Christian; Werthmann, Julian (Algorithms for Sensor Systems (ALGOSENSORS '21))

The Max-Line-Formation Problem – And New Insights for Gathering and Chain-Formation - Castenow, Jannik; Götte, Thorsten; Knollmann, Till; Meyer auf der Heide, Friedhelm (Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021)

Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary - Götte, Thorsten; Vijayalakshmi, Vipin Ravindran; Scheideler, Christian (Proceedings of the 2019 IEEE 33rd International Parallel and Distributed Processing Symposium (IPDPS '19))
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 $α 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 - Götte, Thorsten; Hinnenthal, Kristian; Scheideler, Christian (Structural Information and Communication Complexity)