You are here: Home › … › Previous Events › 2011 › Distributed Algorithms

Distributed Algorithms

Seminar Distributed Algorithms

joint seminar of Dr. Alexander Souza and Prof. Christian Schindelhauer

News

  • 14.10.2011 Web-pages online
  • 25.10. 2011, 10 am: Preliminary meeting. Topics will be distributed. Students, who do not show up on this first meeting will loose their place.

Contents

The seminar deals with current research topics in the field of distributed algorithms.

Organisation

Please register online for the seminar. If you cannot register, you can come to the first meeting on 25.10.2011 to check whether places are available in the  The attendance to the all seminar meetings is compulsory.

Schedule

  • Preliminary Meeting 
    • Tuesday, 25.10.2011, 10:00 - 12:00 c.t., Building 101 - 01-016
  • Kickoff-presentation
  • 1-day block seminar 21.02.2012, 09:00 - 16:00,  Building 101 - 01-016

Forum

Please use the forum for general questions about the lecture. Maybe your question and the answer is probably interesting to other students. Please feel free to start new threads and interesting discussion.

Examination

The grade consists of

  • a short kickoff presentation (15 minutes),
  • a written report (5-12 pages), due 6.2.2012!!
  • an abstract for 2 other topics of the seminar (around 300 words) , due 20.02.2012
    • prepared questions for these topics to be asked in the in the corresponding presentation
  • a final presentation at the end of the semester (30 minutes + 15 minutes questions)


The slides for the final presentation have to be submitted as PDF or PPT file.

The written report has to be drawed up in LaTeX (http://en.wikipedia.org/wiki/LaTeX) and BibTeX (http://en.wikipedia.org/wiki/Bibtex).  The compiled PDF-File plus the LaTeX and BibTeX source files have to be submitted. The written report should have 5 to 12 pages in the default paper class (\documentclass[a4paper]{article}) with additional space for pictures, and table of contents, and bibliography.

Additional information for creating scientific seminar paper with Latex are here. The LaTex file can be used as style sheet as well.

Plagiarism in the presentation and/or written report results in failing the seminar. Furthermore, we report such behavior to the examination office!

The language of the written report and the 2 abstracts can be either german or english. English is the preferred language here. The presentation has to be in English.

 

Topics

  1. Anatomy of a P2P Content Distribution system with Network Coding, Christos Gkantsidis, John Miller, Pablo Rodriguez, IPTPS 2006.
  2. Mobile agent rendezvous in a synchronous torus, Evangelos Kranakis, Danny Krizanc, Euripides Markou, LATIN 2006
  3. Unbounded Contention Resolution in Multiple-Access Channels, Antonio Fernández Anta, Miguel A. Mosteiro, Jorge Ramón Munõz, PODC 2011
  4. Towards Secure and Scalable Computation in Peer-to-Peer Networks, King, Saia, Sanwalani, Vee, FOCS 2006
  5. Byzantizing Paxos by Refinement, Leslie Lamport, Technical Report, Microsoft, 2010
  6. A Randomized Algorithm for Label Assignment in Dynamic Networks, Walraed-Sullivan, Mysore, Marzullo, Vahdat, DISC 2011
  7. Black Hole Search with Finite Automata Scattered in a Synchronous Torus, Chalopin, Das, Labourel, Markou, DISC 2011
  8. On-line Navigation in a Room, Bar-Eli, Berman, Fiat, Yan, Journal of Algorithms archive Volume 17 Issue 3, Nov. 1994 
  9. Trading Bit, Message, and Time Complexity of Distributed Algorithms, Schneider, Wattenhofer, DISC 2011
  10. Distributed (∆ + 1)-Coloring in Linear (in ∆) Time, Barenboim, Elkin, STOC 2009
  11. A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach - Hochbaum, Shmoys - SIAM J. Computing, Vol. 17. No. 3, 1988
  12. Approximation Algorithms for Scheduling Unrelated Parallel Machines - Lenstra, Shmoys, Tardos - Mathematical Programming, Vol. 46, 1990
  13. Minimizing Average Completion Time in the Presence of Release Dates - Phillips, Stein, Wein - Mathematical Programming, Vol. 82, 1998
  14. Scheduling Tasks in Networks - Phillips, Stein, Wein - SIAM Journal on Discrete Mathematics, Vol. 10, Nr. 4, 1997
  15. On-Line Load Balancing for Related Machines - Berman, Charikar, Karpinski - Lecture Notes in Computer Science, Vol. 1272, 1997
  16. Exact and Approximate Algorithms for Scheduling Nonidentical Processors - Horowitz, Sahni - Journal of the ACM, Vol. 23, No. 2, 1976