Research

Future IT systems will be to a far greater extent than today consist of many different components. Such systems are often too large and dynamic, to be managed centrally. Therefore, we focus on algorithmic problems dealing with decentralized methods for the control and optimization of such systems.

Modern distributed IT-systems, such as the Internet, peer-topeersystems, and wireless communication systems, as wellas swarms of sensors or mobile robots, pose new challengesfor algorithm design. As their components (peers, robots, etc.)only have a limited local view of a system‘s current state, newlocal-algorithmic methods for utilizing and controlling thesesystems have to be developed. Our research addresses suchproblems from various perspectives.

Resource Management

Many modern applications will generate so much data in the foreseeable future that it will be essential to place the corresponding service close to the user. In order to keep the placement costs of these services low, we are working on the efficient adjustment of the placement of a fixed amount of resources in order to minimise the costs of incoming requests. One focus is currently the investigation of scenarios in which different services can be offered and demanded. In particular, offering several services in one place, and the demand for combinations of services makes it challenging to decide which combinations should be offered and where.

Scheduling

In modern heterogeneous data centres, scheduling, i.e. the distribution of tasks among resources, is becoming more and more important. We develop and analyse scheduling algorithms that efficiently manage the usage of resources in huge computing centres while guaranteeing provably good performance. Currently, a special focus is on the question of how a combination of a resource-limited server and a cloud can be used efficiently and cost-effectively.

Local strategies for robot swarms

We investigate the theory of swarm robotics, in which we study the tasks that can be performed by a large swarm of robots and the properties that the robots need to accomplish them. Due to the high number of robots, a single robot cannot overlook the entire swarm, but only perceives a small part of the swarm in its immediate vicinity. We are dealing with strategies for robot swarms wherein the goal is to bring the swarm into a certain formation. Even geometrically simple configurations, such as a point or a circle, become a big challenge due to the local views of the robots. Our focus is on the design and analysis of the correctness of such strategies, and in particular on the runtime analysis.

Algorithmic foundations of computer graphics

In order to navigate in a virtual three-dimensional world and to create a realistic impression, high demands are made on data structures and algorithms which are used to manage such worlds and render them as images. We focus on the development of algorithms that can compute an approximate rendering of the virtual world in real time, depending on the viewer's viewing position and direction. A current focus is the development of so-called progressive sampling, which allows the clustering of related geometric primitives to be done efficiently on the graphics card.

Algorithmic game theory

A single party, whether a person, company or state tends to pursue their interests given the situation, whereas the world is combined from multiple interacting parties. We analyse behaviours in such interactions, sometimes adjusting the interactions, while assuming each party optimises for their interests. We model and study the network countenance of agents with social network analyses from the algorithmic and the game-theoretic points of view.



Publications 2021

M. Bienkowski, B. Feldkord, P. Schmidt: A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location. In: Proceedings of the 38th Symposium on Theoretical Aspects of Computer Science (STACS). 2021: 14:1 14:17.

R. Bernijazov, A. Dicks, R. Dumitrescu, M. Foullois, J.M. Hanselle, E. Hüllermeier, G. Karakaya, P. Ködding, V. Lohweg, M. Malatyali, F. Meyer auf der Heide, M. Panzner, C. Soltenborn: A Meta-Review on Artificial Intelligence in Product Creation. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021) – Workshop "AI and Product Design" (2021).

J. Castenow, T. Götte, T. Knollmann, F. Meyer auf der Heide: The Max-Line-Formation Problem and new Insights for Gathering and Chain-Formation. In: Proceedings of the 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 289 304, LNCS 13046, Springer, (2021)

J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide: Gathering a Euclidean Closed Chain of Robots in Linear Time. In: L. Gasieniec, R. Klasing, T. Radzik (Eds.), Proceedings of the 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), Springer, 2021, pp. 29 44.

B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide: Managing Multiple Mobile Resources, Theory of Computing Systems, 65(6): 943 984 (2021)

T. Knollmann, C. Scheideler: A self-stabilizing Hashed Patricia Trie. Information and Computation. 2021.

S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan: A continuous strategy for collision-less gathering, Theoretical Computer Science 852 (2021), pp. 41 60.

S. Li, F. Meyer auf der Heide, P. Podlipyan: The impact of the Gabriel subgraph of the visibility graph on the gathering of mobile autonomous robots, Theoretical Computer Science 852(2021), pp. 29 40.


Patents, prizes, awards

  • 2021 SIROCCO Prize for Innovation in Distributed Computing to Friedhelm Meyer auf der Heide
  • ALGOSENSORS 2021 Best Paper Award and the ALGOSENSORS 2021 Best Student Paper Award to Jannik Castenow, Jonas Harbig, Daniel Jung, Till Knollmann, Friedhelm Meyer auf der Heide for the paper "Gathering a Euclidean Closed Chain of Robots in Linear Time"

Additional Functions

Prof. Meyer auf der Heide

  • Member of the „Hochschulrat“ of the Paderborn University
  • Director of the Collaborative Research Center (SFB 901) „On-The-Fly Computing“
  • Member of the German Academy of Sciences „Leopoldina“, Vice Chair of the Section Information Sciences
  • Member of the NRW Academy of Sciences, Humanities and the Arts
  • Member of the National Academy of Science and Engineering „acatech“
  • DFG Special Advisor (Vertrauensdozent) of the Paderborn University
  • Member of Paderborn Institute for Data Science and Scientific Computing (DASCO)
  • Advisory board member of „Journal of Interconnection Networks (JOIN)“, World Scientific Publishing
  • Chairman of the Scientific Advisory Board of the Leibniz-Zentrum für Informatik, Schloss Dagstuhl
  • Member of the Program Committee of the 33th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA2021)
  • Member of the Program Committee of the 23rd International Symposium on Stabili-zation, Safety, and Security of Distributed Systems
  • Member of the Program Committee of the 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021)

Current research projects

DFG Collaborative Research Center 901 "On-The-Fly Computing"

The objective of CRC 901 – On-The-Fly Computing (OTF Computing) – is to develop techniques and processes for automatic on-the-fly configuration and provision of individual IT services out of base services that are available on world-wide markets. In addition to the configuration by special OTF service providers and the provision by what are called OTF Compute Centers, this involves developing methods for quality assurance and the protection of participating clients and providers, methods for the target-oriented further development of markets, and methods to support the interaction of the participants in dynamically changing markets. Friedhelm Meyer auf der Heide is coordinator of this collaborative research centre scince 2011. The CRC was reevaluated in February 2019. Based on this evaluation, the DFG has approved the third (and final) funding period from July 2019 to June 2023.

Funding: German Research Foundation
Term: 2011 – 2023

 

DFG Collaborative Research Centre 901 “On-The-Fly Computing”, subproject A1 “Capabilities and limitations of local strategies in dynamic networks”

This subproject started in 2011 with the objective to explore the capabilities and limits of local methods for control and optimization of big dynamic networks. Our focus lies on overlay networks, which allow the interaction between actors of the OTF market (the clients) and service providers to support services and provide infrastructure. “Local” in this context means that the control and optimization is not performed by a central instance but distributed by the actors, based on their local information. This subproject is coordinated by Friedhelm Meyer auf der Heide and Christian Scheideler.

Funding: German Research Foundation
Term: 2015 – 2023

 

DFG Collaborative Research Centre 901 “On- The-Fly Computing”, subproject C4 “On-The-Fly Compute Centers II: Execution of Composed Services in Configurable Compute Centers”

In this subproject we are concerned with efficiently utilizing resources within a highly configurable compute center. We emphasizes the collaboration between theoretical and practical computer science on closely related issues. OTF Compute Centers are particularly characterized by their ability to profi tably exploit the properties of OTF services. They are therefore heterogeneous, in that they have various types of calculation units and persistent storage units. They also have one or more networks that connect these resources with each other. OTF services can be provided by a single or several interacting geographically or organizationally distributed OTF Compute Centers and, if necessary, they are supplemented by temporarily rented resources from the cloud. We will therefore develop and analyze scheduling processes, that consider the characteristics of OTF services on the one hand, and OTF Compute Centers on the other. This subproject is coordinated by Holger Karl and Friedhelm Meyer auf der Heide.

Funding: German Research Foundation
Term: 2015 – 2023

 

DFG Project "Algorithms for swarm robotics: distributed computing meets dynamical systems"

The goal of this project is to investigate the capabilities and limitations of local, distributed strategies for swarms of mobile robots. Such strategies consist of protocols run by the individual robots. They are supposed to guide the movements of the robots in such a way that globally a prescribed formation like gathering, forming a line or other shapes is reached from an arbitrary initial configuration of the robots. This research direction is well-established in distributed computing. Our approach is to combine techniques from distributed computing and dynamical systems research in order to enhance the understanding of protocols for such formation tasks. To this end, we analyze the speed of the protocols in terms of runtime complexity in the distributed computing sense as well as stability properties of the prescribed formation with the use of ideas from dynamical systems. While in the distributed computing community often only a worst-case analysis is considered, the tools of dynamical systems allow a more fine-grained analysis of the input configurations by exploring the state space. More concretely, the state space foliation describes the long-term dynamical behavior of input configurations in more detail, i.e. it allows to identify classes of configurations that converge comparably fast or slow and even classes that fail to converge to the prescribed formation. Thus, the combination of both views leads to a more profound understanding of distributed strategies for swarms of mobile robots.

Joint project with Prof. Dr. Michael Dellnitz,
Institue of Mathematics, Paderborn University
Funding: German Research Foundation
Term: 2021 – 2024

 

Extension of sensor simulation for electronic control unit development with SensorSim by dynamically generated 3D scenes using the OSI standard (OSIgoes3D)

The aim of the project is to extend the sensor simulation for electronic control unit development with SensorSim by dynamically generated 3D objects/3D scenes using the Open Simulation Interface (OSI) in order to create the 3D world "on-the-fly" during the simulation time and without having to create and integrate it beforehand. In addition to the dynamic creation of the 3D world, the OSI standard is intended to increase the interoperability of dSPACE's tools. OSI is to be standardized by the ASAM (Association for Standardization of Automation and Measuring Systems). The goal of this project is to create the 3D world "on-the-fly" during the simulation time and not to have to model, tune, and "download" it beforehand.

Funding: dSPACE GmbH
Term: 2019 – 2021


Current industry cooperations

  • dSPACE GmbH, Paderborn, Kooperation im Rahmen der Erzeugung virtueller Welten
  • SICP – Software Innovation Campus Paderborn

Scientific cooperations

  • IT Kanpur, Prof. Surender Baswana PhD, Kanpur, India
  • University of Warwick, Prof. Dr. Artur Czumaj, Warwick, United Kingdom
  • University of Liverpool, Prof. Dr. Martin Gairing, Liverpool, United Kingdom
  • Loughborough University, Prof. Dr. Lars Nagel, Loughborough, United Kingdom
  • KAIST, Prof. Dr. Martin Ziegler, Daejeon, South Korea
  • Charles University, Prof. Dr. Jiri Sgall, Prague, Czech Republic
  • University of Dubai, Prof. Dr. Christine Markarian, Dubai, United Arab Emirates
  • Lebanese American University, Prof. Dr. Faisal N. Abu-Khzam, Beirut, Lebanon
  • École polytechnique fédérale de Lausanne(EPFL), Dr. Alexandra Lassota, Schweiz
  • École polytechnique fédérale de Lausanne(EPFL), Lars Rohwedder Ph.D., Schweiz
  • Hochschule Fulda, Hochschule für angewandte Wissenschaften, Prof. Dr. Tim Süß, Fulda
  • Universität Hamburg, Junior-Professor Dr. Peter Kling, Hamburg
  • Universität Hamburg, Dr. Malin Rau, Hamburg
  • Christian-Albrechts-Universität zu Kiel, Prof. Dr. Klaus Jansen, Kiel
  • University of Haifa, Prof. Leah Epstein, Ph.D., Haifa, Israel
  • Carleton University, Prof. Dr. Nicola Santoro, Ottawa, Canada
  • Israel Institute of Technology (Technion), Prof. Asaf Levin Ph.D., Haifa, Israel
  • University of Warsaw, Tomasz Michalak, Warsaw, Poland
  • University of Warsaw, Marcin Dziubiński, Warsaw, Poland