|
|
|
Seminar of Distributed Computing (2003/04)
When & Where: Tuesdays, 15:15-17: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 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
(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 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 |
|