Heinz Nixdorf Institut: NODES - Offering Dynamics to Emerging Structures

: Now Recruting

This project group offers the opportunity to face challenging questions in the current research area of local algorithms in dynamic networks. For such networks, we will identify locally solvable problems and investigate whether and to what extent dynamic effects can hinder or support us when solving them. Dynamic effects that can be considered here are, for example, the movement of nodes, additions of graph edges, or relabelings of nodes.

The focus of this project group lies in the development and analysis of algorithms, where analysis can be carried out both theoretically and experimentally. However, part of the first half will be the development of a simulator to visualize algorithms and the dynamics of such networks on basis of an existing peer-to-peer simulator. During this phase, the key subject is to identify issues of interest, discuss network dynamics, and get algorithmic ideas; this is to ensure that the simulator will be of use in the second half of the project group.

After this first phase, the simulator will be used to model the different problems that the project group gathered. The simulations shall help us to gain intuition for problems and eventually lead to algorithmic ideas to solve them. As a starting point, one may consider how nodes with only local knowledge can maintain different structural problems (e.g., connectivity, spanners, clusterings, or colorings). Using the simulator, even theoretical hard problems may be analyzed experimentally.

To give an example of issues to be considered, imagine a graph on which a clustering algorithm is executed. Such a clustering algorithm divides the graph's nodes into the groups of cluster centers and of clients, whereas each client belongs to exactly one cluster center. Here the cost of a clustering are given by the sum over all connection cost of a client to its corresponding cluster center. Now, the question is how to improve the given solution by local operations like reconnecting neighbors or changing a node's position? The key issue is that nodes want to improve global properties while having only local knowledge of the graph (e.g., a node only knows its current neighborhood).

What we expect from the students:

You should be interested in algorithm design and analysis and local strategies.
We need creative and self-organized students, who do not blench from challenging problems.
Basic programming skills.

What we offer:

A one-year project that fits the participants' interests.
An insight into problems that are in center of current research.
A year of fun(,) in theory. ;-)

Meeting Dates

All meetings will take place in room F1.310.

06.04.2011, 4:00pm: First meeting and assignment of seminar subjects
13.04.2011, 9:15am: Locality and Dynamics - An Introduction (Keynote, PDF)
20.04.2011, 9:15am: Online Algorithms 1 (PDF)
27.04.2011, 9:15am: Online Algorithms 2 (PDF)
04.05.2011, 9:15am: Facility Location (Powerpoint)
11.05.2011, 9:15am: The Peerfact.Sim simulator (guest lecture, Dr. Kálmán Graffi) (PDF, video)
16.05.2011, all-day: Block Seminar
18.05.2011, 9:15am: Project Management (PDF)
23-24.05.2011, all-day: Kick-off Workshop (Schloss Gehrden)

Seminar

We offer the following seminar topics:

A Near-Optimal Distributed Fully Dynamic Algorithm for Maintaining Sparse Spanners
Advised by: Peter P.
Self-Stabilizing Overlay-Networks
Advised by: Andreas
How networks become navigable as nodes move and forget
Advised by: Andreas
A log-star distributed maximal independent set algorithm for growth-bounded graphs
Advised by: Peter K.
Locality in Distributed Graph Algorithms
Advised by: Peter K.
Weak Graph Colorings
Advised by: Peter K.

You can find the starting papers for each topic here: topics.zip.

Deadline for seminar papers is Friday the 13th, 8:13am. Please prepare 10-15 pages. Send your LaTeX sources AND the corresponding final PDF file as a compressed ZIP file to Peter Kling ( peter.kling(at)uni-paderborn.de). For details see guidelines at the "Lokale Algorithmen" seminar page.

The presentation slides of all students can be downloaded here: presentations.zip.