ETH   Distributed Computing Group
Computer Science
Pervasive Computing

Seminar of Distributed Computing (2003/04)

When & Where: Tuesdays, 15:15-17:00 @ HRS F 5

Professor: Roger Wattenhofer

Coordinator: Regina Bischoff


As a seminar participant, you are invited to

  • present a research paper, and lead the discussion;
  • turn in a 1-2 page report which critically evaluates the achievement of the presented paper (flaw in the model, not exciting when compared to related work, etc.) and/or give a (small, vague) idea how to improve the paper, and/or propose what else might be studied;
  • attend the other talks of the seminar and actively participate in the discussions.

Below we have a series of suggested papers which have been assigned on a first-come-first-serve basis. There are no more time slots available for a presentation in this semester.

Some papers are harder to understand than others. Some papers come in groups, where you need to read and compare all the papers in the group. Tough papers are marked with a star, or even two stars. (Hard papers are sometimes easier to present because not as much detail will be expected in the presentation.)

Your presentation should cover the motivation for the problem as well as some technical parts of the paper in detail. Assume that the other participants know nothing about the subject. You are not supposed to present the whole paper, but just the aspects of the paper that were most intriguing to you. We encourage you to deviate from the logical structure of the paper and strive for the most lucid presentation of the topic.

Your slides and talk should be in English. The presentation should last 45 minutes plus about 15 minutes of discussion.

For signed-up students: Please contact your mentor at the latest 2 weeks before your presentation date. You should have a thorough understanding of the paper 1 week prior to your talk. We expect an electronic copy of your slides and the report no later than 2 weeks after the presentation date.

Schedule of Presentations

  date title presenter material
  2003/10/28 Keynote Talk: P2P Distributed Data: Storage and Access Marcel Waldvogel, IBM Research webpage
  2003/10/21 Reliable Distributed System Approaches Manuel Graber slides, report
  2003/11/11 Peer-to-Peer File Systems Hannes Geissbühler slides, report
  2003/11/18 The Web as a Graph Michelle Ackermann slides, report
  2003/11/25 What Can Be Computed Locally? Michael Kaufmann slides, report
  2003/12/02 Peer-to-Peer Systems Nicole Hatt slides, report
  2003/12/09 Concurrent Online Tracking of Mobile Users Claudio Munari slides, report
  2003/12/16 Decomposing Graphs into Regions of Small Diameter Josias Thoeny slides, report
  2004/01/06 Discrete Mobile Centers André Bayer slides, report
  2004/01/13 Internet Topology Andrea Weisskopf slides, report
  2004/01/20 Compact Routing with Name-Independence Henri Dubois-Ferrière slides only
  2004/02/03 Labeling Schemes for Flow and Connectivity Julio Perez slides, report

The Seminar is now over. Lots of thanks to everybody who participated!

Suggested Papers

  title type mentor assigned
  Algebraic Topology and Distributed Computing: A Primer. [pdf]
M. Herlihy, S. Rajsbaum, Computer Science Today, 1995
 * Regina Bischoff  
  Approximating the Domatic Number. [ps]
U. Feige, M. M. Halldórsson, G. Kortsarz; SIAM J. on Computing, 2002
 ** Fabian Kuhn  
  Compact Routing with Name-Independence. [pdf]
M. Arias, L. J. Cowen, K. A. Laing, R. Rajaraman, O. Taka; SPAA 2003
  Regina Bischoff Henri Dubois-Ferrière
  Concurrent Online Tracking of Mobile Users. [pdf]
B. Awerbuch, D. Peleg; SIGCOMM 1991
  Fabian Kuhn Claudio Munari
  Decomposing Graphs into Regions of Small Diameter. [pdf]
N. Linial, M. Saks; SODA 1991
  Fabian Kuhn Josias Thoeny
  Discrete Mobile Centers. [pdf]
J. Gao, L. J. Guibas, J. Hershberger, L. Zhang, A. Zhu; SCG 2001
  Aaron Zollinger André Bayer
  Internet Topology (2 papers)
Internet topology: Connectivity of IP Graphs. [pdf]
A. Broido, K. Claffy; ITCom 2001
Traceroute and BGP AS Path Incongruities. [pdf]
Y. Hyun, A. Broido, K. Claffy; 2003
  Ruedi Arnold Andrea Weisskopf
  An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree Verification Problem. [pdf]
S. Pettie; FOCS 2002
 * Mirjam Tolksdorf  
  Labeling Schemes for Flow and Connectivity. [pdf]
M. Katz, N. Katz, A. Korman, D. Peleg; SODA 2002
  Aaron Zollinger Julio Perez
  Locality in Distributed Graph Algorithms. [hardcopy only]
N. Linial, SIAM J. Comput. 1992
 * Mirjam Tolksdorf  
  Minimum Restricted Diameter Spanning Trees. [pdf]
R. Hassin, A. Levin; APPROX 2002
  Regina Bischoff  
  MST Construction in O(log log n) Communication Rounds. [pdf]
Z. Lotker, E. Pavlov, B. Patt-Shamir, D. Peleg; SPAA 2003
  Fabian Kuhn Raoul Dessovic
  Network Synchronization with Polylogarithmic Overhead. [ps]
B. Awerbuch, D. Peleg; FOCS 1990
  Fabian Kuhn  
  The Online Set Cover Problem. [pdf]
N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor; STOC 2003
  Fabian Kuhn  
  Peer-to-Peer Systems (2 papers)
Viceroy: A Scalable and Dynamic Emulation of the Butterfly. [pdf]
D. Malkhi, M. Naor, D. Ratajczak; PODC 2002
Pastry: Scalable, Decentralized Object Location and Routing for Large-Scale Peer-to-Peer Systems. [pdf]
A. Rowstron, P. Druschel; Middleware 2001
  Keno Albrecht Nicole Hatt
  Peer-to-Peer File Systems (3 papers)
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. [pdf]
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, H. Balakrishnan; SIGCOMM 2001
Wide-Area Cooperative Storage with CFS. [pdf]
F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica; SOSP 2001
Ivy: A Read/Write Peer-to-Peer File System. [pdf]
A. Muthitacharoen, R. Morris, T. Gil, B. Chen; OSDI 2002
  Keno Albrecht Hannes Geissbühler
  Random Walks on Graphs: A Survey. [pdf]
L. Lovász; Combinatorics (2) 1993
 * Regina Bischoff Gregor Bättig
  Randomized Consensus Algorithms (2 papers)
Randomized Protocols for Asynchronous Consensus. [pdf]
J. Aspnes; PODC 2002
Randomized Consensus in O(N log^2 N) Operations per Processor. [pdf]
J. Aspnes, O. Waarts; FOCS 1992
  Ruedi Arnold  
  Randomized Rumor Spreading. [pdf]
R. Karp, C. Schindelhauer, S. Shenker, B. Vöcking; FOCS 2000
  Ruedi Arnold  
  Reliable Distributed System Approaches (2 papers)
The Process Group Approach to Reliable Distributed Computing. [pdf]
K. Birman; Communications of the ACM, 1993
Spinglass: Secure and Scalable Communication Tools for Mission-Critical Computing [pdf]
K. Birman, R. van Renesse, W. Vogels; DARPA DISCEX-2001
  Ruedi Arnold Manuel Graber
  Spatial Gossip and Resource Location Protocols. [ps]
D. Kempe, J. Kleinberg, A. Demers; STOC 2001
  Ruedi Arnold  
  The Web as a Graph: Measurements, Models and Methods. [ps]
J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins; COCOON 1999
  Mirjam Tolksdorf Michelle Ackermann
  What Can Be Computed Locally? [pdf]
M. Naor, L. Stockmeyer, STOC 93
  Regina Bischoff Michael Kaufmann

Responsible: K. Albrecht & R. Arnold. © Distributed Computing Group