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

Models and Algorithms for Hybrid Networks and Hybrid Programmable Matter - Hinnenthal, Kristian

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

Shortest Paths in a Hybrid Network Model - Augustine, John; Hinnenthal, Kristian; Kuhn, Fabian; Scheideler, Christian; Schneider, Philipp (Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020)

Forming tile shapes with simple robots - Gmyr, Robert; Hinnenthal, Kristian; Kostitsyna, Irina; Kuhn, Fabian; Rudolph, Dorian; Scheideler, Christian; Strothmann, Thim (Nat. Comput.)

Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs - Feldmann, Michael; Hinnenthal, Kristian; Scheideler, Christian (Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS))
We consider the problem of computing shortest paths in 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 local and a 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 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.

Convex Hull Formation for Programmable Matter - Daymude, Joshua J.; Gmyr, Robert; Hinnenthal, Kristian; Kostitsyna, Irina; Scheideler, Christian; Richa, Andréa W. (Proceedings of the 21st International Conference on Distributed Computing and Networking)

Distributed Computation in Node-Capacitated Networks - Augustine, John; Ghaffari, Mohsen; Gmyr, Robert; Hinnenthal, Kristian; Kuhn, Fabian; Li, Jason; Scheideler, Christian (Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures)

Computing by Programmable Particles - Daymude, Joshua J.; Hinnenthal, Kristian; Richa, Andréa W.; Scheideler, Christian (Distributed Computing by Mobile Entities, Current Research in Moving and Computing.)

Faster Construction of Overlay Networks - Götte, Thorsten; Hinnenthal, Kristian; Scheideler, Christian (Structural Information and Communication Complexity)