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.

Algorithmische Spieltheorie

Eine einzelne Partei, sei es eine Person, ein Unternehmen oder ein Staat, neigt dazu, ihre Interessen in der gegebenen Situation zu verfolgen, während die Welt aus mehreren interagierenden Parteien zusammengesetzt ist. Wir analysieren das Verhalten in solchen Interaktionen, wobei wir manchmal die Interaktionen anpassen, während wir davon ausgehen, dass jede Partei ihre Interessen optimal verfolgt. Wir modellieren und untersuchen das Netzwerkverhalten von Akteur*innen mithilfe von Analysen sozialer Netzwerke unter algorithmischen und spieltheoretischen Gesichtspunkten.



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


Patente, Preise, Auszeichnungen

  • 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"

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 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)

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 "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


Aktuelle Industriekoorporationen

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

Wissenschaftliche Koorporationen

  • 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