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

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


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


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


Faster Construction of Overlay Networks

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


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