Distributed Computing
ETH Zurich

Seminar in Distributed Computing (FS 2012)





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 or Jara Uitto 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. Furthermore you may want to have a look at how to design slides, e.g. this article.

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:



  date   presenter   title   slides
  22.02.2012   Tobias Langner

  Stability vs. Cost of Matchings    [pdf]
  29.02.2012   Xiang Gao

  Paths, Trees and Flowers    [pdf]
  7.03.2012   Christoph Niemz

  Click Trajectories and Judo vs. Spam    [pdf]
  14.03.2012   Wang Han

  Maximizing the Spread of Influence through a Social Network    [pdf]
  21.03.2012   Denitsa Dobreva

  Category-based routing in social networks: membership dimension and the small-world phenomenon    [pdf]
  28.03.2012   Gianin Basler

  SignalGuru: leveraging mobile phones for collaborative traffic signal schedule advisory    [pdf]
  4.04.2012   Tanja Werthmüller

  Scalable rational secret sharing    [pdf]
  18.04.2012   Nico Eigenmann

  Distributed (Delta + 1)-Coloring in Linear (in Delta) Time    [pdf]
  25.04.2012   Christoph Burkhalter

  The Round Complexity of Distributed Sorting    [pdf]
  2.05.2012   Lukas Humbel

  Optimal strategies for maintaining a chain of relays between an explorer and a base camp    [pdf]
  9.05.2012   Fei Guo

  Electronic Cash    [pdf]
  16.05.2012   David Stolz

  Recommendation Networks    [pdf]

  30.05.2012   Catalin Halmaghi

  Bounding the locality of distributed routing algorithms    [pdf]

Suggested Papers

  title   presenter   mentor
  Maximizing the Spread of Influence through a Social Network [pdf]
David Kempe, Jon Kleinberg, Éva Tardos. In SIGKDD 2003.
  Wang Han   Philipp Brandes
  Optimal strategies for maintaining a chain of relays between an explorer and a base camp [pdf]
Jarosław Kutyłowski, Friedhelm Meyer auf der Heide. In Theoretical Computer Science (2009)
  Lukas Humbel   Philipp Brandes
  On the Hardness of Being Truthful [pdf]
Christos Papadimitriou, Michael Schapira and Yaron Singer. In FOCS 2008.
      Philipp Brandes
  Bounding the locality of distributed routing algorithms [pdf]
Prosenjit Bose, Paz Carmi and Stephane Durocher. In PODC 2009.
  Catalin Halmaghi   Klaus-Tycho Förster
  Scalable rational secret sharing [pdf]
Varsha Dani, Mahnush Movahedi, Yamel Rodriguez and Jared Saia. In PODC 2011.
  Tanja Werthmüller   Klaus-Tycho Förster
  Category-based routing in social networks: membership dimension and the small-world phenomenon [pdf]
D. Eppstein, M. T. Goodrich, M. Löffler, D. Strash, and L. Trott. Workshop on Graph Algorithms and Applications, Zürich, Switzerland, July 2011.
  Denitsa Dobreva   Klaus-Tycho Förster
  Efficient Scheduling of Data-Harvesting Trees [pdf]
Bastian Katz, Steffen Mecke and Dorothea Wagner. In ALGOSENSORS 2008.
      Jochen Seidel
  SignalGuru: leveraging mobile phones for collaborative traffic signal schedule advisory [pdf]
Emmanouil Koukoumidis, Li-Shiuan Peh, and Margaret Rose Martonosi. In MobiSys 2011.
  Gianin Basler   Jochen Seidel
  Fault-Tolerant Compact Routing Schemes for General Graphs. [pdf]
Shiri Chechik. In ICALP 2011.
      Jochen Seidel
  A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model [pdf]
Thomas Kesselheim.
      Stephan Holzer
  The Round Complexity of Distributed Sorting [pdf]
Boaz Patt-Shamir and Marat Teplitsky. In PODC 2011.
  Christoph Burkhalter   Stephan Holzer
  Optimal-Time Adaptive Strong Renaming, with Applications to Counting [pdf]
Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, Morteza Zadimoghaddam. In PODC 2011.
      Stephan Holzer
  Locally Checkable Proofs [pdf]
Mika Göös and Jukka Suomela. In PODC 2011.
      Jara Uitto
  Distributed (Δ + 1)-Coloring in Linear (in Δ) Time [pdf]
Leonid Barenboim and Michael Elkin. In STOC 2009.
  Nico Eigenmann   Jara Uitto
  A simple local 3-approximation algorithm for vertex cover [pdf]
Valentin Polishchuk, Jukka Suomela. Information Processing Letters 2009.
      Jara Uitto
  Natural Algorithms [pdf]
Bernard Chazelle. In SODA 2009.
      Tobias Langner
  Paths, Trees and Flowers [pdf]
Jack Edmonds. In CJM 1965.
  Xiang Gao   Tobias Langner
  Analyzing Network Coding Gossip Made Easy [pdf]
Bernhard Haeupler. In STOC 2011.
      Tobias Langner
  Bundle (2 papers):
An Analysis of Anonymity in the Bitcoin System [pdf]
Fergal Reid and Martin Harrigan. 2011.
Bitcoin: A Peer-to-Peer Electronic Cash System [pdf]
Satoshi Nakamoto. In Network (2009).
  Fei Guo   Samuel Welten
  Bundle (2 papers):
Click Trajectories: End-to-End Analysis of the Spam Value Chain [pdf]
Kirill Levchenko, Andreas Pitsillidis, Neha Chachra, Brandon Enright, Márk Félegyházi, Chris Grier, Tristan Halvorson, Chris Kanich, Christian Kreibich, He Liu, Damon McCoy, Nicholas Weaver, Vern Paxson, Geoffrey M. Voelker, Stefan Savage. In S&P 2011.
Botnet Judo: Fighting Spam with Itself [pdf]
Andreas Pitsillidis, Kirill Levchenko, Christian Kreibich, Chris Kanich, Nicholas Weaver, Chris Kanich, Geoffrey M. Voelker, Vern Paxson, Nicholas Weaver, Stefan Savage. In Engineering 2010.
  Christoph Niemz   Samuel Welten
  Data Dimensionality Estimation Methods: A survey [pdf]
Francesco Camastra. In Pattern Recognition 2003.
      Samuel Welten
  Extended Schemes for Visual Cryptography [pdf]
Giuseppe Ateniese, Carlo Blundo, Alfredo De Santis and Douglas R. Stinson. 1996.
      Barbara Keller
  Self-stabilizing Cuts in Synchronous Networks [pdf]
Thomas Sauerwald and Dirk Sudholt. In SIROCCO 2008.
      Barbara Keller
  Bundle (2 papers):
Patterns of Influence in a Recommendation Network [pdf]
Jure Leskovec, Ajit Singh and Jon Kleinberg. In PAKDD 2006.
On the Bursty Evolution of Blogspace [pdf]
Ravi Kumar, Jasmine Novak, Prabhakar Raghavan and Andrew Tomkins. In WWW 2003.
  David Stolz   Barbara Keller