Distributed Computing
ETH Zurich

Seminar in Distributed Computing (FS 2011)





When & Where: Wednesdays 15:15 @ ETZ G 91



As a seminar participant, you are invited to


In order to obtain credit points for the seminar, you have to make a presentation. Since only one presentation per week of the semester can take place, there is a limited number of slots (topics) that can be presented (usually 13 or 14). Therefore, we encourage you to contact Stephan Holzer and the mentor corresponding to your favorite topic as early as possible (by email) to claim your presentation slot.



Below we have a series of suggested papers (or groups of papers) which will be assigned on a first-come-first-serve basis. You will be advised by the corresponding mentor (see list).

All presentations should cover the motivation for the problem as well as some technical parts of the paper(s) in detail. Assume that the other participants know nothing about the subject. You are not supposed to present the whole paper(s), but just the aspects that were most intriguing to you. We encourage you to deviate from the logical structure of the paper(s) and strive for the most lucid presentation of the topic. It can also be helpful to go beyond the list of your papers and look at related work.

We further expect the presentation to motivate a lively discussion. Your presentation should not be a mere transfer of knowledge, but inspire an animated debate among the seminar participants.

Your slides and talk should be in English. The presentation should last 45 minutes plus about 15 minutes of discussion.



We encourage discussion during and after a presentation as a main objective of this seminar. The extent to which your own presentation instigates discussion as well as your own participation in the other presentations will influence your grade in this course.



Following the technical part of the presentation and discussion, we will briefly evaluate the quality of the presentation as a group. Below are the criteria according to which we judge a good presentation. They were inspired by the common questionnaire handed out to ETHZ students where they are asked to evaluate their professors.


For signed-up students


We established the following rules to ensure a high quality of the talks and hope that these will result in a good grade for you:


Furthermore we recommend you to read the following links helping you to give a good talk:
How to prepare slides
How to prepare and give a talk (in German) - targets mathematicians but applies to us as well except that we will use projector-slides.


  date   presenter   title   slides
  23.02.2011   Jan Schlegel

  Network Creation Games   [pdf]
  02.03.2011   Christof Baumann

  A Local O(n^2) Gathering Algorithm   [pdf]
  09.03.2011   Abouzar Nouri

  Earthquake Shakes Twitter Users: Real-time Event Detection by Social Sensors   [pdf][odp]
  16.03.2011   Ioana Giurgiu

  Software Transactional Memory   [pdf]
  23.03.2011   Simon Gerber

  Surviving Wi-Fi Interference in Low Power ZigBee Networks   [pdf]
  30.03.2011   Manuel Stocker

  In Defense of Wireless Carrier Sense   [pdf][ppt]
  06.04.2011   Phillip Sommer

  SpiderBat: Augmenting Wireless Sensor Networks with Distance and Angle Information   [pdf][pptx]
      Raphael Eidenbenz

  Hidden Communication in P2P Networks: Steganographic Handshake and Broadcast   [pdf][pptx]
  13.04.2011   Richard Huber

  Tell Me Who I Am: An Interactive Recommendation System   [pdf][odp]
  20.04.2011   Markus Voelker

  Scheduling, Localization, Boundary-Detection in Wireless Networks   [pdf]
  04.05.2011   Fabian Kuhn

  Coordinated Consensus in Dynamic Networks    
  11.05.2011   Michael Koenig

  Cheap Labor Can Be Expensive   [pdf][ppt]
  18.05.2011   Daniel Thomas

  Distributed computing with imperfect randomness   [pdf]
  01.06.2011   Ulrik Brandes


Suggested Papers

  title   presenter   mentor
  The Complexity of Computing a Nash Equilibrium [pdf]
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou. In STOC 2006.
      Raphael Eidenbenz
  Cheap Labor Can Be Expensive [pdf]
Ning Chen, Anna R. Karlin. In SODA 2007.
  Michael Koenig   Raphael Eidenbenz
  Contribution Games in Social Networks [pdf]
Elliot Anshelevich, Martin Hoefer. In Arxiv / ESA 2010.
      Raphael Eidenbenz
  A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model [pdf]
Thomas Kesselheim. In Arxiv / SODA 2011.
      Stephan Holzer
  Distributed computing with imperfect randomness [pdf]
Shafi Goldwasser, Madhu Sudan, Vinod Vaikuntanathan. In DISC 2005.
  Daniel Thomas   Stephan Holzer
  Expander Graphs and their Applications [pdf] (only chapter 1; 9 pages)
Shlomo Hoory, Nathan Linial, Avi Wigderson. In Bulletin of the American Mathematical Society 2006.
      Stephan Holzer
  Noncryptographic Selection Protocols [pdf]
Uriel Feige. In FOCS 1999.
      Barbara Keller
  Tell Me Who I Am: An Interactive Recommendation System [pdf]
Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-Shamir. In TCS 2009
  Richard Huber   Barbara Keller
  The Lovasz Local Lemma and Satisfiability [pdf]
Heidi Gebauer, Robin A. Moser, Dominik Scheder, Emo Welzl. In Festchrift Mehlhorn 2009.
      Barbara Keller
  Natural Algorithms [pdf]
Bernard Chazelle. In SODA 2009
      Tobias Langner
  A Local O(n^2) Gathering Algorithm [pdf]
Bastian Degener, Barbara Kempkes, Friedhelm Meyer auf der Heide. In SPAA 2010.
  Christof Baumann   Tobias Langner
  Partial Information Spreading with Application to Distributed Maximum Coverage [pdf]
Keren Censor Hillel, Hadas Shachnai. PODC 2010.
      Tobias Langner
  Distributed Contention Resolution in Wireless Networks [pdf]
Thomas Kesselheim, Berthold Voecking. In PODC 2010
      Remo Meier
  Computational Complexity and Information Asymmetry in Financial Products [pdf]
Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge. In ICS 2010.
      Remo Meier
  Non-Uniform ACC Circuit Lower Bounds [pdf]
Ryan Williams. In.
      Remo Meier
  Improved Distributed Approximate Matching [pdf]
Zvi Lotker, Boaz Patt-Shamir, Seth Pettie. In SPAA 2008.
      Johannes Schneider
  Bundle (2 paper):
Transactional Locking II [pdf]
Dave Dice, Ori Shalev, Nir Shavit. In DISC 2006.
Time-Based Software Transactional Memory [pdf]
Pascal Felber, Christof Fetzer, Patrick Marlier, Torvald Riegel. In TPDS 2008.
  Ioana Giurgiu   Johannes Schneider
  Sublogarithmic Distributed MIS Algorithm for Sparse Graphs using Nash-Williams Decomposition [pdf]
Leonid Barenboim, Michael Elkin. In PODC 2008.
      Johannes Schneider
  A tight bound on approximating arbitrary metrics by tree metrics [pdf]
Jittat Fakcharoenphol, Satish Rao, Kunal Talwa. In JCSS 2004.
      Jasmin Smula
  Approximation Algorithms for Hierarchical Location [pdf]
C. Greg Plaxton. In STOC 2003.
      Jasmin Smula
  Efficient Distributed Random Walks with Applications [pdf]
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali. In PODC 2010.
      Jasmin Smula
  Surviving Wi-Fi Interference in Low Power ZigBee Networks [pdf]
Chieh-Jan Mike Liang, Nissanka B. Priyantha, Jie Liu, Andreas Terzis In SenSys 2010
  Simon Gerber   Philipp Sommer
  In Defense of Wireless Carrier Sense [pdf]
Micah Z. Brodsky, Robert T. Morris In SIGCOMM 2009
  Manuel Stocker   Philipp Sommer
  Data Dimensionality Estimation Methods: A survey [pdf]
Francesco Camastra. In PR 2003.
      Samuel Welten
  Bundle (3 paper):
Automatic Construction of Travel Itineraries using Social Breadcrumbs [pdf]
Munmun De Choudhury, Moran Feldman, Sihem Amer-Yahia, Nadav Golbandi, Ronny Lempel, Cong Yu. In HT 2010.
Automatic Mashup Generation from Multiple-camera Concert Recordings [pdf]
Prarthana Shrestha, Peter H.N. de With, Hans Weda, Mauro Barbieri, Emile H.L. Aarts. In MM 2010.
Earthquake Shakes Twitter Users: Real-time Event Detection by Social Sensors [pdf]
Takeshi Sakaki, Makoto Okazaki, Yutaka Matsuo. In WWW 2010.
  Abouzar Nouri   Samuel Welten