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.

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.

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.

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.

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.

Baswana, S., Gupta, S., Knollmann, T.: Mincut Sensitivity Data Structures for the Insertion of an Edge. Algorithmica, 2022

Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., Meyer auf der Heide, F.: The k-Server with Preferences Problem. Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 345 – 356, 2022

Castenow, J., Harbig, J., Jung, D., Kling, P., Knollmann, T., Meyer auf der Heide, F.: A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots with Limited Visibility. 26th International Conference on Principles of Distributed Systems (OPODIS) (Accepted), 2022

Castenow, J., Harbig, J., Jung, D., Knollmann, T., Meyer auf der Heide, F.: Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms for Chain-Formation. Theoretical Computer Science, 2022

Castenow, J., Kling, P., Knollmann, T., Meyer auf der Heide, F.: A Discrete and Continuous Study of the Max-Chain-Formation Problem. Information and Computation, Article 104877, 2022

Epstein, L., Lassota, A., Levin, A., Maack, M., Rohwedder, L.: Cardinality Constrained Scheduling in Online Models. In P. Berenbrink, B. Monmege (Eds.), 39th International Symposium
on Theoretical Aspects of Computer Science, (STACS), 2022, Vol. 219, p. 28:1 – 28:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Maack, M., Meyer auf der Heide, F., Pukrop, S.: Server Cloud Scheduling. In Approximation and Online Algorithms. Springer International Publishing, 2022

Maack, M., Pukrop, S., Rasmussen, A. R.: (In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling. In S. Chechik, G. Navarro, E. Rotenberg, G. Herman (Eds.), 30th Annual European Symposium on Algorithms, (ESA), 2022, Vol. 244, p. 77:1 – 77:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

Polevoy, G., Dziubinski, M.: Fair, Individually Rational and Cheap Adjustment. In L. De Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2022

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}

DAAD Projekt "DigiChemLab"

The goal of the project is the development of a virtual learning platform for the chemical-technical education using virtual reality technology. The learning platform represents a supplementary offer for the preparation of the work in chemical laboratories (e.g. internships). The objective is to develop a digital chemistry laboratory for the digitalization of chemistry courses (virtual training platform) in order to increase the safety awareness. Joint project with Prof. Dr. Wolfgang Bremser, Department of Chemistry, Chemistry Materials Science, Paderborn University and Prof. Dr. Sabine Fechner, Department of Chemistry, Chemistry Education, Paderborn University. External cooperation partners are the departments Materials Science of the Chinese Qingdao University of Science and Technology (QUST),

_{Funding: DAAD (German Academic Exchange Service)
Term: 2021 – 2022}

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

• 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, Prof. Dr. Petra Berenbrink, 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
• Qingdao University of Science and Technology(QUST), Prof. Dr. Wende Tian, Qingdao, China
• Shandong University (SDU), Prof. Dr. B. Chen, Jinan, China