Aktuell:
Project Group: Resource Allocation in disTributed Systems (RATS)
This project group focuses on modelling, solving and analyzing resource allocation problems in distributed systems from a theoretical viewpoint. We consider large distributed systems consisting of peers that offer a variety of resources such as computational power or locally stored information, e.g., virtual machines, CPU time, databases. Over time, different entities pose requests in such a system which ask for the access to some resource. These requests have to be answered by the peers incurring costs that model limitations of the system, e.g., processing speed, data rate between peers and overhead paid due to the allocation of local resources. We consider both centralized and distributed solutions as well as algorithms which do not know the requests in advance and have to adapt to the input on the fly. The scenario is closely related to the OTF computing scenario currently research in subproject A1 of the CRC901 (https://sfb901.uni-paderborn.de/).
Within this broad scenario, we want to design algorithms that offer a low cost when answering requests while having only a small demand on the capabilities of the peers. We aim at theoretical models capturing the various possible settings in which we want to analyze our algorithmic approaches. The typical theoretical frameworks used in theory are those of approximation and online algorithms. Approximation algorithms aim to compute almost optimal solutions while simultaneously running in polynomial time. On the other hand, online algorithms deal with inputs which are not known completely at the beginning of the computation and therefore have to make decisions without knowledge of the future. Despite this lack of knowledge the aim is to design algorithms which compute solutions which are close to the optimum. The tasks of the project group also include the implementation of a simulation environment which allows us to benchmark the designed solutions by generating different instances of the problem and evaluating the algorithms under different metrics.
Further Reading
There already exists a large body of literature on different problems within the scope of resource allocation. The following list of papers offers a general overview on the topic and on the techniques we want to apply within this project group. For the two topics approximation and online algorithms we have linked one survey paper covering a variety of models and results for overview and a technical paper for a concrete problem illustrating the type of techniques which are required to solve these types of problems.
| 1) | Online algorithms: a survey | https://doi.org/10.1007/s10107-003-0436-0 |
| 2) | New results on server problems | https://doi.org/10.1137/0404017 |
| 3) | Approximation algorithms for facility location problems | https://doi.org/10.1007/3-540-44436-X_4 |
| 4) | Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation | https://doi.org/10.1145/375827.375845 |
Requirements
This project group targets at students that are interested and experienced in the theory of computing.
To participate successfully in the project group, a solid understanding of the basic concepts of theoretical computer science as well as basics from analysis, algebra and stochastics is necessary. We recommend to consult the reading list above to get a first idea of the concepts which are central to the project group. We also strongly recommend to apply for the identically named seminar Resource Allocation in disTributed Systems (Seminar) which will cover current results in the research area which is the topic of this project group.
If you are interested in participating in the project group, please submit the assignment given through the Jupyter system: pg.cs.upb.de
For additional information on the registration for a project group, visit https://cs.uni-paderborn.de/en/studies/study-elements/project-groups/