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 und Scheduling

In modernen heterogenen Datenzentren gewinnt Ressourcenmanagement mehr und mehr an Bedeutung. Rechenzeit, Energie oder Datenrate sind nur einige Beispiele für eingeschränkte Ressourcen. In unserer Fachgruppe entwickeln wir Ansätze, um Scheduling-Algorithmen effizienter zu machen und dabei der steigenden Größe von Rechenzentren gerecht zu werden. Ein besonderer Fokus liegt dabei auf ressourcenbeschränktem Scheduling und der Platzierung von Ressourcen in Netzwerken.

Dynamische Datenströme

Datenströme entstehen in einer Vielzahl von Anwendungen, z. B. physikalischen Experimenten oder Sensornetzen. Die Herausforderung besteht darin, mit der enormen Datenmenge fertig zu werden, die von den Geräten erzeugt wird. Typischerweise sind die Datenströme zu groß und kommen zu schnell an, um vollständig über ein Netzwerk zu einem zentralen Server gesendet und in Echtzeit verarbeitet zu werden. Wir erforschen die Grundlagen für das Design und die Analyse von verteilten Algorithmen, die nützliche Informationen aus den Streams mit begrenzten Ressourcen wie Speicher, Kommunikationsvolumen und Rechenzeit extrahieren.

Computergrafik: Echtzeit-Navigation in komplexen 3D-Welten

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 Betrachtungsposition und -richtung des Betrachters. Wir testen unsere Ansätze in Anwendungen von Fahrerassistenzsystemen gemeinsam mit Partnern am Heinz Nixdorf Institut.

Ad-hoc-Netze in Umgebungen ohne Infrastruktur

Die Topologie dynamischer Netzwerke verändert sich über die Zeit, d. h., die Teilnehmer treten dem Netzwerk bei, sie scheiden aus dem Netzwerk aus oder sie verändern einfach nur ihre Position. Teilweise zerfallen solche Netzwerke in einzelne Komponenten, die nicht mehr zusammenhängend sind. Wir befassen uns in diesem Umfeld mit Strategien, die die Daten im Netzwerk durch sogenannte Postboten austauschen. Die Strategien werden in Ad-hoc-Netzwerken von Smartphones angewendet und untersucht.

Algorithmische Spieltheorie

Bei vielen aktuellen Problemen – beispielsweise bei großen dezentralen Netzwerken – steht nicht mehr die Frage der Lösung durch eine zentrale Autorität im Mittelpunkt, sondern die verteilte Lösung durch eine Vielzahl von Akteuren. Hierbei wählen Akteure ihre Strategien nach ihren eigennützigen Interessen, was zu Lösungen führen kann, die schlechter sind als die einer zentralen Autorität. Wir untersuchen hierbei einerseits, wie stark der Einfluss des strategischen Handelns der Akteure auf die Qualität der Lösungen ist. Andererseits interessiert uns die Berechnung von Vorhersagen, zu welchen Ergebnissen das strategische Verhalten führen kann.



Publikationen 2018

Althaus, Ernst; Brinkmann, André; Kling, Peter; Meyer auf der Heide, Friedhelm; Nagel, Lars; Riechers, Sören; Sgall, Jirí; Suess, Tim: Scheduling shared continuous resources on many-cores. Journal of Scheduling, 21(1): S. 77 – 92, 2018


Benter, Markus; Knollmann, Till; Meyer auf der Heide, Friedhelm; Setzer, Alexander; Sundermeier, Jannik: A Peer-to-Peer based Cloud Storage supporting orthogonal Range Queries of arbitrary Dimension. In: Proceedings of the 4th International Symposium on Algorithmic Aspects of Cloud Computing (ALGOCLOUD) (accepted), 20. – 21. Aug. 2018


Drees, Maximilian; Feldotto, Matthias; Riechers, Sören; Skopalik, Alexander: Pure Nash equilibria in restricted budget games. Journal of Combinatorial Optimization 2018


Feldkord, Björn; Feldotto, Matthias; Gupta, Anupam; Guruganesh, Guru; Kumar, Amit; Riechers, Sören; Wajc, David: Fully Dynamic Bin Packing with Little Repacking. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), S. 51:1 – 51:24, 9. – 13. Jul. 2018, Schloss Dagstuhl - Leibniz-Zentrum für Informatik


Feldkord, Björn; Malatyali, Manuel; Meyer auf der Heide, Friedhelm: A Dynamic Distributed Data Structure for Top-k and k-Select Queries. In: Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovic on the Occasion of His 60th Birthday, S. 311 – 329, 2018


Feldkord, Björn; Meyer auf der Heide, Friedhelm: Online Facility Location with Mobile Facilities. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 373 – 381, 16. – 18. Jul. 2018, ACM


Feldotto, Matthias; Haake, Claus-Jochen; Skopalik, Alexander; Stroh-Maraun, Nadja: Disaggregating User Evaluations Using the Shapley Value. In: Proceedings of the 13th Workshop on the Economics of Networks, Systems and Computation (NetEcon 2018) (accepted), S. 5:1 – 5:6, Jun. 2018

Feldotto, Matthias; Leder, Lennart; Skopalik, Alexander: Congestion Games with Mixed Objectives. Journal of Combinatorial Optimization, 36(4): S. 1145 – 1167 2018


Hamann, Heiko; Markarian, Christine; Meyer auf der Heide, Friedhelm; Wahby, Mostafa: Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets. In: Fun With Algorithms (FUN), S. 22:1 – 22:13, 13. – 15. Jun. 2018


Jung, Daniel; Kolb, Christina; Scheideler, Christian; Sundermeier, Jannik: Brief Announcement: Competitive Routing in Hybrid Communication Networks. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 231 – 233, 16. – 18. Jul. 2018, ACM


Jung, Daniel; Kolb, Christina; Scheideler, Christian; Sundermeier, Jannik: Competitive Routing in Hybrid Communication Networks. In: Proceedings of the 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS) (accepted), 23. – 24. Aug. 2018


Knollmann, Till; Scheideler, Christian: A Self-Stabilizing Hashed Patricia Trie. In: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer Lecture Notes in Computer Science LNCS, Band 11201 , 4. – 7. Nov. 2018, Springer


König, Jürgen; Mäcker, Alexander; Meyer auf der Heide, Friedhelm; Riechers, Sören: Scheduling with interjob communication on parallel processors. Journal of Combinatorial Optimization, 36(4): S. 1356 – 1379, 2018


Li, Shouwei; Markarian, Christine; Meyer auf der Heide, Friedhelm: Towards Flexible Demands in Online Leasing Problems. Algorithmica, 80(5): S. 1556 – 1574, 2018


Mäcker, Alexander; Malatyali, Manuel; Meyer auf der Heide, Friedhelm; Riechers, Sören: Cost-Efficient Scheduling on Machines from the Cloud. Journal of Combinatorial Optimization, 36(4): S. 1168 – 1194, 2018


Markarian, Christine: An Optimal Algorithm for Online Prize-collecting Node-weighted Steiner Forest. In: International Workshop on Combinatorial Algorithms (IWOCA), 16. – 19. Jul. 2018


Markarian, Christine; Abu-Khzam, Faisal N. ; Meyer auf der Heide, Friedhelm; Schubert, Michael: Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Adhoc Networks. In: Theory of Computing Systems (TOCS), Nr. 8, S. 1673 – 1684, 2018


Meyer auf der Heide, Friedhelm; Schaefer, Johannes: Brief Announcement: Communication in Systems of Home Based Mobile Agents. In: Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), S. 359 – 361, 16. – 18. Jul. 2018, ACM


Promotionen

Daniel Jung

Local Strategies for Swarm Formations on a Grid

My dissertation deals with the Gathering problem for swarms of n point-shaped robots on a grid, in which all robots of the swarm are supposed to gather at a previously undefined point. Special attention is paid to the strong limitation of robot capabilities. These include in particular the lack of global control, a global compass, global visibility and (global) communication skills. Furthermore, all robots are identical. The robots are given only local abilities. This includes a constant range of vision. The robots all work completely synchronously. In this work we present and analyze three different Gathering strategies in different robot models. We formally prove correctness and total running time: Chapter 4 focuses on minimizing the available robot capabilities. The underlying strategy completes the gathering in O(n²) time. For the following Chapters 5 and 6, the aim is to optimize the total running time under using only local robot capabilities: We additionally allow a constant-sized memory and a constant number of locally visible statuses (lights, flags). For the strategies of both chapters we show an asymptotically optimal running time of O(n). Unlike in Chapters 4 and 5, we additionally restrict connectivity and vision to an initially given chain connectivity in Chapter 6, where two chain neighbors must have a distance of 1 from each other. A robot can only see and interact with a constant number of its direct chain neighbors.

 

Matthias Feldotto

Approximate Pure Nash Equilibria in Congestion, Opinion Formation and Facility Location Games

This thesis investigates approximate pure Nash equilibria in different game-theoretic models. In such an outcome, no player can improve her objective by more than a given factor through a deviation to another strategy. In the first part, we investigate two variants of Congestion Games in which the existence of pure Nash equilibria is guaranteed through a potential function argument. However, the computation of such equilibria might be hard. We construct and analyze approximation algorithms that enable the computation of states with low approximation factors in polynomial time. To show their guarantees we use sub games among players, bound the potential function values of arbitrary states and exploit a connection between Shapley and proportional cost shares. Furthermore, we apply and analyze sampling techniques for the computation of approximate Shapley values in different settings. In the second part, we concentrate on the existence of approximate pure Nash equilibria in games in which no pure Nash equilibria exist in general. In the model of Coevolving Opinion Formation Games, we bound the approximation guarantees for natural states nearly independent of the specific definition of the players' neighborhoods by applying a concept of virtual costs. For the special case of only one influential neighbor, we even show lower approximation factors for a natural strategy. Then, we investigate a two-sided Facility Location Game among facilities and clients on a line with an objective function consisting of distance and load. We show tight bounds on the approximation factor for settings with three facilities and infinitely many clients. For the general scenario with an arbitrary number of facilities, we bound the approximation factor for two promising candidates, namely facilities that are uniformly distributed and which are paired.


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 ACM-STOC TheoryFest Invited Papers Committee (2018)
  • Member of the Program Committee of the 16th Workshop on Approximation and Online Algorithms (WAOA 2018)
  • Member of the Program Committee of the 13th Workshop on Parallel Systems and Algorithms (PASA 2018)
  • Member of the Program Committee of the Doktorandenprogramm der INFORMATIK 2017
  • Co-Organizer and Reviewer for the Bundeswettbewerb Informatik 2018

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.

Funding: German Research Foundation
Term: 2011 – 2019

 

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

 

DFG Collaborative Research Centre 901 “On-The-Fly Computing”, subproject A3 “The market for services: Incentives, algorithms, implementation"

In subproject A3 we model and analyze the market for composed IT-services. The main challenges in the economic considerations are the composition aspect, automatization of transactions, and the dynamics of composed services. For the analysis we use and develop methods from the fi elds of non-cooperative, cooperative, and algorithmic game theory. Furthermore, the study of bounded rational behavior rests on methods from evolutionary game theory, behavioral economics and the theory of learning. This subproject is coordinated by Claus-Jochen Haake, Burkhard Hehenkamp, and Alexander Skopalik.

Funding: German Research Foundation
Term: 2015 – 2019

 

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

 

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

BMBF-Project: Resilience by Spontaneous Volunteers Networks for Coping with Emergencies and Disaster (RESIBES)

In RESIBES, we set up network of spontaneous volunteers, which can be quickly activated and deployed in a coordinated manner in a crisis. Individuals can register as so-called active or passive spontaneous volunteers in the network. Active spontaneous volunteers offer their workforce, while passive spontaneous volunteers provide material resources. In our project part, we are building a robust communication network, which in the case of application supports the coordination of the deployed spontaneous volunteers and the comprehensive assessment. Communication is also possible if the communication infrastructure is damaged or overloaded. To this end, we develop an ad-hoc network using the smartphones of the spontaneous volunteers. In Paderborn, Friedhelm Meyer auf der Heide, Matthias Fischer and Bernd Kleinjohann coordinate this project.

Funding: Federal Ministry of Education and Research
Term: 2016 – 2019


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
  • Carnegie Mellon University, Prof. Dr. Anupam Gupta, Pittsburgh, USA
  • Carnegie Mellon University, Dr. David Wajc, Pittsburgh, USA
  • Carnegie Mellon University, Dr. Guru Guruganesh, Pittsburgh, USA
  • IIT Delhi, Prof. Dr. Amit Kumar, New Delhi, India
  • Karls Universität Prag, Prof. Dr. Jiri Sgall, Prag, Tschechien
  • Haigazian University, Prof. Dr. Christine Markarian, Beirut, Lebanon
  • Lebanese American University, Prof. Dr. Faisal N. Abu-Khzam, Beirut, Lebanon
  • Albert-Ludwigs-Universität Freiburg, Prof. Dr. Stefan Kaufmann, Freiburg, Germany
  • Johannes Gutenberg-Universität Mainz, Prof. Dr. Ernst Althaus, Mainz, Germany
  • Johannes Gutenberg-Universität Mainz, Prof. Dr. Andre Brinkmann, Mainz, Germany
  • Ostfalia Hochschule für angewandte Wissenschaften, Prof. Dr. Tim Süß, Suderburg, Germany
  • University of Augsburg, Prof. Dr. Tobias Harks, Augsburg, Germany
  • Universität Hamburg, Junior-Professor Dr. Peter Kling, Hamburg, Germany