# Seminar in Distributed Computing (FS 2011)

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 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.

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.

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.

Schedule

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 |
tba |

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 |