Distributed Computing
ETH Zurich

Seminar in Distributed Computing (FS 2014)





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 Klaus-Tycho Förster 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 (or these ones).

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
  19.02.2014   Barbara Keller

  Convergence in (Social) Influence Networks    [pdf]
  26.02.2014   Roni Häcki

  Romantic Bundle    [pdf]
  05.03.2014   Jochen Zehnder

  Lossless Migrations of Link-State IGPs    [pdf]
  12.03.2014   Lei Zhong

  Locally Stable Marriage with Strict Preferences    [pdf]
  19.03.2014   Elias Yousefi Amin Abadi

  Bitcoin Bundle    [pdf]
  26.03.2014   Jian Zhang

  Low-rank matrix completion using alternating minimization    [pdf]
  02.04.2014   Jeremia Bär

  Internet background radiation    [pdf]
  09.04.2014   Alessandro Dovis

  Simple, Fast and Deterministic Gossip and Rumor Spreading    [pdf]
  16.04.2014   Adrian Leuenberger

  On the complexity of universal leader election    [pdf]
  30.04.2014   Damian Scherrer

  Airwave Bundle    [pdf]
  07.05.2014   James Guthrie

  Sorting Bundle    [pdf]
  14.05.2014   Matteo Panzacchi

  Backscatter Bundle    [pdf]
  21.05.2014   Jait Dixit

  Performance-effective and low-complexity task scheduling for heterogeneous computing    [pdf]
  28.05.2014   Andrea Lattuada

  Distributed Maximal Matching: Greedy is Optimal    [pdf]

Suggested Papers

  title   presenter   mentor
  The GraphSLAM Algorithm with Applications to Large-Scale Mapping of Urban Structures [pdf]
Sebastian Thrun and Michael Montemerlo. In Robotics Research 2006.
      Pascal Bissig
  Backscatter Bundle (2 papers):
Full Duplex Backscatter [pdf]
Dinesh Bharadia and Kiran Raj Joshi and Sachin Katti. In Hotnets 2013.
Ambient Backscatter: Wireless Communication Out of Thin Air [pdf]
Vincent Liu, Aaron Parks, Vamsi Talla, Shyamnath Gollakota, David Wetherall, Joshua R. Smith. In SIGCOMM 2013.
  Matteo Panzacchi   Pascal Bissig
  Airwave Bundle (2 papers):
Whole-Home Gesture Recognition Using Wireless Signals [pdf]
Qifan Pu, Sidhant Gupta, Shyamnath Gollakota, and Shwetak Patel. In MobiCom 2013.
AirWave: Non-Contact Haptic Feedback Using Air Vortex Rings [pdf]
Sidhant Gupta, Dan Morris, Shwetak N. Patel, and Desney Tan. In UbiComp 2013.
  Damian Scherrer   Pascal Bissig
  On the Hardness of Being Truthful [pdf]
Christos Papadimitriou and Michael Schapira. In FOCS 2008.
      Philipp Brandes
  Locally Stable Marriage with Strict Preferences [pdf]
Martin Hoefer and Lisa Wagner. In ICALP 2013.
  Lei Zhong   Philipp Brandes
  Romantic Bundle (2 papers):
Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook [pdf]
Lars Backstrom and Jon Kleinberg. In CSCW 2014.
Mining Smartphone Data to Classify Life-Facets of Social Relationships [pdf]
Jun-Ki Min, Jason Wiese, Jason I. Hong, John Zimmerman. In CSCW 2013.
  Roni Häcki   Philipp Brandes
  Bitcoin Bundle (2 papers):
An Analysis of Anonymity in the Bitcoin System [pdf]
Fergal Reid and Martin Harrigan. In PASSAT 2011.
Quantitative Analysis of the Full Bitcoin Transaction Graph [pdf]
Dorit Ron and Adi Shamir. In FC 2013.
  Elias Yousefi Amin Abadi   Christian Decker
  Simple, Fast and Deterministic Gossip and Rumor Spreading [pdf]
Bernhard Haeupler. In SODA 2013.
  Alessandro Dovis   Klaus-Tycho Förster
  The Urinal Problem [pdf]
Evangelos Kranakis, Danny Krizanc. In FUN 2010.
Note: In this talk you will also have to present results from some of the work referenced in the paper.
      Klaus-Tycho Förster
  Lossless Migrations of Link-State IGPs [pdf]
Vanbever, L.; Vissicchio, S. ; Pelsser, C. ; Francois, P. ; Bonaventure, O. In Transactions on Networking 2012.
  Jochen Zehnder   Klaus-Tycho Förster
  Bundle (3 papers)(Internet background radiation):
Extracting Benefit from Harm: Using Malware Pollution to Analyze the Impact of Political and Geophysical Events on the Internet [pdf]
Alberto Dainotti and Roman Ammann and Emile Aben. In SIGCOMM 2012.
Characteristics of Internet Background Radiation [pdf]
Ruoming Pang, Vinod Yegneswaran, Paul Barford, Vern Paxson, and Larry Peterson. In SIGCOMM 2004.
Internet Background Radiation Revisited [pdf]
Eric Wustrow, Manish Karir, Michael Bailey, Farnam Jahanian, and Geoff Houston. In SIGCOMM 2010.
  Jeremia Bär   Michael König
  Sorting Bundle (2 papers)(Sorting, fast and... slow?):
One or more approaches from the sort benchmark competition [html]

Optionally in addition: Pessimal Algorithms and Simplexity Analysis [pdf]
Andrei Broder and Jorge Stolfi. In ACM SIGACT News 1984.
  James Guthrie   Michael König
  Simple Deterministic Algorithms for Fully Dynamic Maximal Matching [pdf]
Neiman, Solomon. In STOC 2013.
      Tobias Langner
  Low-rank matrix completion using alternating minimization [pdf]
Jain, Netrapalli, Sanghavi. In STOC 2013.
  Jian Zhang   Tobias Langner
  Bundle (3 papers):
MoodScope: Building a Mood Sensor from Smartphone Usage Patterns [pdf]
LiKamWa, Liu, Lane, Zhong. In MobiSys 2013.
Can Your Smartphone Infer Your Mood [pdf]
LiKamWa, Liu, Lane, Zhong. In PhoneSense 2011.
Towards Unobtrusive Emotion Recognition for Affective Social Communication [pdf]
Choi, Lee, Park. In CCNC 2012.
      Tobias Langner
  What can be decided locally without identifiers? [pdf]
Pierre Fraigniaud, Mika Göös, Amos Korman, Jukka Suomela. In PODC 2013.
      Jochen Seidel
  On the complexity of universal leader election [pdf]
Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, Amitabh Trehan. In PODC 2013.
  Adrian Leuenberger   Jochen Seidel
  Performance-effective and low-complexity task scheduling for heterogeneous computing [pdf]
Topcuoglu, H.; Hariri, S.; Min-You Wu. In Transactions on Parallel and Distributed Systems 2002.
Note: In this talk you will also have to present theoretical background on task scheduling not covered in the paper.
  Jait Dixit   Jochen Seidel
  Distributed Maximal Matching: Greedy is Optimal [pdf]
Juho Hirvonen and Jukka Suomela. In PODC 2012.
  Andrea Lattuada   Jara Uitto
  Rendezvous of Two Robots with Constant Memory [pdf]
Paola Flocchini, Nicola Santoro, Giovanni Viglietta and Masafumi Yamashita. In SIROCCO 2013.
      Jara Uitto
  RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis [html]
Daniel Genkin, Adi Shamir and Eran Tromer. In IACR 2013.
      Jara Uitto