Sem­in­ar Ad­vanced Dis­trib­uted Al­gorithms

Lecturer: Prof. Dr. Christian Scheideler

 

Module Information:

  • 5 ECTS

First Meeting and Topic Assignment:

  • Thursday, October 10, at 6 pm in F2.211 (Fürstenallee)

Submission of almost final versions of the reports: January 31

Submission of final versions of reports: February 21

These deadlines are strict, i.e., no further extensions will be granted. The seminar itself is planned to take place as a block seminar in March 5-6. All participants are required to be present at the block seminar.

Grading:

Participants are expected to prepare a detailed report (~20 pages) and a presentation of their topic. Both need to be passed in order to pass the course, and both count 50% towards the final grade. Please be aware that reports are checked for plagiarism, so use your own words as much as possible and cite anything you take from other sources!

Topics:

It is highly recommended that participants of the seminar have a strong algorithms and theory background. Also, they should have a background in the theory of distributed systems. Here, it is highly recommended that they either attended the course "Advanced Distributed Algoirthms and Data Structures" or a PG offered by the research group of Christian Scheideler. Please have a look at the papers below to make up your mind which one you would like to work on:

  • Christian Scheideler, Alexander Setzer: On the Complexity of Local Graph Transformations. ICALP 2019: 150:1-150:14.

  • John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Fabian Kuhn, Jason Li: Distributed Computation in Node-Capacitated Networks. SPAA 2019: 69-79.

  • Kristian Hinnenthal, Christian Scheideler, Martijn Struijs: Fast Distributed Algorithms for LP-Type Problems of Bounded Dimension. DISC 2019: 393-394.

  • Daniel Jung, Christina Kolb, Christian Scheideler, Jannik Sundermeier: Competitive Routing in Hybrid Communication Networks. ALGOSENSORS 2018: 15-31.

  • Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, Thim Strothmann: Forming Tile Shapes with Simple Robots. DNA 2018: 122-138.

  • Michael Feldmann, Christian Scheideler, Alexander Setzer:
    Skueue: A Scalable and Sequentially Consistent Distributed Queue. IPDPS 2018: 1040-1049.

  • Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler:
    Shape Recognition by a Finite Automaton Robot. MFCS 2018: 52:1-52:15.

  • Michael Feldmann, Christina Kolb, Christian Scheideler: Self-stabilizing Overlays for High-Dimensional Monotonic Searchability. SSS 2018: 16-31.

  • Christian Scheideler, Alexander Setzer: Relays: A New Approach for the Finite Departure Problem in Overlay Networks. SSS 2018: 239-253.

  • Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Christian Sohler: Distributed Monitoring of Network Properties: The Power of Hybrid Networks. ICALP 2017: 137:1-137:15.

  • Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann:
    Universal Shape Formation for Programmable Matter. SPAA 2016: 289-299.

  • Maximilian Drees, Robert Gmyr, Christian Scheideler: Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration. SPAA 2016: 417-427.

  • Martina Eikel, Christian Scheideler: IRIS: A Robust Information System Against Insider DoS Attacks. TOPC 2(3): 18:1-18:33 (2015) .

  • Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig: SKIP+: A Self-Stabilizing Skip Graph. J. ACM 61(6): 36:1-36:26 (2014) .

  • Chen Avin, Bernhard Haeupler, Zvi Lotker, Christian Scheideler, Stefan Schmid:
    Locally Self-Adjusting Tree Networks. IPDPS 2013: 395-406.

  • Sebastian Kniesburges, Andreas Koutsopoulos, Christian Scheideler: CONE-DHT: A Distributed Self-Stabilizing Algorithm for a Heterogeneous Storage System. DISC 2013: 537-549.

  • Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler:
    Stabilizing consensus with the power of two choices. SPAA 2011: 149-158.

  • Baruch Awerbuch, Christian Scheideler: Towards a Scalable and Robust DHT. Theory Comput. Syst. 45(2): 234-260 (2009).

  • Baruch Awerbuch, Andréa W. Richa, Christian Scheideler: A jamming-resistant MAC protocol for single-hop wireless networks. PODC 2008: 45-54.

  • Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler:
    The Effect of Faults on Network Expansion. Theory Comput. Syst. 39(6): 903-928 (2006).

  • Kishore Kothapalli, Christian Scheideler, Melih Onus, Christian Schindelhauer: Distributed coloring in O/spl tilde/(/spl radic/(log n)) bit rounds. IPDPS 2006.

Further information: