Seminar in Distributed Computing (FS 2010)
Summary
Organization
When & Where: Wednesdays, 15:15-17:00 @ ETZ G 91
Coordinators:
As a seminar participant, you are invited to
- present two or three research papers 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 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.
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.
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 | ||||
---|---|---|---|---|---|---|---|
24.02.2010 | Yuval Emek |
tba | |||||
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] | ||||
07.04.2010 | |
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 |