


Seminar of Distributed Computing (2003/04)
When & Where: Tuesdays, 15:1517:00 @ HRS F 5
Professor: Roger Wattenhofer
Coordinator: Regina Bischoff
Organization
As a seminar participant, you are invited to
 present a research paper, and lead the discussion;
 turn in a 12 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 firstcomefirstserve 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 signedup 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 
PeertoPeer 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 
PeertoPeer 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 NameIndependence 
Henri DuboisFerriè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 NameIndependence. [pdf]
M. Arias, L. J. Cowen, K. A. Laing, R. Rajaraman, O. Taka; SPAA 2003


Regina Bischoff 
Henri DuboisFerriè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 InverseAckermann 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. PattShamir, 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 


PeertoPeer 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 LargeScale PeertoPeer Systems. [pdf]
A. Rowstron, P. Druschel; Middleware 2001


Keno Albrecht 
Nicole Hatt 

PeertoPeer File Systems (3 papers)
Chord: A Scalable Peertopeer Lookup Service for Internet Applications. [pdf]
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, H. Balakrishnan; SIGCOMM 2001
WideArea Cooperative Storage with CFS. [pdf]
F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica; SOSP 2001
Ivy: A Read/Write PeertoPeer 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
(extract)


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 MissionCritical Computing [pdf]
K. Birman, R. van Renesse, W. Vogels; DARPA DISCEX2001


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 
