Distributed Computing
ETH Zurich

Seminar in Distributed Computing (FS 2010)





When & Where: Wednesdays, 15:15-17:00 @ 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 dcg group-member (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
  24.02.2010   Yuval Emek

  03.03.2010   Alexandru Moga

  Small-World Navigability   [pdf][ppt]
  10.03.2010   Imtiaz Farhan

  Acoustic Monitoring usingWireless Sensor Networks   [pdf][ppt]
  17.03.2010   Ercan Ucan

  Donnybrook: Enabling Large- Scale, High-Speed, Peer-to- Peer Games   [pdf]
  24.03.2010   Yu Li

  Auction-based Model of BitTorrent   [pdf][ppt]
  31.03.2010   Zack Zhu

  Collaborative Human Computing   [pdf][ppt]

  No seminar due to Easter holidays.    
  14.04.2010   Mahdi Asadpour

  A DoS-Resilient Information System for Dynamic Data Management   [pdf][ppt]
  21.04.2010   Matthias Egli

  Distributed Quantum Computing   [pdf][ppt]
  28.04.2010   Alex Hugger

  Collaborative Filtering   [pdf][ppt]
  05.05.2010   Rahul Jain

  Localization in Sensor Networks   [pdf]
  12.05.2010   Irina Botan

  Software transactional memory   [pdf][ppt]
  19.05.2010   Christian Decker

  A Distributed Polylogarithmic Time Algorithm for Self-Stabilizing Skip Graphs   [pdf]
  26.05.2010   Joao Moreno

  Tsmp: Time synchronized mesh protocol   [pdf][ppt]
  02.06.2010   Andreas Boerrnert

  Synopsis diffusion for robust aggregation in sensor networks    

Suggested Papers

  title   presenter   mentor
  Incentive-Compatible Interdomain Routing [pdf]
Joan Feigenbaum, Vijay Ramachandran and Michael Schapira, EC 2006.
Interdomain Routing and Games [pdf]
Hagay Levin, Michael Schapira and Aviv Zohar, STOC 2008.
      Raphael Eidenbenz
  BitTorrent is an Auction: Analyzing and Improving BitTorrent's Incentives [pdf]
Dave Levin, Katrina LaCurts, Neil Spring, Bobby Bhattacharjee, SIGCOMM 2008 .
TrInc: Small Trusted Hardware for Large Distributed Systems [pdf]
Dave Levin, John R. Douceur, Jacob R. Lorch, Thomas Moscibroda, NSDI 2009.
  Yu Li   Raphael Eidenbenz
  The complexity of computing a Nash equilibrium [ps] [pdf]
C. Daskalakis, P. Goldberg and C. Papadimitriou, STOC 2006.
      Raphael Eidenbenz
  Distributed Quantum Computing [pdf] (pages 1-11)
Buhrman, H. and Roehrig, H. In MFCS 2009.
  Matthias Egli   Stephan Holzer
  Distributed computing with imperfect randomness [pdf]
Goldwasser, S. and Sudan, M. and Vaikuntanathan, V.. In DISC 2005.
      Stephan Holzer
  Expander Graphs and their Applications [pdf] (only most important results)
Shlomo Hoory, Nathan Linial, and Avi Wigderson. In Bulletin of the American Mathematical Society 2006.
      Stephan Holzer
  Collaborative Filtering:
GroupLens: An Open Architecture for Collaborative Filtering of Newnews [pdf]
Resnick, P. and Iacovou, N. and Suchak, M. and Bergstrom, P. and Riedl, J. In CSCW 1994.
Amazon.com recommendations: item-to-item collaborative filtering [pdf]
Linden, G. and Smith, B. and York, J. In IEEE Internet computing 2003.
  Alex Hugger   Michael Kuhn
  Small-World Navigability:
Identity and Search in Social Networks [pdf]
Watts, D.J. and Dodds, P.S. and Newman, MEJ In Science 2002.
Small-World Phenomena and the Dynamics of Information [pdf]
Kleinberg, J. In NIPS 2002.
Geographic routing in social networks [pdf]
Liben-Nowell, D. and Novak, J. and Kumar, R. and Raghavan, P. and Tomkins, A. PNAS 2005.
An Experimental Study of Search in Global Social Networks [pdf]
Dodds, P.S. and Muhamad, R. and Watts, D.J. In Science 2003.
  Alexandru Moga   Michael Kuhn
  Distributed Computing, Thinking, and Working:
SETI@ home: an experiment in public-resource computing [pdf]
Anderson, D.P. and Cobb, J. and Korpela, E. and Lebofsky, M. and Werthimer, D. In CACM 2002.
The Rise of Crowdsourcing [pdf]
Howe, J. In Wired Magazine 2006.
Recaptcha: Human-based character recognition via web security measures [pdf]
Von Ahn, L. and Maurer, B. and McMillen, C. and Abraham, D. and Blum, M. Science 2008.
  Zack Zhu   Michael Kuhn
  Weak graph colorings: distributed algorithms and applications [pdf]
Kuhn, F. In SPAA 2009.
Distributed Coloring in ~O (sqrt(log n)) Bit Rounds [pdf]
Kothapalli, K. and Onus, M. and Scheideler, C. and Schindelhauer, C. In IPDPS 2006.
      Christoph Lenzen
  Distributed Agreement in Tile Self-Assembly [pdf]
Sterling, A. In DNA 2009.
Randomized Self-Assembly for Exact Shapes [pdf]
Doty, D. In FOCS 2009.
      Christoph Lenzen
  Natural Algorithms [pdf]
Chazelle B. In SODA 2009.
      Christoph Lenzen
  Synchrony and Asynchrony in Neural Networks [pdf]
Kuhn, F. and Panagiotou, K. and Spencer, J. and Steger, A. In SODA 2010.
      Christoph Lenzen
  A Distributed Polylogarithmic Time Algorithm for Self-Stabilizing Skip Graphs [pdf]
Jacob, R. and Richa, A. and Scheideler, C. and Schmid, S. and Taeubig, H. In PODC 2009.
  Christian Decker   Remo Meier
  Donnybrook: Enabling Large-Scale, High-Speed, Peer-to-Peer Games [pdf]
Bharambe, A. and Douceur, J.R. and Lorch, J.R. and Moscibroda, T. and Pang, J. and Seshan, S. and Zhuang, X. In SIgcomm 2008.
  Ercan Ucan   Remo Meier
  A DoS-Resilient Information System for Dynamic Data Management. [pdf]
Baumgart, M. and Scheideler, C. and Schmid, S. In SPAA 2009.
  Mahdi Asadpour   Remo Meier
  Software transactional memory for dynamic-sized data structures [pdf]
Herlihy, M. and Luchangco, V. and Moir, M. and Scherer III, W.N. In PODC 2003.
A flexible framework for implementing software transactional memory [pdf]
Herlihy, M. and Luchangco, V. and Moir, M. In PODC 2003.
  Irina Botan   Johannes Schneider
  Tsmp: Time synchronized mesh protocol [pdf]
Pister, K.S.J. and Doherty, L. In DSN 2008.
  Joao Moreno   Johannes Schneider
  Synopsis diffusion for robust aggregation in sensor networks [pdf]
Nath, S. and Gibbons, P.B. and Seshan, S. and Anderson, Z., In SenSys 2004.
  Andreas Boerrnert   Johannes Schneider
  Approximation Algorithms for Hierarchical Location Problems [pdf]
C. Greg Plaxton, In ACM STOC 03.
      Jasmin Smula
  Crumbling walls: a class of practical and efficient quorum systems [pdf]
David Peleg, Avishai Wool, In Distributed Computing 1997.
      Jasmin Smula
  Approximating Minimum Max-Stretch spanning Trees on unweighted graphs [pdf]
Y. Emek, D. Peleg, In SIAM J. Comput. 2008.
      Jasmin Smula
  Radio Interferometric Geolocation [pdf]
Miklos Maroti, Peter Voelgyesi, Sebestyen Dora, Branislav Kusy, Andras Nadas, Akos Ledeczi, Gyoergy Balogh, Karoly Molnar. In SenSys 2005.
Sensor Network-Based Countersniper System [pdf]
Gyula Simon, Miklos Maroti, Akos Ledeczi, Gyoergy Balogh, Branislav Kusy, Andras Nadas, Gabor Pap, Janos Sallai, Ken Frampton. In SenSys 2004.
  Rahul Jain   Philipp Sommer
  A Macroscope in the Redwoods [pdf]
Gilman Tolle, Joseph Polastre, Robert Szewczyk, David Culler, Neil Turner, Kevin Tu, Stephen Burgess, Todd Dawson, Phil Buonadonna, David Gay, and Wei Hong. In SenSys 2005.
An Analysis of a Large Scale Habitat Monitoring Application [pdf]
Robert Szewczyk, Alan Mainwaring, Joseph Polastre, John Anderson, David Culler. In SenSys 2004.
      Philipp Sommer
  Flush: A Reliable Bulk Transport Protocol for Multihop Wireless Networks [pdf]
Sukun Kim, Rodrigo Fonseca, Prabal Dutta, Arsalan Tavakoli, David Culler, Philip Levis, Scott Shenker, and Ion Stoica. In SenSys 2007.
VoxNet: An Interactive, Rapidly-Deployable Acoustic Monitoring Platform [pdf]
Michael Allen, Lewis Girod, Ryan Newton, Samuel Madden, Daniel T. Blumstein, Deborah Estrin. IPSN 2008.
  Farhan Imtiaz   Philipp Sommer