Home > Research Groups > Algorithms and Complexity > Teaching > Seminar: Resource Allocation in disTributed Systems (RATS)

Seminar: Resource Allocation in disTributed Systems (RATS)

In this Seminar we are going to explore popular models and techniques in the area of resource allocation problems in large networks. Topics will typically consist of an introduction into a model and used techniques, and an important or interesting result in the introduced problem based on the given techniques.

The application for this Seminar is managed through the Jupyter System. Klick here for more information on the application procedure.


Materials

You can find all relevant materials including the slides of the introductory talk on the page of the seminar in PAUL.

Lecturer

Friedhelm Meyer auf der Heide

Modul

Seminar I / Seminar II
Modules III 2.1, 2.2

Dates & Deadlines

  • First meeting (distribution of topics):
    October 9th, 2019, 15:00, F0.530, Fürstenallee 11

  • First meeting with advisor (You are expected to have read the paper, and come with concrete questions):
    November 14th-15th, 2019

  • Please note the exam registration deadlines in PAUL!
    October 21st - November 21st, 2019

  • Submission deadline of the 0-version of seminar thesis (see Step II below):
    December 16th, 2019

    (We strongly recommend to give at least part of the thesis to your advisor in advance to this deadline, in consultation with him)

  • Submission deadline of the reviews (see Step III below):
    January 13th, 2020

  • Submission deadline of the final version of the seminar thesis:
    January 27th, 2020

  • Block Seminar, Presentation of your work (see Step I below):
    February 6th-7th, 2020


Topic Assignment and Registration

The topics are given in the first meeting. Reservations or defaults of issues are not possible. In order to make an informed choice, we expect you to have a look at all the topics listed below before the first meeting. The registration process is centrally organized through the Jupyter system, where you can enter your preferences. However, this does not guarantuee you can get a topic from your submitted list.

Grading and Demands

I) Presentation

45 minutes presentation and 15 minutes discussion and questions.
Your audience: Your fellow students.
    
As a minimal requirement, the presentation should motivate your model, formally introduce the problem, explain the necessary techniques, and provide insight into the necessary algorithms and their analysis. In paired topics, we expect both students to equally contribute to the presentation.

II) Seminar thesis

Essay of length 15 to 20 pages written according to the standards of a scientific paper.
Submitting work of others is cheating and a violation of academic plagiarism rules, which is a serious offense. We use a commercial, Internet-based plagiarism detection service to check your submissions.

III) Reviews

Peer review procedure similar to scientific publications.
You submit your thesis (paper) at easychair.org.
Some (2-3) peers (other students) review your submission.
    • Read and understand the submitted paper
    • Criticize the paper
    • Make recommendations on how to improve
    • Be honest, polite, and helpful when writing your reviews
Possible Criteria:
    • Structure of the paper
    • Self-containment (necessary terms are defined)
    • Thoroughness and correctness of the presented arguments
    • Formatting & Language
The reviews you write will influence your final grade.
The reviews you receive will not influence your grade (but your final version).
Each student has to write 2 reviews (each 1-2 pages).

We expect your active participation (as opposed to mere attendance) at all presentations of this seminar.

We will grade the quality of the presentation and the quality of the essay / seminar thesis individually. You have to pass (i.e., 4.0 or better) each part individually to pass this course. Note that commitment, diligence, and compliance with our deadlines will be taken into account. Note that attempts of cheating / plagiarism immediately lead to a failure of the seminar.

Remarks

General

We expect each participant to take care of their own work independently. It is your responsibility to contact your advisor and schedule appointments with them early enough. We strongly recommend you to discuss questions regarding the topic, the composition, and the structure of your written seminar thesis with your advisor as early as possible. Starting only one week before any of the deadlines will not be sufficient. Note also that finding an appointment directly before your thesis' submission or seminar talk cannot be guaranteed, since the advisors need to arrange their appointments with their own teaching and research.

Each topic has one or several references that should be understood as starting points for your research. Hence, it is very likely that you will need further papers or textbooks to fully understand your topic. The actual content of your seminar thesis as well as your seminar talk should be discussed with your advisor. The same holds for your seminar talk. Make use of search engines for scientific papers to find more references relevant for your topic.


Seminar Thesis

We expect an essay of length 15 to 20 pages written according to the standards of a scientific paper. A simple summary of the referenced literature is insufficient. We expect you to identify the important ideas and proofs of the referenced literature and present them in a correct and appropriate way. We strongly recommend to use LateX for your thesis (see below for a possible style). All citations must be marked as such and referenced with their origin. Plagiarism directly leads to failure of the seminar. Note that plagiarism not only includes copies from the original literature, but also copies from other authors (e.g., other seminar thesis or wikipedia) or translations of them.

Title and Abstract

Create a brief abstract that summarizes the problem and the main results. An abstract is kept short (typically 10-20 lines). Also make up a title for your thesis (note that this is not necessarily the title of the used literature or the title from our topic list). It is important to make your own reasoning about a title that describes the thesis best from your point of view.

References

Each thesis contains a reference list that contains at least the literature used in your thesis. In the digital libraries of DBLP, ACM, IEEE, or Springer you can find detailed literature reference information. For conference proceedings or journals ALWAYS specify the pages. For journals, additionally provide volume and journal number. Do not rely on the authors to do their references correct (e.g., reference list in a paper or at the author's website). Sometimes these references are wrong or incomplete. Also do not rely on search engines like CiteSeer or Google Scholar: always verify the correctness and completeness of your references. Especially, it is insufficient if you only provide links to the papers or citations in the web.

LaTeX Style

We recommend the usage of an existing template suited for scientific papers.
Examples:
The ACM Master Template www.acm.org/publications/proceedings-template
Springer LaTeX Template www.springer.com/gp/livingreviews/latex-templates
LIPIcs LaTeX Template www.dagstuhl.de/en/publications/lipics/instructions-for-authors/

Submission

The submission of your thesis as well as the reviews are done via easychair here: https://easychair.org/conferences/?conf=rats2020

Topics

1. A Primal Dual Approximation for Facility Location

Many approximation and online algorithms are based on the technique of Primal-Dual algorithms which are based on the principle of weak duality for linear programs. This topic introduces the technique and the underlying principles and then applies it to the Metric Facility Location problem. In that problem, we are given a set of clients and possible facility locations located in the same metric space. The goal is to open a set of facilities and connect all clients to a facility such that the cost for opening facilities and connections between clients and facilities are minimized.
  
doi.org/10.1561/0400000024
m.tau.ac.il/~nivb/download/pd-survey.pdf
doi.org/10.1145/375827.375845
  
Advisor: Björn Feldkord

2. Online Data Management

We consider the general setting of File Allocation, where a File can be copied and moved with a network to answer read and write requests to the file. For write requests, consistency must be maintained. For a subproblem called File Migration, which deals with the placement of just a single copy over time, we consider an extended variant with exactly k copies and how to derive competitive algorithms based on the classical k-Server problem.
  
doi.org/10.1016/S0890-5401(03)00055-5
doi.org/10.1016/S0304-3975(00)00259-0
  
Advisor: Björn Feldkord

3. Weak Adversaries for the k-Server Problem

The k-Server problem is one of the most popular online problems in theoretical computer science. Given are k servers located in a metric space. In each time step a request arrives which must be served by moving one server onto the request. The goal is to minimize the total movement. We explore the basic algorithms given when the problem was first introduced and then consider a more recent resources augmentation variant, in which the online algorithm has more servers than the offline solution it is compared to.
  
doi.org/10.1016/0196-6774(90)90003-W
doi.org/10.1137/0404017
doi.org/10.1145/3301314
  
Advisor: Björn Feldkord

4. Randomized Online Algorithms and Tree Metrics

For many optimization problems in metric spaces it is often easier to design algorithms for tree metrics than general metrics. We discuss a technique to embedd any metric space into a tree metric which approximates the original distances within a log(n)-factor. We then show how to use this embedding to derive an online algorithm for the k-Server problem with just polylogarithmic competitive ratio.
  
doi.org/10.1109/SFCS.1996.548477
doi.org/10.1145/2783434
  
Advisor: Till Knollmann

5. The Competitive Ratio of the Online Facility Location Problem

In the Online Facility Location problem, clients arrive over time and must be connected to an open facility immediately. An algorithm decides where to open a facility which implies cost possibly dependent on the location. The goal is to minimize the cost for opening facilities and connecting clients to them. We consider first a simple randomized algorithm and then more complex deterministic algorithms for the problem. The results are complemented by a lower bound which demonstrates that randomized and deterministic algorithms are equal in power w.r.t. the competitive ratio.
  
doi.org/10.1109/SFCS.2001.959917
doi.org/10.1007/s00453-007-9049-y
doi.org/10.1016/j.jda.2006.03.001
  
Advisor: Till Knollmann

6. The Competitive Ratio of Randomized Online Algorithms

We explore the different types of adversaries used in the context of randomized algorithms and apply them to a simple example problem. The different adversaries are connected in the sense that an algorithm effective against one of them implies the existence of algorithms against the other adversaries as well. The same is true for lower bounds for a given problem. We explore this on the example of File Migration, where one File can be migrated in a network to reduce cost for accessing the file.
  
doi.org/10.1007/BF01294260
doi.org/10.1137/S0097539791199796
  
Advisor: Till Knollmann

7. Distributed Facility Location in the CONGEST Model

In the Metric Facility Location problem, a set of clients must be assigned to facilities. An algorithm aims at minimizing the total cost induced by opening facilities as well as all the distances between facilities and their assigned clients. This problem is also of interest in distributed systems, where the peers of a network not only want to solve the problem, but they want to compute the result in few communication rounds with preferably small messages. The given papers consider the CONGEST model, where the message size is bounded at each peer in each communication round, and establish techniques to quickly compute a maximal independent set on the network. Afterwards, the technique is used for a distributed primal-dual algorithm allowing to solve the problem in a small number of communication rounds while achieving a constant approximation ratio.

doi.org/10.1145/1281100.1281111
doi.org/10.1145/1582716.1582747
  
Advisor: Till Knollmann