ETH   Distributed Computing Group
Information Technology and Electrical EngineeringTIK

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


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
  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

Responsible: K. Albrecht. © Distributed Computing Group