


Seminar of Distributed Computing (2004/05)
When & Where: Tuesdays, 15:1517: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 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. 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 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 

2004/10/19 
Bounded timestamping in messagepassing 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 
AntiSpam 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 

AntiSpam techniques beyond Bayesian filters
Find and compare anti spam measurements which go beyond traditional filtering like
GreyListing, Sender ID Framework from Microsoft, SPF, etc.


Nicolas Burri 
Fabio Lanfranchi 

Bounded timestamping in messagepassing 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
PrimalDual 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, Clusterbased 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, JeanMichel Busca, Luciana ArantesBezerra; 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
ContentionFree MAC protocols for Wireless Sensor Networks. [pdf]
C. Busch, M. MagdonIsmail, 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 MPOMC 2004 

Aaron Zollinger 
Otmar Caduff 

MST Construction in O(log log n) Communication Rounds. [pdf]
Z. Lotker, E. Pavlov, B. PattShamir, D. Peleg; SPAA 2003


Fabian Kuhn 
Thomas Locher 

MultiUser 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/4Approximation 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 

SemiDefinite Relaxations for Minimum Bandwidth and other VertexOrdering Problems [ps]
A. Blum, G. Konjevod, R.Ravi, S. Vempala, STOC 1998 
* 
Thomas Moscibroda 


The Power of Small Coalitions in Graphs. [ps]
JC. 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 Adhoc Networks.
X.Y. Li, W.Z. Song, Y. Wang;
MASS 2004 

Aaron Zollinger 
Roman Metz 
