Research Projects of the Distributed Algorithms Group
Here is an overview of ongoing projects.
Solving Combinatorial Optimization Problems using Peer-to-Peer Networks
Researchers: Peter Merz, Thomas Fischer, Matthias Priebe
Large combinatorial optimization problems pose a major challenge even for modern heuristic optimization techniques.
Because of their NP-hardness property, these problems feature exceedingly extensive search spaces.
One particularly prominent example is the Traveling Salesman Problem (TSP), one of the most widely known and practically most relevant combinatorial problems. Since the exact solution is usually intractable to obtain for large problem instances, heuristics are the preferred means to solve the problem at hand, but even this approach requires massive amounts of computation power. We focus on Peer-to-Peer networks as a source of huge computational resources that may be leveraged for the purpose of solving NP-hard problems.
We wish to deliver a problem-independent middleware for distributed computation in Peer-to-Peer networks.
On top of this platform, we intend to deploy distributed algorithms to search for solutions to the TSP and other NP-hard problems.
As we concentrate on solving large problem instances, we develop heuristic algorithms specially customized to handle distributed computation and large data sets.
Within our group, there are simultaneous activities on both fields.
You can learn more about the middleware or about solving the TSP and other problems.
Distributed Scheduling of Jobs in Grid Environments
Researchers: Peter Merz, Mathias Dalheimer
This project considers alternative approaches for job scheduling in grid environments. Instead of Using a centralized job scheduler, decentralized approaches are studied based on buyer and seller agents. Within this framework, auctions are used for deciding which resource runs which job. This enables the use of dynamic strategies for "resource sellers" depending on the actual market situation and also a flexible way for "resource buyers" to choose from the available resources.
P2P Topologies and Algorithms for P2P Grids
Researchers: Peter Merz
Using Peer-to-Peer (P2P) technology for distributed computing requires efficient protocols for group management and resource discovery. Approaches for file-sharing or lookup such as Distributed Hash Tables are not well-suited for P2P overlays for distributed computing (also called P2P Grids or Desktop Grids).
We focus in this project on distributed algorithms for highly dynamic resource discovery and overlay management in a fault-tolerant way. The project concentrates on epidemic algorithms for overlay management in combination with effictive broadcast/multicast schemes for job announcement. Aspects like trust, security and incentive mechanisms are also considered.
Read more...
-