Seminar in Distributed Computing (FS 2012)
Summary
Organization
When & Where: Wednesdays 15:15 @ ETZ G 91
Coordinators:
As a seminar participant, you are invited to
- present one, two or three research paper(s) assigned to your presentation date, and lead the discussion;
- attend all talks of the seminar and actively participate in the discussions.
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.
Presentation
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.
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.
Evaluation
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.
- Motivated Talk
The speaker was motivated and kept the audience interested throughout the presentation.
R1: Der Dozent / die Dozentin bot einen engagierten Unterricht. - Clearly Explained
The speaker made the material clear and comprehensible.
R2: Der Dozent / die Dozentin vermochte den Stoff verständlich und anschaulich zu erklären. - Knowledge Transfer
The (awake and participating) audience learned something.
S2: Der Wissenstransfer fand statt im Zusammenhang mit der Vorlesung. - Difficulty
The presentation was (too) difficult, easy, or just right to follow.
S4: Die Vorlesung war [zu] schwierig/einfach, gerade richtig. - Prior Knowledge
The speaker did not assume inappropriate prior knowledge.
S6: Die Vorlesung baute auf bekannten Vorkenntnissen auf. - Structure
The presentation had a clear concept and discernable structure.
S8: Der Dozent / die Dozentin präsentierte seinen/ihren Unterricht strukturiert (Aufbau, Transparenz, roter Faden). - Encouraged Participation
The speaker actively encouraged participation and successfully led the discussion.
S9: Der Dozent / die Dozentin ermutigte aktive Mitarbeit und ging gut auf Fragen und Bemerkungen ein. - Media
The speaker made good use of the available presentation tools such as overhead, whiteboard, etc.
S10: Der Dozent / die Dozentin setzte die verwendeten Hilfsmittel, wie Wandtafel, Overhead und Demonstrationen, gut und hilfreich ein.
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:
- At least 5 weeks before your talk: first meeting with your mentor (you need to read the assigned literature before this meeting).
- At least 3 weeks before your talk: meet your mentor to discuss the structure of your talk.
- At least 1 week before your talk: give the talk in front of your mentor who will provide feedback.
- At the presentation date we expect an electronic copy of your slides.
Schedule
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] | ||||
23.05.2012 | [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 |