|
|
|
Seminar of Distributed Computing (2004/05)
When & Where: Tuesdays, 15:15-17:00 @ ETZ F 76.1 (room has changed)
Professor: Roger Wattenhofer
Coordinator: Pascal von Rickenbach
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. Please
contact the mentor of the paper which you would like to present. If
you want to present a paper falling into our domain that is not on the
list, please contact the seminar coordinator.
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. It can also be helpful to go beyond the list of your papers and look at related work.
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 |
|
2004/10/19 |
Bounded time-stamping in message-passing systems |
Vijay D'silva |
slides, report |
|
2004/10/26 |
Distributed Mail Servers |
Till Kleisli |
slides, report |
|
2004/11/02 |
Denial of Services & Counter Measurements |
Janneth Malibago |
slides, report |
|
2004/11/09 |
Anti-Spam techniques beyond Bayesian filters |
Fabio Lanfranchi |
slides, report |
|
2004/11/16 |
Random Walks on Graphs: A Survey |
Fabian Pichler |
slides, report |
|
2004/11/23 |
No presentation |
|
|
|
2004/11/30 |
Topology Control in Heterogeneous Wireless Networks |
Roman Metz |
slides, report |
|
2004/12/07 |
Location Services |
Otmar Caduff |
slides, report |
|
2004/12/14 |
Energy efficient MAC protocols for Wireless Sensor Networks |
Andri Toggenburger |
slides, report |
|
2005/12/21 |
On the Power Assignment Problem in Radio Networks |
Luzius Meisser |
slides, report |
|
2005/01/11 |
TinyOS: a System Architecture for Wireless Sensor Networks |
Jan Rellermeyer |
slides, report |
|
2005/01/18 |
Greedy Algorithms for Graph Problems |
Elia Noris |
slides, report |
|
2005/01/25 |
MST Construction in O(log log n) Communication Rounds |
Thomas Locher |
slides, report |
|
2005/02/01 |
Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks |
Nicolas Born |
slides, report |
|
2005/02/01 |
Algebraic Topology and Distributed Computing: A Primer |
Matthias Sala |
|
Suggested Papers
|
|
title |
type |
mentor |
assigned |
|
Algebraic Topology and Distributed Computing: A Primer. [pdf]
M. Herlihy, S. Rajsbaum; Computer Science Today, 1995
|
* |
Fabian Kuhn |
Matthias Sala |
|
An Asymptotic Scheme for Multigraph Edge Coloring. [ps]
P. Sanders, D. Steurer; SODA 2005 |
|
Stamatis Stefanakos |
|
|
Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks. [pdf]
C. Busch, S. Surapaneni, S. Tirthapura; SPAA 2003 |
|
Pascal von Rickenbach |
Nicolas Born |
|
Anti-Spam techniques beyond Bayesian filters
Find and compare anti spam measurements which go beyond traditional filtering like
Grey-Listing, Sender ID Framework from Microsoft, SPF, etc.
|
|
Nicolas Burri |
Fabio Lanfranchi |
|
Bounded time-stamping in message-passing systems. [ps]
M Mukund, K Narayan Kumar, M Sohoni; J. on Theoretical Computer Science, 2003 |
|
Pascal von Rickenbach |
Vijay D'silva |
|
Denial of Services & Counter Measurements (2 papers)
Internet Indirection Infrastructure. [pdf]
I.Stoica, D. Adkins, S. Zhuang, S. Shenker, S. Surana; SIGCOMM 2002
Taming IP Packet Flooding Attacks. [pdf]
Daniel Adkins, Karthik Lakshminarayanan, Adrian Perrig, Ion Stoica (UC Berkeley and CMU); HotNets 2003
|
|
Nicolas Burri |
Janneth Malibago |
|
Distributed Dominating Set Algorithms (2 papers)
An Efficient Distributed Algorithm for Constructing Small Dominating Sets. [ps]
L. Jia, R. Rajaraman, T. Suel; Distributed Computing, 2002
Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs. [pdf]
S. Rajagopalan, V. Vazirani; SIAM J. on Computing, 1998 |
|
Fabian Kuhn |
|
|
Distributed Mail Servers (2 papers)
Manageability, Availability and Performance in Porcupine: A Highly Scalable, Cluster-based Mail Service. [pdf]
Yasushi Saito, Brian N. Bershad, and Henry M. Levy; SOSP 1999
POST: A secure, resilient, cooperative messaging system [pdf]
Alan Mislove, Ansley Post, Charles Reis, Paul Willmann, Peter Druschel, Dan S. Wallach, Xavier Bonnaire, Pierre Sens, Jean-Michel Busca, Luciana Arantes-Bezerra; HotOS 2003
|
|
Keno Albrecht |
Till Kleisli |
|
Energy efficient MAC protocols for Wireless Sensor Networks (2 papers)
A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks. [pdf]
T. Herman, S. Tixeuil; ALGOSENSORS 2004
Contention-Free MAC protocols for Wireless Sensor Networks. [pdf]
C. Busch, M. Magdon-Ismail, F. Sivrikaya, B. Yener;
DISC 2004 |
|
Pascal von Rickenbach |
Andri Toggenburger |
|
Greedy Algorithms for Graph Problems (2 papers)
Models of Greedy Algorithms for Graph Problems. [pdf]
S. Davis, R. Impagliazzo; SODA 2004
Priority Algorithms for Graph Problems. [pdf]
A. Borodin, J. Boyar, K.S. Larsen;
WAOA 2004 |
|
Thomas Moscibroda |
Elia Noris |
|
Location Services (2 papers)
A Scalable Location Service for Geographic Ad Hoc Routing. [pdf]
J. Li, J. Jannotti, D.S.J. De Couto, D.R. Karger, R. Morris; MobiCom 2000
LLS: a Locality Aware Location Service for Mobile Ad Hoc Networks. [pdf]
I. Abraham, D. Dolev, D. Malkhi;
Dial M-POMC 2004 |
|
Aaron Zollinger |
Otmar Caduff |
|
MST Construction in O(log log n) Communication Rounds. [pdf]
Z. Lotker, E. Pavlov, B. Patt-Shamir, D. Peleg; SPAA 2003
|
|
Fabian Kuhn |
Thomas Locher |
|
Multi-User Editors (2 papers)
Papers to be announced
|
|
Keno Albrecht |
|
|
Network Synchronization with Polylogarithmic Overhead. [ps]
B. Awerbuch, D. Peleg; FOCS 1990
|
|
Fabian Kuhn |
|
|
New 3/4-Approximation Algorithm for MAX SAT. [ps]
M.X. Goemans, D.P. Williamson; SIAM Journal on Discrete Mathematics, 1994 |
|
Mirjam Tolksdorf |
|
|
On the distributed complexity of computing maximal matchings. [ps]
M. Hanckowiak, M. Karoniski, A. Panconesi; SODA 1998 |
|
Fabian Kuhn |
|
|
On the Power Assignment Problem in Radio Networks. [pdf]
A. Clementi, P. Penna, R. Silvestri; Mobile Networks and Applications, 2004 |
|
Thomas Moscibroda |
Luzius Meisser |
|
Random Walks on Graphs: A Survey. [pdf]
L. Lovász; Combinatorics (2) 1993
|
* |
Mirjam Tolksdorf |
Fabian Pichler |
|
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems [ps]
A. Blum, G. Konjevod, R.Ravi, S. Vempala, STOC 1998 |
* |
Thomas Moscibroda |
|
|
The Power of Small Coalitions in Graphs. [ps]
J-C. Bermond, J. Bond, D. Peleg, S. Perennes; Discrete Applied Mathematics, 2003 |
|
Fabian Kuhn |
|
|
TinyOS: a System Architecture for Wireless Sensor Networks
www.tinyos.net
|
|
Pascal von Rickenbach |
Jan Rellermeyer |
|
Topology Control in Heterogeneous Wireless Networks (2 papers)
Topology Control in Heterogeneous Wireless Networks: Problems and Solutions. [pdf]
N. Li, J.C. Hou; INFOCOM 2004
Localized Topology Control for Heterogeneous Wireless Ad-hoc Networks.
X.-Y. Li, W.-Z. Song, Y. Wang;
MASS 2004 |
|
Aaron Zollinger |
Roman Metz |
|