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 Rechnersysteme liefern in vielerlei Hinsicht erweiterte Anwendungsmöglichkeiten:

  • Das Internet bietet die Möglichkeit zum weltweiten Informationsaustausch und hat sogar das Potential, als gigantischer Parallelrechner genutzt zu werden.
  • Peer-to-Peer Netzwerke ermöglichen die Unterstützung von verteilten Anwendungen durch Adaption der Netzwerktopologie.
  • Drahtlose Kommunikationssysteme erlauben sehr flexible Kommunikation auch zwischen mobilen Stationen.
  • Schwärme von Sensoren oder mobilen Robotern erschließen neue Anwendungsszenarien.
  • Hardware-Unterstützung für Grafikanwendungen ermöglicht Echtzeit-Navigation in sehr komplexen virtuellen Szenen.

Eine besondere Herausforderung stellen dabei Systeme dar, die aus unterschiedlichen Komponenten bestehen und deren Struktur sich mit der Zeit verändert. Dabei sehen wir eine gemeinsame Herausforderung: Komponenten (Peers, Roboter, ...) haben nur sehr eingeschränkte lokale Sicht auf den aktuellen Zustand des Gesamtsystems, ein global guter Zustand muss durch lokale Regeln erzeugt und aufrechterhalten werden.


Zurzeit stehen folgende Themenbereiche im Mittelpunkt unserer Forschungsinteressen:

Lokale Strategien in dynamischen Netzwerken

Dynamische Netzwerke, d. h. Netzwerke, deren Topologie sich über die Zeit verändert, spielen in vielen Bereichen eine wichtige Rolle. Sie tauchen z. B. als sogenannte Overlay Netze zur Unterstützung von Peer-to-Peer Systemen auf, deren Topologie ständig an die Anforderungen der Nutzer angepasst werden muss. Auch Bewegungsmuster von Roboterschwärmen bilden dynamische Netzwerke.

Weitere Beispiele sind Datenstrukturen für bewegliche Objekte in der Computergrafik oder drahtlose, mobile Kommunikationsnetzwerke. Wegen der Größe und Dynamik derartiger Netzwerke ist es häufig nicht möglich, sie durch eine zentrale Kontrolle zu steuern oder zu optimieren. Vielmehr müssen die Knoten des Netzwerkes selbst über ihrer Aktionen entscheiden, wobei sie nur über sehr eingeschränkte, lokale Information über das gesamte Netzwerk verfügen. Auf der anderen Seite sollen derartige lokale Strategien, ausgeführt in den Knoten des Netzwerks, zu global gutem Verhalten führen. Die Entwicklung derartiger lokaler Strategien in verschiedensten Anwendungsszenarien ist ein wesentliches Forschungsthema unserer Fachgruppe.


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.

Computergrafik: Echtzeitnavigation in komplexen virtuellen Szenen

Um in einem virtuellen dreidimensionalen Raum navigieren und einen realistischen Eindruck erzeugen zu können, werden u. a. hohe Ansprüche an Datenstrukturen gestellt, mit denen solche Szenen verwaltet, und mit denen Bilder gerendert werden. Ein Schwerpunkt liegt bei uns auf der Entwicklung von Methoden, die abhängig von der Blickposition und -richtung des Betrachters in Echtzeit Entscheidungen über das für die Blickposition effizienteste der anwendbaren Rendering-Verfahren zu treffen. Wir erproben unsere Ansätze in Anwendungen zur Produktionsplanung und -steuerung gemeinsam mit Partnern im Heinz Nixdorf Institut.



Unsere Aktivitäten 2013

Publikationen

Abshoff, S.; Benter, M.; Malatyali, M.; Meyer auf der Heide, F.: On Two-Party Communication Through Dynamic Networks. In: Principles of Distributed Systems, 17th International Conference, OPODIS 2013, LNCS, 16 – 18 Dec 2013, Springer-Verlag

Abshoff, S.; Benter, M.; Cord-Landwehr, A.; Malatyali, M.; Meyer auf der Heide, F.: Token Dissemination in Geometric Dynamic Networks. In: Algorithms for Sensor Systems – 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, LNCS, 5 – 6 Sep 2013, Springer-Verlag

Benter, M.; Neumann, F.; Frey, H.: Reactive Planar Spanner Construction in Wireless Ad Hoc and Sensor Networks. In: Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM), Apr 2013

Benter, M.; Divband, M.; Kniesburges, S.; Koutsopoulos, A.; Graffi, K.: Ca-Re-Chord: A Churn Resistant Self-stabilizing Chord Overlay Network. In: Proceedings of the Conference on Networked Systems (NetSys), Mar 2013

Brandes, P.; Kempkes, B.; Meyer auf der Heide, F.: Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally. Theoretical Computer Science, to appear 2013

Eikel, B.; Jähn, C.; Fischer, M.; Meyer auf der Heide, F.: Spherical Visibility Sampling. Computer Graphics Forum, 32(4): pp. 49 – 58, July 2013

Gausemeier, J.; Grafe, M.; Meyer auf derHeide, F. (editor.) 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung.
HNI-Verlagsschriftenreihe, Paderborn, volume 311 , 18 – 19 Apr 2013, Heinz Nixdorf Institut

Happe, M.; Kling, P.; Meyer auf der Heide, F.; Platzner, M.; Plessl, C.: On-The-Fly Computing: A Novel Paradigm for Individualized IT Services. In: Proceedings of the 9th Workshop on Software Technology for Future embedded and Ubiquitous Systems (SEUS), June 2013, IEEE

Harks, T.; Hoefer, M.; Klimm, M.; Skopalik, A.: Computing pure Nash and strong equilibria in bottleneck congestion games. Mathematical Programming, 141(1 – 2): pp. 193 – 215, Oct 2013

Hoefer, M.; Skopalik, A.: On the Complexity of Pareto-Optimal Nash and Strong Equilibria. Theory Comput. Syst., 53(3): pp. 441 – 453, Oct 2013

Jähn, C.; Eikel, B.; Fischer, M.; Petring, R.; Meyer auf der Heide, F.: Evaluation of Rendering Algorithms using Position-Dependent Scene Properties. In: Advances in Visual Computing, LNCS, volume 8033 , pp. 108 – 118. Springer Berlin Heidelberg, 2013

Keller, M.; Pawlik, S.; Pietrzyk, P.; Karl, H.: A Local Heuristic for Round-Trip-Time-Optimized Distributed Cloud Deployment. In: Workshop on Distributed Cloud Computing, 9 – 12 Dec 2013

Kling, P.; Pietrzyk, P.: Profitable Scheduling on Multiple Speed-Scalable Processors. In: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), July 2013, ACM

Markarian, C.; Schubert, M.; Meyer auf der Heide, F.: Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks. In: Algorithms for Sensor Systems – 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, LNCS, 5 – 6 Sep 2013, Springer-Verlag

Meyer auf der Heide, F.: Algorithmische Grundlagen für die Selbstorganisation von Roboterschwärmen. In: 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, HNI-Verlagsschriftenreihe, Paderborn, pp. 7– 16, 18 – 19 Apr 2013, Heinz Nixdorf Institut

Petring, R.; Eikel, B.; Jähn, C.; Fischer, M.; Meyer auf der Heide, F.: Darstellung heterogener 3-D-Szenen in Echtzeit. In: 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung, HNI-Verlagsschriftenreihe, Paderborn, volume 311 , pp. 49 – 60, 18 – 19 Apr 2013, Heinz Nixdorf Institut

Petring, R.; Eikel, B.; Jähn, C.; Fischer, M.; Meyer auf der Heide, F.: Real-Time 3D Rendering of Heterogeneous Scenes. In: Advances in Visual Computing, LNCS, volume 8033 , pp. 448 – 458. Springer Berlin Heidelberg, 2013

Promotionen

Benjamin Eikel
Spherical Visibility Sampling – Preprocessed Visibility for Occlusion Culling in Complex 3D Scenes

Many 3D scenes (e.g. generated from CAD data) are composed of a multitude of objects that are nested in each other. An industrial plant, for instance, may contain multiple machines and the machines may have an electric motor with many smaller parts like rotor and stator located inside. Since the objects occlude each other, only few are visible from outside.

This work presents a new technique, Spherical Visibility Sampling (SVS), for real-time 3D rendering of such – often highly complex – scenes. SVS exploits the occlusion and annotates hierarchically structured objects with direction dependent visibility information in a preprocessing step. or different directions, the direction-dependent visibility encodes which objects of a scene‘s region are visible from that direction from the outside of the regions‘ enclosing bounding sphere. Since there is no need to store a separate view space subdivision as in most techniques based on preprocessed visibility, a small memory footprint is achieved. Using the direction-dependent visibility information for an interactive walkthrough, the potentially visible objects can be retrieved very efficiently without the need for further visibility tests.

The evaluation shows that using SVS allows to preprocess complex 3D scenes fast and to visualize them in real time (e.g. a Power Plant model and five animated Boeing 777 models with billions of triangles). The comparison with two state of-the-art occlusion culling algorithms demonstrates the advantages and disadvantages of SVS. Because SVS does not require hardware support for occlusion culling during rendering, it is even applicable for rendering complex scenes on mobile devices.

Peter Pietrzyk
Local and Online Algorithms for Facility Location
The topic of this thesis is approximation and online algorithms for an optimization problem known as „Facility Location“. This problem, or one of its many variants, arises as a sub problem in many practical applications, and is thus of significant importance in the field of Operations Research. Furthermore, it is also one of the most studied optimization problems in theoretical computer science with hundreds of research papers published during the last decades.

Most of these papers introduce approximation algorithms for different variants of the problem making Facility Location a benchmark problem for various new kinds of approximation techniques.

In this thesis, we focus on the theoretical aspects of Facility Location by designing and, most importantly, analyzing approximation and online algorithms. Our algorithms deal with three distinct scenarios in which Facility Location occurs: (i) networks that are exposed to perpetual changes, (ii) wireless sensor networks with strong locality constraints, and (iii) distributed settings where the focus lies, first and foremost, on the quality of the computed approximation. We deal with each of these three scenarios within its own dedicated chapter.

Chapter 2 covers Scenario (i). It presents an online algorithm designed for a highly dynamic network where additional nodes are perpetually added. The difficulty here is that these new nodes‘ requests have to be handled efficiently without any knowledge of the network‘s future development.

Scenario (ii) is considered in Chapter 3. Two distributed algorithms for wireless sensor networks are presented here. Due to the nodes‘ limited communication range, locality is of high importance in this scenario. Additional aspects like inaccurate measurement data, power consumption, and dynamics are also taken into account.

Finally, Scenario (iii) is considered in Chapter 4. Our objective here is to distributedly compute a solution with an approximation ratio that is as close as possible to the best achievable ratio. In order to accomplish this, we allow, compared to Scenario (ii), a higher running time, but still require that the algorithm terminates in sub-linear time.

The thesis ends with Chapter 5 where possible directions of future work are presented.


Weitere Funktionen

Prof. Meyer auf der Heide

  • Member of the „Hochschulrat“ of the University of Paderborn
  • Director of the Collaborative Research Center (SFB 901) „On-The-Fly Computing“
  • ƒƒMember of the German Academy of Sciences „Leopoldina“
  • ƒƒMember of the NRW Academy of Sciences, Humanities and the Arts
  • ƒƒDFG Special Advisor (Vertrauensdozent) of the University of Paderborn
  • ƒƒDirector of the NRW-Graduate School of Dynamic Intelligent Systems (one of three directors)
  • ƒƒAssistant Chairman of the Paderborn Institute for Scientific Computation (PaSCo)
  • ƒƒManaging Editor of „Journal of Interconnection Networks (JOIN)“, World Scientific Publishing
  • ƒƒMember of the Scientific Advisory Board of the Leibniz-Zentrum für Informatik, Schloss Dagstuhl
  • ƒƒMember of the Evaluation Committee of the Bundeswettbewerb „Jugend Forscht“,
  • Coordinator of the section on Computer Science and Mathematics
  • ƒƒMember of the Award Committee of the European Association for Theoretical Computer Science (EATCS)
  • ƒƒMember of the Milner Award Committee
  • ƒƒProgram Chair for Track C „Experimental Algorithms“ of the 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotic (ALGOSENSORS 2013)
  • ƒƒCo-Program Chair of the 11. Paderborner Workshop Augmented & Virtual Reality in der Produktentstehung (ARVR 2013)
  • ƒƒMember of the program committee of the Algorithms and Data Structures Symposium (WADS 2013)
  • ƒƒMember of the program committee of the workshop „Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2013
  • ƒƒMember of the program committee of the 20st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013)
  • ƒƒMember of the program committee of the 21th Conference on Algorithms and Complexity (CIAC 2013)

Jun.-Prof. Skopalik

  • Member of the program committee of the 6th International Symposium on Algorithmic Game Theory (SAGT)

Graduiertenprogramme

  • ƒƒInternational Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • GSANS – the Paderborn Graduate School on Applied Network Science
  • ƒƒDFG Research Training Centre „Research Training Group Automatisms – Emerging structures in information technology, media, and culture“

Aktuelle Forschungsprojekte

DFG Collaborative Research Center 901

„On-The-Fly Computing“ with the Subprojects A1 „Capabilities and limitations of local strategies in dynamic networks“ (jointly with Prof. Dr. Christian Scheideler), C2 „On-The-Fly Compute Centers“ (jointly with Jun.-Prof. Dr.- Christian Plessl, Prof. Dr. Marco Platzner), and Z (Central Duties of the CRC)

MULTIPLEX

EU-IP Foundational Research on MULTIlevel comPLEX networks and systems (MULTIPLEX)

it‘s OWL

Cross-sectional project Human-Machine-Interaction(BMBF), Querschnittsprojekt Mensch-Maschine-Interaktion


Unsere Aktivitäten 2012

Publikationen:

Cord-Landwehr, Andreas; Kling, Peter; Mallmann-Trenn, Frederik: Slow Down & Sleep for Profit in Online Deadline Scheduling. In: Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), Dec 2012, Springer-Verlag

Cord-Landwehr, Andreas; Hüllmann, Martina; Kling, Peter; Setzer, Alexander: Basic Network Creation Games with Communication Interests. In: Algorithmic Game Theory, SAGT 2012, Lecture Notes in Computer Science, number 7615 , pp. 72-83, 22 - 23 Oct 2012, Springer-Verlag

Fanelli, Angelo; Moscardelli, Luca ; Skopalik, Alexander: On the Impact of Fair Best Response Dynamics. In: Mathematical Foundations of Computer Science 2012, Sep 2012, Springer-Verlag

Süß, Tim; Koch, Clemens; Jähn, Claudius; Fischer, Matthias; Meyer auf der Heide, Friedhelm: Asynchronous Occlusion Culling on Heterogeneous PC Clusters for Distributed 3D Scenes. In: Proceedings of International Symposium on Visual Computing (ISVC), Lecture Notes in Computer Science, volume 7431 , pp. 502-512, 16 - 18 July 2012, Springer-Verlag

Kling, Peter; Meyer auf der Heide, Friedhelm; Pietrzyk, Peter: An Algorithm for Online Facility Leasing. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, volume 7355 , pp. 61--72, 30 June - 2 July 2012, Springer-Verlag

Damerow, Valentina; Manthey, Bodo; Meyer auf der Heide, Friedhelm; Räcke, Harald; Scheideler, Christian; Sohler, Christian; Tantau, Till: Smoothed Analysis of Left-To-Right Maxima with Applications. ACM Transactions on Algorithms, 8(3)(30), July 2012

Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm: Optimal and Competitive Runtime Bounds for Continuous, Local Gathering of Mobile Robots. In: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), ACM International Conference Proceeding Series, pp. 18--26, 25 - 27 June 2012

Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Continuous Local Strategies for Robotic Formation Problems. In: Proceedings of the 11th International Symposium on Experimental Algorithms - SEA, Lecture Notes in Computer Science, volume 7276 , pp. 9-17, June 2012, Springer-Verlag

Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander: Computing approximate pure Nash equilibria in congestion games. SIGecom Exchanges, 11(1): pp. 26-29 2012

Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander: Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. In: ACM Conference on Electronic Commerce, 1 Jan 2012, ACM

Drees, Maximilian; Hüllmann, Martina; Koutsopoulos, Andreas ; Scheideler, Christian: Self-Organizing Particle Systems. In: Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012

Brandes, Philipp; Meyer auf der Heide, Friedhelm: Distributed Computing in Fault-Prone Dynamic Networks. In: 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS 2012, to appear), 2012

 

Promotionen

Barbara Kempkes:

Local strategies for robot formation problems

We consider a team of autonomous mobile robots in the Euclidean plane. There is no central control and the robots have to coordinate themselves. The key challenge is that each robot can only see its immediate neighbors and can also communicate only with robots in this neighborhood. This results in many algorithmic problems. This dissertation examines the conditions under which the robots can gather in one point respectively form a line between two fixed stations. For both problems, several robot strategies are presented in various models. These strategies are examined for their efficiency; Upper and lower bounds for the required number of rounds as well as the travelled distance are shown. In some cases, we also compare the distance traveled when using our strategies to the distance needed by an optimal global algorithm. Like this, competitive factors are derived.

Tim Süß:

Parallel real-time rendering using heterogeneous PC clusters

Often 3D scenes created with CAD applications have a high geometric complexity.There are several concepts (like out-of-core rendering, levels of detail, parallel rendering) to render such scenes in real-time.This dissertation focuses on the usage of heterogeneous PC clusters for parallel real-time rendering of highly complex scenes.For three different scene types specific rendering approaches were developed, where a small group of high-end computers is supported by a large number of weaker PC cluster nodes.The first scene type consists of static scenes that can be stored completely in a single computer's main memory, while the scenes of the second type exceed this memory limitations.The scenes of the last type contain not only static but also dynamic objects.

 

Weitere Funktionen

Friedhelm Meyer auf der Heide:

  • Member of the “Hochschulrat“ of the University of Paderborn
  • Director of the Collaborative Research Center (SFB 901) “On-The-Fly Computing"
  • Member of the German Academy of Sciences “Leopoldina“
  • DFG Special Advisor (Vertrauensdozent) of the University of Paderborn
  • Director of the NRW-Graduate School of Dynamic Intelligent Systems (one of three directors)
  • Assistant Chairman of the Paderborn Institute for Scientific Computation (PaSCo)
  • Managing Editor of “Journal of Interconnection Networks (JOIN)“, World Scientific Publishing
  • Member of the program committee of the workshop “Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2012
  • Member of the program committee of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012)
  • Member of the Evaluation Committee of the Bundeswettbewerb “Jugend Forscht“, Coordinator of the section on Computer Science and Mathematics.
  • Member of the Award Committee of the European Association for Theoretical Computer Science (EATCS)
  • Member of the Milner Award Committee

Graduiertenprogramme

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • GSANS - the Paderborn Graduate School on Applied Network Science
  • DFG Research Training Centre "Research Training Group Automatisms - Emerging structures in information technology, media, and culture"

Aktuelle Forschungsprojekte

DFG Collaborative Research Center 901:
„On-The-Fly Computing“ with the Subprojects A1  “Capabilities and limitations of local strategies in dynamic networks" (jointly with Prof. Dr. Christian  Scheideler),  C2  „On-The-Fly Compute Centers“ (jointly with Jun.-Prof.  Dr.-Christian Plessl, Prof. Dr. Marco Platzner), and Z (Central Duties of the CRC)

MULTIPLEX:
EU-IP Foundational Research on MULTIlevel comPLEX networks and systems (MULTIPLEX)

DFG-SmartTeams:
DFG-Schwerpunktprogramm 1183 „Organic Computing“ mit dem Projekt: „Smart Teams“ (zusammen mit Prof. Dr. rer. nat. Christian Schindelhauer, Freiburg)

Unsere Aktivitäten 2011

Publikationen:

Gehweiler, Joachim; Kling, Peter; Meyer auf der Heide, Friedhelm: An Experimental Comparison of Load Balancing Strategies in a Web Computing Environment. In: Wyrzykowski, Roman (Hrsg.) Proceedings of the 9th International Conference on Parallel Processing and Applied Mathematics, LNCS, 2011

Abshoff, Sebastian; Cord-Landwehr, Andreas; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter: Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks. In: Proceedings of 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, LNCS, 2011

Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: A new Approach for Analyzing Convergence Algorithms for Mobile Robots. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), LNCS, volume 6756, pp. 650--661, 2011

Kling, Peter; Meyer auf der Heide, Friedhelm: Convergence of Local Communication Chain Strategies via Linear Transformations. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 159--166, 2011

Eikel, Benjamin; Jähn, Claudius; Petring, Ralf: PADrend: Platform for Algorithm Development and Rendering. In: Gausemeier, Jürgen; Grafe, Michael; Meyer auf der Heide, Friedhelm (Hrsg.) Augmented & Virtual Reality in der Produktentstehung, HNI-Verlagsschriftenreihe, Band 295, pp. 159--170, Heinz Nixdorf Institut, Universität Paderborn, 2011

Süß, Tim; Koch, Clemens; Jähn, Claudius; Fischer, Matthias: Approximative occlusion culling using the hull tree. In: Proceedings of Graphics Interface 2011, pp. 79--86, Canadian Human-Computer Communications Society, 2011

Süß, Tim; Jähn, Claudius; Fischer, Matthias; Meyer auf der Heide, Friedhelm; Koch, Clemens: Ein paralleles Out-of-Core Renderingsystem für Standard-Rechnernetze. In: Gausemeier, Jürgen; Grafe, Michael; Meyer auf der Heide, Friedhelm (Hrsg.) Augmented & Virtual Reality in der Produktentstehung, HNI-Verlagsschriftenreihe, Band 295, S. 185--197, Heinz Nixdorf Institut, Universität Paderborn, 2011

Degener, Bastian; Fekete, Sándor; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: A survey on relay placement with runtime and approximation guarantees. Computer Science Review, 5(1): pp. 57-68, 2011

Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: Collisionless Gathering of Robots with an Extent. In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), LNCS, volume  6543, pp. 178-189, 2011

Schumacher, Tobias; Süß, Tim; Plessl, Christian; Platzner, Marco: FPGA Acceleration of Communication-Bound Streaming Applications: Architecture Modeling and a 3D Image Compositing Case Study. International Journal of Reconfigurable Computing, pp. 1--11, 2011

Renken, Hendrik; Laroque, Christoph; Fischer, Matthias: An Easy Extendable Modeling Framework for Discrete Event Simulation Models and their Visualization. In: Proceedings of The 25th European Simulation and Modelling Conference - (ESM'11), 2011

Degener, Bastian; Kempkes, Barbara; Langner, Tobias; Meyer auf der Heide, Friedhelm; Wattenhofer, Roger: A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In: Proceedings of the 23rd annual ACM symposium on parallel algorithms and architectures (SPAA'11), pp. 139-147, 2011

Klaas, Alexander; Laroque, Christoph; Fischer, Matthias; Dangelmaier, Wilhelm: Simulation Aided, Knowledge Based Routing for AGVs in a Distribution Warehouse. In: Proceedings of the 2011 Winter Simulation Conference, 2011

Brandes, Philipp; Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Energy-efficient strategies for building short chains of mobile robots locally. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO'11), pp. 138-149, 2011

Briest, Patrick; Raupach, Christoph: The Car Sharing Problem. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'11), 2011

Briest, Patrick; Hoefer, Martin; Krysta, Piotr: Stackelberg Network Pricing Games. Algorithmica, 2011

Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: Organic Computing — A Paradigm Shift for Complex Systems, Autonomic Systems, volume 1, chapter Energy-Awareness in Self-organising Robotic Exploration Teams, pp. 531-543, Springer Verlag, 2011

Briest, Patrick; Krysta, Piotr: Buying Cheap is Expensive: Approximability of Combinatorial Pricing Problems. SIAM Journal on Computing, 2011

Klaas, Alexander; Laroque, Christoph; Renken, Hendrik; Dangelmaier, Wilhelm: Goal-Based Agents in Material Flow Simulations - Integration of an Agent Programming Framework in the Discrete Event Simulator D3FACT. In: Proceedings of The 25th European Simulation and Modelling Conference (ESM'11), 2011

Briest, Patrick; Krysta, Piotr; Vöcking, Berthold: Approximation Techniques for Utilitarian Mechanism Design. SIAM Journal on Computing, 2011

 

Promotionen

Joachim Gehweiler:
Peer-to-Peer Based Parallel Web Computing
Web computing is a variant of parallel computing where the idle times of PCs donated by worldwide distributed users are employed to execute parallel programs. In this thesis we consider a web computing variant with two important properties: First, we support the execution of coupled, massively parallel algorithms (rather than distributed data processing). And second, we organize the system in peer-to-peer fashion.We present the Paderborn University BSP-based Web Computing (PUB-Web) library, which supports the execution of parallel programs in the bulk-synchronous style (BSP) in such a web computing setting. In this thesis, we focus on important technical and algorithmic aspects, in particular: In order to schedule processes with respect to the currently available computing power, which continually changes in an unpredictable fashion, we need intelligent load balancing algorithms and as a basic precondition the technical ability to migrate threads at runtime.To achieve the latter, we present the PadMig thread migration and checkpointing library. In order to tackle the distributed load balancing problem, we present an algorithm based on Distributed Heterogeneous Hash-Tables. In order to judge the quality of the schedules produced, we perform extensive experiments. Beside the available computing power, we finally also consider the network bandwidth as a secondary criterion for load balancing.

Sascha Effert:
Verfahren zur redundanten Datenplatzierung in skalierbaren Speichersystemen
Moderne Datenzentren sind mit einer rasant wachsenden Menge an Daten konfrontiert, welche sie mit immer höherer Geschwindigkeit hochverfügbar speichern müssen. Daher brauchen sie Speichersysteme, welche mit ihren Anforderungen wachsen. Zunehmend werden dazu Speichernetze eingesetzt, in welchen Datenserver einen virtuellen Speicher über Festplatten erzeugen. Dabei ist die Last des virtuellen Speichers so zu verteilen, dass die physikalischen Festplatten optimal genutzt werden. Um Ausfälle kompensieren zu können ist es nötig, Daten redundant zu speichern. Die Verfahren zur Datenverteilung müssen diesen Anforderungen gerecht werden. Einen wichtigen Beitrag liefern hier pseudorandomisierte Hashfunktionen. Innerhalb dieser Arbeit gehe ich auf verschiedene Speichersysteme ein. Speziell untersuche ich Speichernetze, welche aus Datenservern mit lokalen Festplatten bestehen. Für diese zeige ich, wie sie bei verschiedenen Arten der Datenverteilung skalieren. Leider wird keines der betrachteten Speichersysteme allen Anforderungen gerecht. Als Lösung stelle ich das Verfahren Redundant Share vor, welches alle Anforderungen erfüllt. Mittels Redundant Share kann eine beliebige Anzahl an Kopien der Daten des virtuellen Speichers wie gefordert verteilt werden. Gleichzeitig erfordert das Hinzufügen neuer Festplatten einen begrenzten Aufwand. Abschließend vermesse ich eine Implementierung von Redundant Share und vergleiche die Ergebnisse mit anderen Verteilern.

weitere Funktionen

Friedhelm Meyer auf der Heide:

  • Member of the “Hochschulrat“ of the University of Paderborn
  • Director of the Collaborative Research Center (SFB 901) “On-The-Fly Computing"
  • Member of the German Academy of Sciences “Leopoldina“
  • DFG Special Advisor (Vertrauensdozent) of the University of Paderborn
  • Member of the Board of External Scientific Advisers (Fachbeirat) of the Max-Planck-Institute for Computer Science at Saarbrücken
  • Direktor der NRW-Graduate School of Dynamic Intelligent Systems (one of three directors)
  • Assistant Chairman of the Paderborn Institute for Scientific Computation (PaSCo)
  • Managing Editor of “Journal of Interconnection Networks (JOIN)“, World Scientific Publishing
  • Member of the program committee of the workshop “Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2011
  • Member of the Evaluation Committee of the Bundeswettbewerb “Jugend Forscht“, Coordinator of the section on Computer Science and Mathematics.
  • General Chair of the ACM-Symposium “Parallelism in Algorithms and Architectures (SPAA)“
  • Member of the Award Committee of the European Association for Theoretical Computer Science (EATCS)

Patrick Briest:

  • Member of the program committee of the "ACM Conference on Electronic Commerce (EC)", 2011.
  • Member of the program committee of the "International Symposium on Theoretical Aspects of Computer Science (STACS)", 2011.

Graduiertenprogramme:

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • GSANS - the Paderborn Graduate School on Applied Network Science
  • DFG Research Training Centre "Research Training Group Automatisms - Emerging structures in information technology, media, and culture"

Aktuelle Forschungsprojekte

DFG Collaborative Research Center 901:

„On-The-Fly Computing“ with the Subprojects A1  “Capabilities and limitations of local strategies in dynamic networks" (jointly with Prof. Dr. Christian  Scheideler),  C2  „On-The-Fly Compute Centers“ (jointly with Jun.-Prof.  Dr.-Ing.  André Brinkmann, Prof. Dr. Marco Platzner), and Z (Central Duties of the CRC)

FRONTS:

EU-Strep “Foundations of Adaptive Networked Societies of Tiny Artefacts“

DFG-SmartTeams:

DFG-Schwerpunktprogramm 1183 „Organic Computing“ mit dem Projekt: „Smart Teams“ (zusammen mit Prof. Dr. rer. nat. Christian Schindelhauer, Freiburg)

DFG-AVIPASIA:

DFG project “Interactive Model Modification, Synchronized Analysis and 3D Visualization of Parallel Discrete Event Simulation“ (with Prof. Dr.-Ing. habil. Wilhelm Dangelmaier and Dr. rer. nat. Matthias Fischer)

Unsere Aktivitäten 2010

Publikationen

Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; Warner, Daniel; Weddemann, Christoph; Wonisch, Daniel: Collision-less gathering of robots with an extent. In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), 22. - 28. Jan. 2011, Springer

Janson, Thomas; Mahlmann, Peter; Schindelhauer, Christian: A Self-Stabilizing Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs. In: Proceedings of the 16th International Conference on Parallel and Distributed Systems (ICPADS’10), Shanghai, China, 9. - 10. Dez. 2010, IEEE

Suess, Tim; Wiesemann, Timo; Fischer, Matthias: Evaluation of a c-Load-Collision-Protocol for Load-Balancing in Interactive Environments. In: 5th IEEE International Conference on Networking, Architecture, and Storage, S. 448 - 456, 15. - 17. Jul. 2010 IEEE Computer Society, IEEE Press

Dumrauf, Dominic; Suess, Tim: On the Complexity of Local Search for Weighted Standard Set Problems. In: Proc. 6th Conference on Computability in Europe, S. 132-140, 30. Jun. - 4. Jul. 2010

Abramsky, Samson ; Gavoille, Cyril ; Kirchner, Claude ; Meyer auf der Heide, Friedhelm; Spirakis, Paul G. (Hrsg.) 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) Part I. LNCS, Band 6198, Bordeaux, France, Jul. 2010, Springer

Abramsky, Samson ; Gavoille, Cyril ; Kirchner, Claude ; Meyer auf der Heide, Friedhelm; Spirakis, Paul G. (Hrsg.) 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) Part II. LNCS, Band 6199, Bordeaux, France, Jul. 2010, Springer

Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane: Kinetic Facility Location. Algorithmica, 57(3): S. 562-584, Jul. 2010

Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm: A continuous, local strategy for constructing a short chain of mobile robots. In: SIROCCO '10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, LNCS, Band 6058, S. 168-182, 7. - 11. Jun. 2010, Springer

Meyer auf der Heide, Friedhelm; Phillips, Cynthia (Hrsg.) SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures. , Thira, Santorini, Greece, Jun. 2010, ACM Press

Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: A local O(n²) gathering algorithm. In: SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, S. 217-223, Jun. 2010, ACM

Suess, Tim; Jaehn, Claudius; Fischer, Matthias: Asynchronous Parallel Reliefboard Computation for Scene Object Approximation. In: Eurographics Symposium on Parallel Graphics and Visualization (EGPGV), S. 43-51, Norrköping, Sweden, Mai 2010 Eurographics Association, Eurographics Association

Mense, Mario; Schindelhauer, Christian: Read-Write-Codes: An Erasure Resilient Encoding System for Flexible Reading and Writing in Storage Networks. In: Proceedings of 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Lecture Notes in Computer Science, Band 5873, S. 624--639, 2010, Springer

Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter: A local, distributed constant-factor approximation algorithm for the dynamic facility location problem . In: International Parallel & Distributed Processing Symposium (IPDPS), 2010

Fischer, Matthias; Renken, Hendrik; Laroque, Christoph; Schaumann, Guido; Dangelmaier, Wilhelm: Automated 3D-Motion Planning for Ramps and Stairs in Intra-Logistics Material Flow Simulations. In: Proceedings of the 2010 Winter Simulation Conference (WSC 2010), S. 1648 - 1660, 5. - 8. Dez. 2010 IEEE, Omnipress

Damerow, Valentina; Manthey, Bodo; Meyer auf der Heide, Friedhelm; Räcke, Harald; Scheideler, Christian; Sohler, Christian; Tantau, Till: Smoothed Analysis of Left-To-Right Maxima with Applications. akzeptiert in: ACM Transactions on Algorithms 2010

Briest, Patrick; Chalermsook, Parinya; Khanna, Sanjeev; Laekhanukit, Bundit; Nanongkai, Danupon: Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. In: Workshop on Internet and Network Economics (WINE), 2010 (Details)

Briest, Patrick; Röglin, Heiko: The Power of Uncertainty: Bundle-Pricing for Unit-Demand Customers. In: Workshop on Approximation and Online Algorithms (WAOA), 2010 (Details)

Briest, Patrick; Chawla, Shuchi; Kleinberg, Robert D.; Weinberg, S. Matthew: Pricing Randomized Allocations. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010

Gehweiler, Joachim; Meyerhenke, Henning: A Distributed Diffusive Heuristic for Clustering a Virtual P2P Supercomputer. In: Proceedings of 24th International Parallel and Distributed Processing Symposium (IPDPS, HPGC), 2010

Meyer auf der Heide, Friedhelm; Scheideler, Christian: Algorithmische Grundlagen verteilter Speichersysteme. Informatik-Spektrum, 33(5): S. 468-474 2010

Degener, Bastian; Fekete, Sándor; Kempkes, Barbara; Meyer auf der Heide, Friedhelm: A survey on relay placement with runtime and approximation guarantees. Computer Science Review 2010

Gehweiler, Joachim; Meyer auf der Heide, Friedhelm: Bin Packing - How Do I Get My Stuff into the Boxes?. In: Algorithms Unplugged, Springer, 2010

Eikel, Benjamin; Jaehn, Claudius; Fischer, Matthias: Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware. In: Advances in Visual Computing, Lecture Notes in Computer Science, Band 6453, S. 622--633. Springer, Berlin / Heidelberg, 2010

Suess, Tim; Wiesemann, Timo; Fischer, Matthias: Gewichtetes c-Collision-Protokoll zur Balancierung eines parallelen Out-of-Core-Renderingsystems. In: Augmented & Virtual Reality in der Produktentstehung, S. 39-52, 2010 Universität Paderborn, HNI Verlagsschriftenreihe

Meyerhenke, Henning; Gehweiler, Joachim: On Dynamic Graph Partitioning and Graph Clustering using Diffusion. In: Dagstuhl Seminar Proceedings 10261: Algorithm Engineering, 2010

 

Promotionen

Dr. rer. nat. Jan Mehler:
Power-aware online file allocation in dynamic networks
Sowohl die Vernetzung von mobilen drahtlosen Geräten wie Smartphones und PDAs als auch die Verbreitung von Sensornetzwerken nimmt zur Zeit stark zu. Eine wesentliche Anforderung an solche mobilen ad hoc Netzwerke besteht darin, den Netzwerkknoten eine gemeinsame Nutzung von Daten zu ermöglichen. Beim von Bartal eingeführten File Allocation Problem hat ein Datenverwaltungssystem die Möglichkeit nach Bedarf beliebig viele Kopien eines Datums auf den Knoten des Netzwerks zu erzeugen und auch wieder zu löschen. Da die Knoten eines mobilen ad hoc Netzwerks in der Regel nur eine stark beschränkte Energiereserve besitzen, besteht unser Ziel darin Algorithmen zu entwickeln, die den bei der Bedienung einer Folge von Lese- und Schreibanfragen der Netzwerkknoten anfallenden Energiebedarf, möglichst gering halten. Um dies zu erreichen muss ein Algorithmus Kopien so im Netzwerk platzieren, dass sie zwar möglichst nahe an den zugreifenden Knoten liegen, aber gleichzeitig eine Aktualisierung aller Kopien nicht zu teuer wird. Wir verallgemeinern das File Allocation Problem von Bartal auf Netzwerke, die sich mit der Zeit verändern. Dabei besteht eine wesentliche Herausforderung darin, dass weder bekannt ist welche Anfragen in Zukunft gestellt werden noch wie sich das Netzwerk verändern wird. Wir untersuchen die Qualität verschiedener online Algorithmen für das File Allocation Problem in dynamischen Netzwerken sowohl theoretisch als auch mittels simulationsbasierter Experimente.

Dr. rer. nat. Peter Mahlmann:
Peer-to-peer networks based on random graphs
Peer-to-Peer Netzwerke gehören zur Klasse der Overlay-Netzwerke, d.h. für die Kommunikation zwischen den Netzwerkteilnehmern (Peers) wird ein darunter liegendes, physikalisches Netzwerk (zumeist das Internet) verwendet. Eine besondere Eigenschaft ist die symmetrische Funktionalität der Peers, d.h. jeder Peer agiert sowohl als Server als auch als Client. Diese Eigenschaft bietet das Potenzial für sehr hohe Robustheit, da ein ausgefallener Peer durch jeden anderen ersetzt werden kann. Es ist wichtig diese potenziell vorhandene Robustheit auch tatsächlich beim Entwurf von Peer-to-Peer Netzwerken zu nutzen, da Untersuchungen zeigen, dass Peer-to-Peer Netzwerke einer sehr starken Dynamik unterliegen. Somit ist es sinnvoll eine einfache Netzwerkstruktur zu wählen, die auch bei starker Dynamik aufrechterhalten werden kann und die Funktionalität des Netzwerks garantiert. Dieses Kriterium wird z.B. von Zufallsnetzwerken erfüllt. In dieser Arbeit stellen wir lokale Graph-Transformationen zum Aufbau und der Aufrechterhaltung von Zufallsnetzwerken ohne zentrale Koordination vor. Diese erlauben es auch im Fall starker Dynamik Eigenschaften wie logarithmischen Durchmesser und Expansionseigenschaft durch lokale Handshake-Operationen mit minimalen Kommunikationskosten aufrecht zu erhalten. Um das Problem der effizienten Suche in Zufallsnetzwerken zu umgehen, setzen wir Zufallsnetzwerke als Baustein für ein strukturiertes Peer-to-Peer Netzwerk ein. Im 3nuts Netzwerk werden Zufallsnetzwerke, Such-Bäume und verteilte Hash-Tabellen auf geschickte Art und Weise kombiniert um ihre jeweiligen Stärken zu erhalten und die jeweiligen Schwächen zu umgehen. Die resultierende Netzwerkarchitektur ist selbst-stabilisierend, Last-balanciert, unterstützt Bereichsanfragen und erlaubt Routing mit niedrigen Latenzen durch Anpassung der Overlay-Struktur an das physikalische Netzwerk.

Dr. rer. nat. Sebastian Degener:
Local, distributed approximation algorithms for geometric assignment problems

Wir betrachten eine Gruppe von autonomen Robotern, die in einem unbekannten Gelände ausgesetzt werden. Es gibt keine zentrale Steuerung und die Roboter müssen sich selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen. In dieser Arbeit wird untersucht, wie in einem solchen Szenario Zuweisungsaufgaben gelöst werden können, so dass sich trotz der lokalen Einschränkungen global beweisbar gute Lösungen ergeben. Dabei werden im ersten Teil der Arbeit Roboter zu Schätzen zugewiesen, die im Gelände gefunden wurden. Im zweiten Teil der Arbeit werden dynamische Rollenzuweisungen innerhalb des Roboterteams vorgenommen. Dabei müssen die Zuweisungen mit der Zeit geändert werden, da die Roboter sich bewegen. Es werden jeweils untere Schranken gezeigt, sowie lokale Approximationsalgorithmen beschrieben und analysiert.

 

weitere Funktionen

Friedhelm Meyer auf der Heide:

  • Mitglied des Hochschulrats der Universität Paderborn
  • Mitglied der Deutschen Akademie der Naturforscher „Leopoldina“
  • DFG-Vertrauensdozent der Universität Paderborn
  • Mitglied des Fachbeirats des Max-Planck-Instituts für Informatik, Saarbrücken
  • Direktor der NRW-Graduate School of Dynamic Intelligent Systems (einer von drei Direktoren)
  • Stellvertretender Vorsitzender des Paderborn Institute for Scientific Computation (PaSCo) und seines Graduiertenkollegs
  • Managing Editor des „Journal of Interconnection Networks (JOIN)“, World Scientific Publishing
  • Mitglied im Programmkomitee des Workshops „Parallele Algorithmen, Rechnerstrukturen und Systemsoftware (PARS)“, 2010
  • Leiter des Programmkomitees des Track C “Foundations of networked Computation” des “37th International Colloquium on Automata, Languages and Programming (ICALP 2010)”
  • Leiter der Sektion Informatik und Mathematik der Bundes-Jury des Bundeswettbewerbs “Jugend Forscht“,
  • General Chair des ACM-Symposiums „Parallelism in Algorithms and Architectures (SPAA)“
  • Mitglied des Award Committee der European Association for Theoretical Computer Science (EATCS)

Patrick Briest:

  • Mitglied im Programmkomitee des "International Symposium on Theoretical Aspects of Computer Science (STACS)", 2011.

 

Graduiertenprogramme:

  • International Graduate School: NRW Graduate School of Dynamic Intelligent Systems
  • Pasco-GK: DFG-Graduiertenkolleg „Wissenschaftliches Rechnen“
  • DFG-Graduiertenkolleg „Automatismen - Strukturentstehung außerhalb geplanter Prozesse in Informationstechnik, Medien und Kultur“

Aktuelle Forschungsprojekte

AEOLUS: EU-Integrated Project “Algorithmic Principles for Building Efficient Overlay Computers“ (AEOLUS)

FRONTS: EU-Strep “Foundations of Adaptive Networked Societies of Tiny Artefacts“

DFG-SmartTeams: DFG-Schwerpunktprogramm 1183 „Organic Computing“ mit dem Projekt: „Smart Teams“ (zusammen mit Prof. Dr. rer. nat. Christian Schindelhauer, Freiburg)

DFG-AlgoEngCG: DFG-Schwerpunktprogramm 1307 „Algorithm Engineering“ mit dem Projekt: „Algorithm Engineering für Probleme der Computergrafik“ (zusammen mit Dr. rer. nat. Matthias Fischer)

DFG-AVIPASIA: DFG-Projekt „Synchronisierte Analyse und 3D-Visualisierung paralleler Ablaufsimulationen in interaktiv erstellten Ausprägungen“ (zusammen mit Prof. Dr.-Ing. habil. Wilhelm Dangelmaier und Dr. rer. nat. Matthias Fischer)

ViProSim: Kompetenzzentrum „Verteilte Visualisierung und Simulation“. Zielvereinbarung der Universität Paderborn und dem Ministerium für Wissenschaft und Forschung des Landes Nordrhein-Westfalen