@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},
}
@inproceedings{16346,
author = {Daymude, Joshua J. and Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Scheideler, Christian and Richa, Andréa W.},
booktitle = {Proceedings of the 21st International Conference on Distributed Computing and Networking},
isbn = {9781450377515},
title = {{Convex Hull Formation for Programmable Matter}},
doi = {10.1145/3369740.3372916},
year = {2020},
}
@article{17808,
author = {Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian and Strothmann, Thim},
journal = {Nat. Comput.},
number = {2},
pages = {375--390},
title = {{Forming tile shapes with simple robots}},
doi = {10.1007/s11047-019-09774-2},
volume = {19},
year = {2020},
}
@inproceedings{20755,
abstract = {We consider the problem of computing shortest paths in \emph{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 \emph{local} and a \emph{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 \emph{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.
},
author = {Feldmann, Michael and Hinnenthal, Kristian and Scheideler, Christian},
booktitle = {Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS)},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs}},
doi = {10.4230/LIPIcs.OPODIS.2020.31},
year = {2020},
}
@inproceedings{13652,
author = {Hinnenthal, Kristian and Scheideler, Christian and Struijs, Martijn},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
title = {{Fast Distributed Algorithms for LP-Type Problems of Low Dimension}},
doi = {10.4230/LIPICS.DISC.2019.23},
year = {2019},
}
@inproceedings{15627,
author = {Augustine, John and Hinnenthal, Kristian and Kuhn, Fabian and Scheideler, Christian and Schneider, Philipp},
booktitle = {Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
isbn = {9781611975994},
pages = {1280--1299},
title = {{Shortest Paths in a Hybrid Network Model}},
doi = {10.1137/1.9781611975994.78},
year = {2019},
}
@inproceedings{8871,
author = {Augustine, John and Ghaffari, Mohsen and Gmyr, Robert and Hinnenthal, Kristian and Kuhn, Fabian and Li, Jason and Scheideler, Christian},
booktitle = {Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures},
pages = {69----79},
publisher = {ACM},
title = {{Distributed Computation in Node-Capacitated Networks}},
doi = {10.1145/3323165.3323195},
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},
}
@inbook{9599,
author = {Daymude, Joshua J. and Hinnenthal, Kristian and Richa, Andréa W. and Scheideler, Christian},
booktitle = {Distributed Computing by Mobile Entities, Current Research in Moving and Computing.},
pages = {615--681},
publisher = {Springer, Cham},
title = {{Computing by Programmable Particles}},
doi = {https://doi.org/10.1007/978-3-030-11072-7_22},
year = {2019},
}
@inproceedings{5764,
author = {Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian and Strothmann, Thim Frederik},
booktitle = {Proceedings of the 24th International Conference on DNA Computing and Molecular Programming},
pages = {122--138},
publisher = {Springer International Publishing},
title = {{Forming Tile Shapes with Simple Robots}},
doi = {10.1007/978-3-030-00030-1_8},
year = {2018},
}
@inproceedings{5986,
author = {Gmyr, Robert and Hinnenthal, Kristian and Kostitsyna, Irina and Kuhn, Fabian and Rudolph, Dorian and Scheideler, Christian},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK},
pages = {52:1--52:15},
title = {{Shape Recognition by a Finite Automaton Robot}},
doi = {10.4230/LIPIcs.MFCS.2018.52},
year = {2018},
}
@inproceedings{105,
abstract = {We initiate the study of network monitoring algorithms in a class of hybrid networks in which the nodes are connected by an external network and an internal network (as a short form for externally and internally controlled network). While the external network lies outside of the control of the nodes (or in our case, the monitoring protocol running in them) and might be exposed to continuous changes, the internal network is fully under the control of the nodes. As an example, consider a group of users with mobile devices having access to the cell phone infrastructure. While the network formed by the WiFi connections of the devices is an external network (as its structure is not necessarily under the control of the monitoring protocol), the connections between the devices via the cell phone infrastructure represent an internal network (as it can be controlled by the monitoring protocol). Our goal is to continuously monitor properties of the external network with the help of the internal network. We present scalable distributed algorithms that efficiently monitor the number of edges, the average node degree, the clustering coefficient, the bipartiteness, and the weight of a minimum spanning tree. Their performance bounds demonstrate that monitoring the external network state with the help of an internal network can be done much more efficiently than just using the external network, as is usually done in the literature.},
author = {Gmyr, Robert and Hinnenthal, Kristian and Scheideler, Christian and Sohler, Christian},
booktitle = {Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP)},
pages = {137:1----137:15},
title = {{Distributed Monitoring of Network Properties: The Power of Hybrid Networks}},
doi = {10.4230/LIPIcs.ICALP.2017.137},
year = {2017},
}
@misc{223,
abstract = {We consider the problem of aggregation in overlay networks. We use a synchronous time model in which each node has polylogarithmic memory and can send at most a polylogarithmic number of messages per round. We investigate how to quickly compute the result of an aggregate functionf over elements that are distributed among the nodes of the network such that the result is eventually known by a selected root node. We show how to compute distributive aggregate functions such as SUM, MAX, and OR in time $O(\log n / \log\log n)$ using a tree that is created in a pre-processing phase. If only a polylogarithmic number of data items need to be aggregated, we show how to compute the result in time $O(\sqrt{\log n / \log\log n})$. Furthermore, we show how to compute holistic aggregate functions such as DISTINCT, SMALLEST(k) and MODE(k) in time $O(\log n / \log\log n)$. Finally, we show a lower bound of $\Omega(\sqrt{\log n / \log\log n})$ for deterministic algorithms that compute any of the aggregate functions in the scope of the thesis.},
author = {Hinnenthal, Kristian},
publisher = {Universität Paderborn},
title = {{Aggregation in Overlay Networks}},
year = {2016},
}
@misc{18002,
author = {Hinnenthal, Kristian},
title = {{Formbildung selbstorganisierender Partikelsysteme}},
year = {2014},
}