Forschung

Zukünftige IT-Systeme werden noch in weit stärkerem Maße als heute aus vielen unterschiedlichen Komponenten bestehen. Solche Systeme sind häufig zu groß und zu dynamisch, um zentral verwaltet werden zu können. Daher stehen bei uns algorithmische Probleme im Vordergrund, die sich mit dezentralen Methoden zur Kontrolle und Optimierung derartiger Systeme befassen.

Moderne verteilte IT-Systeme wie z. B. das Internet, Peer-to-Peer-Systeme oder drahtlose Kommunikationssysteme, aber auch Schwärme von Sensoren oder mobilen Robotern stellen neuartige Herausforderungen an die Algorithmenentwicklung. Da wegen der Größe und Dynamik solcher Systeme die einzelnen Komponenten (Peers, Roboter ...) nur sehr eingeschränkte lokale Information über den aktuellen Zustand des Gesamtsystems haben, müssen neue lokale algorithmische Methoden zur Nutzung und Kontrolle solcher Systeme entwickelt werden. Unsere Forschung befasst sich auf vielfältige Weise mit derartigen lokalen Algorithmen.

Ressourcenmanagement

Viele moderne Anwendungen werden in absehbarer Zeit so viele Daten generieren, dass eine Platzierung des entsprechenden Services nah am Nutzer unumgänglich wird. Um die Platzierungskosten dieser Services gering zu halten, beschäftigen wir uns mit der effizienten Anpassung der Platzierung einer festen Menge von Ressourcen, um die Anfragekosten zu minimieren. Ein Schwerpunkt ist aktuell die Untersuchung von Szenarien, in denen unterschiedliche Services angeboten und nachgefragt werden können. Insbesondere das Anbieten mehrerer Services an einer Stelle und die Nachfrage nach Kombinationen von Services macht die Frage herausfordernd, zu entscheiden, wo welche Kombinationen angeboten werden sollen.

Scheduling

In modernen heterogenen Rechenzentren gewinnt Scheduling, also das Verteilen von Aufgaben auf Ressourcen, mehr und mehr an Bedeutung. In unserer Fachgruppe entwickeln und analysieren wir Schedulingalgorithmen, die die Nutzung von Ressourcen in großen Rechenzentren effizient und zugleich mit beweisbar guter Qualität organisieren. Derzeit liegt dabei ein besonderer Fokus auf der Frage, wie eine Kombination aus einem ressourcenbeschränkten Server und einer Cloud effizient und kostengünstig genutzt werden kann.

Lokale Strategien für Roboterschwärme

Die Theorie der Schwarmrobotik untersucht, welche Aufgaben von einem großen Schwarm von Robotern ausgeführt werden können und welche Eigenschaften die Roboter dafür benötigen. Durch die hohe Anzahl von Robotern kann ein einzelner Roboter nicht den gesamten Schwarm überblicken, sondern nimmt nur einen kleinen Teil des Schwarms in seiner unmittelbaren Umgebung wahr. Wir beschäftigen uns mit Strategien für Roboterschwärme, deren Ziel es ist, den Schwarm in eine bestimmte Formation zu bringen. Dabei werden bereits geometrisch einfache Konfigurationen, wie z. B. ein Punkt oder ein Kreis, bedingt durch die lokalen Sichten der Roboter, zu einer großen Herausforderung. Unser Fokus liegt auf dem Entwurf und der Analyse der Korrektheit solcher Strategien und insbesondere auf der Laufzeitanalyse.

Algorithmische Grundlagen der Computergrafik

Um in einer virtuellen dreidimensionalen Welt zu navigieren und einen realistischen Eindruck zu erwecken, werden hohe Anforderungen an Datenstrukturen und Algorithmen gestellt, mit denen solche Welten verwaltet und als Bilder dargestellt werden. Wir konzentrieren uns auf die Entwicklung von Algorithmen, die eine approximative Darstellung der virtuellen Welt in Echtzeit berechnen können, abhängig von der Position und Blickrichtung des Betrachters. Ein derzeitiger Schwerpunkt ist die Entwicklung von sog. progressivem Sampling, das es erlaubt, das Clustern von zusammengehörigen geometrischen Primitiven effizient auf der Grafikkarte zu erledigen.

Umgang mit Dynamik: Dynamische Datenstrukturen für Graphenprobleme

Um Anfragen an Graphen - gebe z. B. einen kürzesten Weg von A nach B, den Durchmesser oder einen minimalen Schnitt im Graphen an - zu beantworten, sind geschickte Datenstrukturen notwendig, Besonders herausfordernd wird die Aufgabe, wenn sich der Graph über die Zeit verändert und die Datenstruktur daher ständig angepasst werden muss. Aktuell haben wir eine solche sog. dynamische Datenstruktur für die Berechnung minimaler Schnitte entwickelt.



Publikationen 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.


Promotionen

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.


Weitere Funktionen

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)

Aktuelle Forschungsprojekte

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


Aktuelle Industriekoorporationen

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

Wissenschaftliche Koorporationen

  • 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