Local Algorithms

Print

Overview

The central control and optimization of networks reaches its limits if networks become very large and change constantly. Examples of such networks are the Internet, web graphs, peer-to-peer systems or large teams of mobile robots with limited sensor range. Therefore, the nodes themselves have to decide upon their actions, whereby they only possess a limited, local view on the overall network. On the other hand, such local strategies, performed by nodes of the network, should lead to a globally good behavior.

In this seminar, local algorithms for various problems are presented and analyzed. A nice overview of some aspects of the subject can be found in

http://www.cs.helsinki.fi/u/josuomel/publications/local-survey.html

The seminar will be held in English. 

Dates 

  • First meeting (assigment of topics):
    Wednesday, April 10th 2013, 4pm, F0.530 (Fürstenallee!)

  • Submission Deadline for written Seminar Thesis:
    Sunday, June 30th 2013 11:59:59 p.m.

  • Block seminar:
    Monday, July 15th 2013 after 2:00 pm, and
    Tuesday, July 16th 2013 all day
     

Preliminary List of Topics

This is a preliminary list of topics which will be extended soon. All links are available within the university's network.

  1. Local Decision without Identifiers

    Pierre Fraigniaud, Mika Göös, Amos Korman, Jukka Suomela: What can be decided locally without identifiers? CoRR abs/1302.2570 (2013) http://arxiv.org/abs/1302.2570

  2. Hardness of Distributed Approximation

    Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer: Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41(5): 1235-1265 (2012) http://dx.doi.org/10.1137/11085178X

  3. Maximal Independent Sets in Growth-Bounded Graphs

    Johannes Schneider, Roger Wattenhofer: A log-star distributed maximal independent set algorithm for growth-bounded graphs. PODC 2008: 35-44 http://dl.acm.org/citation.cfm?doid=1400751.1400758

  4. Computing the Diameter of a Network

    Silvio Frischknecht, Stephan Holzer, Roger Wattenhofer: Networks cannot compute their diameter in sublinear time. SODA 2012: 1150-1162 http://dl.acm.org/citation.cfm?id=2095207

  5. Distributed Algorithms for Edge Dominating Sets

    Jukka Suomela: Distributed algorithms for edge dominating sets. PODC 2010: 365-374 http://dl.acm.org/citation.cfm?doid=1835698.1835783

  6. Local algorithms in (weakly) coloured graphs

    Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, Jara Uitto: Local algorithms in (weakly) coloured graphs. CoRR abs/1002.0125 (2010) http://arxiv.org/abs/1002.0125

  7. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

    Matti Åstrand, Jukka Suomela: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. SPAA 2010: 294-302 http://doi.acm.org/10.1145/1810479.1810533

  8. Local Control Strategies

    Zhiyun Lin, Mireille E. Broucke, Bruce A. Francis: Local control strategies for groups of mobile autonomous agents. IEEE Trans. Automat. Contr. 49(4): 622-629 (2004) http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1284730

  9. Robot convergence via center of gravity algorithms

    Reuven Cohen and David Peleg. Robot convergence via center of gravity algorithms. In Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2004, pages 79-88, June 2004. http://u.math.biu.ac.il/~reuven/publications/sirocco.pdf

  10. Gathering of Asynchronous Robots with Limited Visibility

    Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Gathering of Asynchronous Robots with Limited Visibility. Theoretical computer science, 337(1-3):147-168, 2005. http://people.scs.carleton.ca/~santoro/Reports/Robots-Limited.pdf

  11. Point Formation and Related Agreement Problems for Synchronous Mobile Robots with Limited Visibility

    Hideki Ando, Ichiro Suzuki, Masafumi Yamashita. Point Formation and Related Agreement Problems for Synchronous Mobile Robots with Limited Visibility. 1995. http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA296911

  12. Worst-Case Optimal Geographic Routing

    Fabian Kuhn, Rogert Wattenhofer, Aaron Zollinger: Worst-Case optimal and average-case efficient geometric ad-hoc routing. MobiHoc (2003). http://dl.acm.org/citation.cfm?id=778447

  13. Beaconless Geographic Routing

    Stefan Rührup, Ivan Stojmenović: Contention-based georouting with guaranteed delivery, minimal communication overhead, and shorter paths in wireless sensor networks. IPDPS (2010). http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5470408

  14. Reactive Topology Control for Routing in Wireless Networks

    Hanna Kalosha, Amiya Nayak, Stefan Rührup Ivan Stojmenovic: Select-and-Protest-based Beaconless Georouting with Guaranteed Delivery in Wireless Sensor Networks. INFOCOM (2008). http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4509673

Topic Assignment and Registration

The topics are assigned in the first meeting. Reservations are not possible. You must register yourself in PAUL to attend this seminar. Unregistered students are not considered. The order of registration is of no importance. If there are more students interested in this seminar than places available, the selection of participants is made according to the study progress. For this seminar, e.g., the requirement would be the completed bachelor.

The seminar topics will be published here until the end of March. You should have a look at the topics and respective papers before the first meeting and choose topic preferences. 

Module 

  • Modules III 2.1, 2.2

Grading

We will grade the following parts of this course individually:

  • quality of the presentation
  • quality of the essay
  • (brief) oral exam

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.

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

Remarks

General

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. 

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. The same holds for your seminar talk. Note 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. 

If you are looking for additional research papers, the following links might be helpful:

Presentation

You should present your topic in a presentation of 45 minutes. After that there will be a discussion of about 15 minutes.

Seminar Thesis

We expect an essay of length 12 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. The mandatory typesetting for your thesis is LaTeX (see below for details). All citations must be marked as such and referenced to 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 theses) 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 conferencing 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.

Further Reading

For further reading we advice

Submission of your Seminar Thesis (updated version)

 

The thesis has to be created with LaTeX using our customized version of the svmult-Style package (Version 5.4 of the package Contributed Books, Proceedings and similar with changes as explained below) by Springer. We will create a complete volume consisting of all submissions. You have to submit the LaTeX sources AND a complete pdf of your seminar thesis by mail. The mail shall contain only one zip or tar.gz file with these data and must be sent to Sebastian Abshoff. Please do NOT include your matriculation number in your thesis. For the LaTeX document you have to follow the following rules of the game:

 

 

  • The document must be compiled with pdflatex. Hence, pictures must to be included as pdf, jpg or png.
  • There is only one "*.tex" file for your complete seminar thesis.
  • For an easy start: use the file "author.tex" from the svmult-package and extend it. All pictures and the LaTeX file itself have to be contained in the same directory.
  • Your file must be encoded in UTF-8.
  • Your highest breakdown-level is \section. (Thus, you can use \section, \subsection, \subsubsection, \paragraph, etc.)
  • To distinguish all self-defined commands, labels and references, each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi".)
  • Each command, label and reference consists of the prefix, followed by an individual identifier. Thus, if Matthias wants to call a label "myCoolLabel", the label has to be defined by \label{MaFiMyCoolLabel}.
  • The name of your LaTeX file consists only of your prefix supplemented by the suffix ".tex" (e.g., "MaFi.tex"). Each picture is prefixed with your personal prefix.
  • After the \maketitle call in your LaTeX document, you have to add your abstract with the command "\abstract{ ... }". After the abstract add your local table of contents with the commands "\bigskip\par\hrule\smallskip\par\setcounter{minitocdepth}{2} \dominitoc".
  • We only use the svmult theorem environment. This means, the option "nospthms" and the package "amsthm" can not be used. (The package "amsthm" is not compatible to "svmult".)
  • We do not use the BibTeX compiler to process literature references. Instead of this, you have to add your literature references like presented in the svmult template file "reference.tex". However, you do not use two files but include the references at the end of your thesis file. You have to follow the style given in the template file, i.e., "author, year, title,...".
  • To format the pseudocode of your algorithms you can either use "algorithmicx" together with its floating environment "algorithm" from the package "algorithms", or you can use the "listings" environment. We recommend to start with predefined commands as given by package "algpseudocode". We do not use the package "algorithmic".
  • Your header must look as follows:
    \documentclass{svmult}
    \usepackage[utf8x]{inputenc}
    \usepackage[T1]{fontenc}
    \usepackage{makeidx}
    \usepackage{graphicx}
    \usepackage{multicol}
    \usepackage[bottom]{footmisc}
    \usepackage{amsmath, amssymb, amsfonts, amscd}
    \usepackage{algpseudocode}
    \usepackage{algorithm}
    \usepackage{listings}
    \usepackage{verbatim}
    \makeindex
  • Further packages are not allowed. The page size as defined by svmult is too small for our purposes: Use the following customized svmult file to replace the file shipped with the Springer package: use this file!