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.

Bildinformationen anzeigen

Kristian Hinnenthal, M.Sc.

 Kristian Hinnenthal, M.Sc.

Theorie verteilter Systeme

Wissenschaftlicher Mitarbeiter

+49 5251 60-6730
+49 5251 60-6697
Fürstenallee 11
33102 Paderborn

Sonderforschungsbereich 901

Wissenschaftlicher Mitarbeiter


  • Overlaynetzwerke
  • Hybride Netzwerke
  • (Hybride) Programmierbare Materie


  • WS12/13: Übungen zu "Modellierung"
  • SS13: Übungen zu "Grundlagen der Programmiersprachen"
  • WS13/14: Übungen zu "Modellierung"
  • WS14/15: Übungen zu "Modellierung"
  • WS16/17: Übungen zu "Fundamental Algorithms"
  • WS17/18: Übungen zu "Fundamental Algorithms"
  • SS18: Übungen zu "Digitaltechnik"
  • WS18/19: Übungen zu "Berechenbarkeit und Komplexität"
  • SS19-WS19/20: Projektgruppe "OverHyPeD"

Veröffentlichungen (RIS-DB)

Liste im Research Information System öffnen

Formbildung selbstorganisierender Partikelsysteme

K. Hinnenthal, Bachelorarbeit, 2014

Aggregation in Overlay Networks

K. Hinnenthal, Masterarbeit, Universität Paderborn, 2016

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.

    Distributed Monitoring of Network Properties: The Power of Hybrid Networks

    R. Gmyr, K. Hinnenthal, C. Scheideler, C. Sohler, in: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017, pp. 137:1--137:15

    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.

      Forming Tile Shapes with Simple Robots

      R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, T.F. Strothmann, in: Proceedings of the 24th International Conference on DNA Computing and Molecular Programming, Springer International Publishing, 2018, pp. 122-138

      Shape Recognition by a Finite Automaton Robot

      R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, in: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, 2018, pp. 52:1-52:15

      Fast Distributed Algorithms for LP-Type Problems of Low Dimension

      K. Hinnenthal, C. Scheideler, M. Struijs, in: 33rd International Symposium on Distributed Computing (DISC 2019), 2019

      Shortest Paths in a Hybrid Network Model

      J. Augustine, K. Hinnenthal, F. Kuhn, C. Scheideler, P. Schneider, in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 1280-1299

      Distributed Computation in Node-Capacitated Networks

      J. Augustine, M. Ghaffari, R. Gmyr, K. Hinnenthal, F. Kuhn, J. Li, C. Scheideler, in: Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2019, pp. 69--79

      Faster Construction of Overlay Networks

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

      Computing by Programmable Particles

      J.J. Daymude, K. Hinnenthal, A.W. Richa, C. Scheideler, in: Distributed Computing by Mobile Entities, Current Research in Moving and Computing., Springer, Cham, 2019, pp. 615-681

      Convex Hull Formation for Programmable Matter

      J.J. Daymude, R. Gmyr, K. Hinnenthal, I. Kostitsyna, C. Scheideler, A.W. Richa, in: Proceedings of the 21st International Conference on Distributed Computing and Networking, 2020

      Forming tile shapes with simple robots

      R. Gmyr, K. Hinnenthal, I. Kostitsyna, F. Kuhn, D. Rudolph, C. Scheideler, T. Strothmann, Nat. Comput. (2020), 19(2), pp. 375-390

      Fast Hybrid Network Algorithms for Shortest Paths in Sparse Graphs

      M. Feldmann, K. Hinnenthal, C. Scheideler, in: Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020

      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.

        Liste im Research Information System öffnen


        • "Shape Recognition by a Finite Automaton Robot", EuroCG 2018, Berlin
        • "Forming Tile Shapes with Simple Robots", BDA 2018, London
        • "O-Hull Formation for Programmable Matter", EuroCG 2018, Utrecht
        • "Fast Shape Formation with Hybrid Programmable Matter", BDA 2019, Toronto

        Die Universität der Informationsgesellschaft