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.

Handling dynamics: dynamic data structures for graph problems

In order to answer graph queries – e.g. the shortest path from A to B, the diameter or a minimal cut in the graph - clever data structures are necessary. The task becomes especially challenging when the graph changes over time and the data structure must, therefore, be constantly adapted. We have developed such a so-called dynamic data structure for the calculation of minimal cuts.



Publicatons 2020

H. Karl, D. Kundisch, F. Meyer auf der Heide, H. Wehrheim: A Case for a New IT Ecosystem: On-The-Fly Computing. Business &; Information Systems Engineering 62 (2020) 467 – 481.

J. Castenow, B. Feldkord, T. Knollmann, M. Malatyali, F. Meyer auf der Heide: The Online Multi-Commodity Facility Location Problem. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020.

J. Castenow, C. Kolb, C. Scheideler: A Bounding Box Overlay for Competitive Routing in Hybrid Communication Networks. In: Proceedings of the 21st International Conference on Distributed Computing and Networking (ICDCN), ACM.

J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide: Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented & Luminous Robots with Limited Visibility. In: Stabilization, Safety, and Security of Distributed Systems – 21st International Symposium, SSS 2020, Austin, Texas, USA, November 18 – 21, 2020, Proceedings (Accepted), 2020.

J. Castenow, M. Fischer, J. Harbig, D. Jung, F. Meyer auf der Heide: Gathering Anonymous, Oblivious Robots on a Grid. Theoretical Computer Science 815 (2020) 289 – 309.

J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide: A Discrete and Continuous Study of the Max-Chain-Formation Problem. In: Stabilization, Safety, and Security of Distributed Systems - 21st International Symposium, SSS 2020, Austin, Texas, USA, November 18 – 21, 2020, Proceedings (Accepted), 2020.

J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide: Brief Announcement: A Discrete and Continuous Study of the Max-Chain-Formation Problem: Slow Down to Speed up. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020.

M. Braun, J. Castenow, F. Meyer auf der Heide: Local Gathering of Mobile Robots in Three Dimensions. In: Proceedings of the 27th Conference on Structural Information and Communication Complexity (SIROCCO), Springer, 2020.

S. Baswana, S. Gupta, T. Knollmann: Mincut Sensitivity Data Structures for the Insertion of an Edge. In: F. Grandoni, G. Herman, P. Sanders (Eds.), 28th Annual European Symposium on Algorithms (ESA 2020), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2020, pp. 12:1 – 12:14.

S. Pukrop, A. Mäcker, F. Meyer auf der Heide: Approximating Weighted Completion Time for Order Scheduling with Setup Times. In: Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2020.


PhD Theses

Björn Feldkord

Mobile resource allocation

This thesis covers the topic of resource allocationproblems that are tailored to scenariosprimarily involving mobile users. The resourcesare placed close to the users, e.g., at the basestations of a mobile network. The performanceof applications accessed by the users depends,among other things, on latencies which have tobe guaranteed by a suitable placement of theresources. This implies that the configurationof resources must be continuously adapted.However, these changes must be easily computableand quickly applicable to maintain a highservice quality. We propose two basic models,which deal with the placement of mobile resources:Our first model is called the MobileServer problem, where we are concerned withthe placement of a fixed number of resources.These resources can be moved over a short distancebefore answering an incoming request.For this problem, we propose online algorithmsbased on the methods used in similar problemssuch as the k-Server and Page Migrationproblems, and prove asymptotically almostoptimal competitive ratios. The second problemis an extension of the Online Facility Locationproblem, where we allow an online algorithm tocorrect its positions of the facilities over time.The movement distance is limited implicitlythrough a cost proportional to the distance aswell as directly through a fixed upper boundper time step. We propose online algorithmsthat achieve competitive ratios independent oftime and the number of clients. The results areasymptotically optimal on the line.


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 33rd IEEE International Parallel & Distributed Processing Symposium (IPDPS 2019)

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: Distributed Data Streams in Dynamic Environments (DISDAS) in the DFG-Priority Programme 1736 Algorithms for Big Data

In this project we lay the foundations for the design and analysis of distributed algorithms that continuously compute aggregated information of streams of data which are observed by a multitude of devices. These devices may be mobile, i.e. capable of moving in the plane or in space, and contain both (wireless) communication devices and sensors for observing their environment. The major challenge is to cope with the huge amount of data generated by the devices. Typically, the data streams are too big and arrive too fast to be completely stored, or sent to a central server through a network, or processed in real time. Thus we have to fi nd ways to extract useful information from the streams using restricted resources like memory, communication volume and computation time. In this project, we are developing continuous algorithms in distributed environments, taking both the dynamics of the devices and of the observed events into account. This reflects the scenario of moving people with smartphones who observe their environment. Friedhelm Meyer auf der Heide coordinates this project.

Funding: German Research Foundation
Term: 2014 – 2020

 

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 – 2020


Current industry cooperations

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

Scientific cooperations

  • 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
  • Haigazian University, Prof. Dr. Christine Markarian, Beirut, Lebanon
  • Lebanese American University, Prof. Dr. Faisal N. Abu-Khzam, Beirut, Lebanon
  • Johannes Gutenberg-Universität Mainz, Prof. Dr. Ernst Althaus, Mainz
  • Johannes Gutenberg-Universität Mainz, Prof. Dr. Andre Brinkmann, Mainz
  • Hochschule Fulda, Hochschule für angewandte Wissenschaften, Prof. Dr. Tim Süß, Fulda
  • Universität Hamburg, Junior-Professor Dr. Peter Kling, Hamburg
  • Christian-Albrechts-Universität zu Kiel, Prof. Dr. Klaus Jansen, Kiel
  • Hasso Plattner Institut Potsdam, Dr. Pascal Lenzner, Potsdam
  • Carleton University, Prof. Dr. Nicola Santoro, Ottawa, Canada
  • Albert-Ludwigs-Universität Freiburg, Prof. Dr. Stefan Kaufmann, Freiburg