Distributed Computing
ETH Zurich

Seminar in Distributed Computing (HS 2008)



In the upcomming fall semester we will try something new for our "Seminar in Distributed Computing" – an ETH Zurich edition! The seminar will cover work by ETH professors in the area of distributed computing. A variety of topics, such as systems, networking, wearable, mobile, security, algorithms, data management, programming, both practice and theory, will be adressed. The only common denominator will be "distributed".

Each professor selected a list of papers co-authored by him/her. Some papers come in groups and cover a common topic, others can be presented on their own. The authors will be invited to attend the students' talks, and (if the schedule meets their availability) the attendees will be able to ask questions and discuss the presented material with them.

The idea is to introduce some of the best reasearch produced at ETH to the students and enable more vivid discussions, which will hopefully be enriched by the proximity of the authors.



When & Where: Wednesdays, 15:15-17:00 @ ETZ G 91



As a seminar participant, you are invited to


In order to obtain credit points for the seminar, you have to make a presentation. Since only one presentation per week of the semester can take place, there is a limited number of slots (topics) that can be presented (usually 13 or 14). Therefore, we encourage you to contact us as early as possible (by email) to claim your presentation slot.



Below we have a series of suggested papers (or groups of papers) which will be assigned on a first-come-first-serve basis.

Your presentation should cover the motivation for the problem as well as some technical parts of the paper(s) in detail. Assume that the other participants know nothing about the subject. You are not supposed to present the whole paper(s), but just the aspects that were most intriguing to you. We encourage you to deviate from the logical structure of the paper(s) 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.

We further expect the presentation to motivate a lively discussion. Your presentation should not be a mere transfer of knowledge, but inspire an animated debate among the seminar participants.

Your slides and talk should be in English. The presentation should last 45 minutes plus about 15 minutes of discussion.



We encourage discussion during and after a presentation as a main objective of this seminar. The extent to which your own presentation instigates discussion as well as your own participation in the other presentations will influence your grade in this course.



Following the technical part of the presentation and discussion, we will briefly evaluate the quality of the presentation as a group. Below are the criteria according to which we judge a good presentation. They were inspired by the common questionaire handed out to ETHZ students where they are asked to evaluate their professors.


For signed-up students:


Please contact your mentor early enough before your presentation date, in time to make the corrections and/or improvements he/she suggests. We expect an electronic copy of your slides by the presentation date.

Schedule of Presentations

  date topic/professor   presenter mentor material
  2008/09/17 Improving Traffic Flow by Local Methods
  Prof. Sandor Fekete (Guest speaker)    
  2008/09/24 Distributed Databases
Prof. Donald Kossmann
  Olga Goussevskaia slides [pdf]
  2008/10/01 Aurora/Borealis
Prof. Nesime Tatbul
  Olga Goussevskaia slides [pdf]
  2008/10/08 Distributed Systems
Prof. Gustavo Alonso
  Nicolas Burri slides [pdf]
  2008/10/15 Consensus
Prof. Peter Widmayer
  Johannes Schneider slides [pdf]
  2008/10/22 Routing in Road Networks
  Robert Geisberger, Google Zurich (Guest speaker)    
  2008/10/29 Declarative Routing
Prof. Timothy Roscoe
  Christoph Lenzen slides [pdf]
  2008/11/05 Internet Routing
Prof. Bernhard Plattner
  Philipp Sommer slides [pdf]
  2008/11/12 Smart-Its
Prof. Friedemann Mattern
  Michael Kuhn slides [pdf]
  2008/11/19 Security in Sensor Networks
Prof. Srdjan Capkun
  Roland Flury slides [pdf]
  2008/11/26 Causality, consistency, and logical time in distributed computations
Prof. Friedemann Mattern
  Thomas Locher slides [pdf]
  2008/12/03 Mobile Computing and Context
Prof. Gerhard Troester
  Remo Meier slides [pdf]
  2008/12/10 Catching elephants with mice: sparse sampling for monitoring sensor networks
Prof. Emo Welzl
  Yvonne-Anne Pignolet slides [pdf]
  2008/12/17 Model Driven Security
Prof. David Basin
  Raphael Eidenbenz slides [pdf]
summary [pdf]

Suggested Papers

  title   professor  
  Distributed Databases (3 papers)
Building a Database on S3 [pdf]
Matthias Brantner, Daniela Florescu, David Graf, Donald Kossmann, Tim Kraska, In SIGMOD 2008.
Dynamo: Amazon’s Highly Available Key-value Store [pdf]
Amazon.com, In SOSP 2007.
The Chubby lock service for loosely-coupled distributed systems [pdf]
Mike Burrows, Google Inc., In USENIX OSDI 2006.
  Donald Kossmann  
  The State of the Art in Distributed Query Processing [pdf] Donald Kossmann, In ACM Computing 2000.   Donald Kossmann  
  Catching elephants with mice: sparse sampling for monitoring sensor networks [pdf]
S. Gandhi, S. Suri, E. Welzl, In 5th International ACM Conference on Embedded Networked Sensor Systems (SenSys), 2007.
  Emo Welzl  
  Pseudo-Telepathie (3 papers)
The cost of exactly simulating quantum entanglement with classical communication [pdf]
Gilles Brassard, Richard Cleve, Alain Tapp, In Physical Review Letters 1999.
Towards Characterizing the Non-Locality of Entangled Quantum States [pdf]
Renato Renner, Stefan Wolf, IEEE International Symposium on Information Theory, 2003.
Quantum Pseudo-Telepathy and the Kochen-Specker Theorem [pdf]
Renato Renner, Stefan Wolf, IEEE International Symposium on Information Theory, 2004.
  Stefan Wolf  
  Distributed transmit diversity in relay networks [pdf]
Cemal Akçaba, Patrick Kuppinger, and Helmut Bölcskei, In IEEE Information Theory Workshop (ITW), 2007.
  Helmut Bölcskei  
  Crystallization in large wireless networks [pdf]
Veniamin I. Morgenshtern, Helmut Bölcskei, In IEEE Transactions on Information Theory, 2007.
  Helmut Bölcskei  
  Model Driven Security: from UML Models to Access Control Infrastructures [pdf]
David Basin, Juergen Doser, Torsten Lodderstedt, In ACM Transactions on Software Engineering and Methodology, 2006.
  David Basin  
  OFMC: A Symbolic Model-Checker for Security Protocols [pdf]
David Basin, Sebastian Moedersheim, Luca Vigano, In International Journal of Information Security, 2005.
  David Basin  
  Causality, consistency, and logical time in distributed computations (4 papers)
Synchronous, Asynchronous, and Causally Ordered Communication [pdf]
Bernadette Charron-Bost and Friedemann Mattern and Gerard Tel, In Distributed Computing, 1996.
Virtual Time and Global States of Distributed Systems [pdf]
Friedemann Mattern, In Workshop on Parallel and Distributed Algorithms, 1989.
On the Relativistic Structure of Logical Time in Distributed Systems [pdf]
Friedemann Mattern, In Datation et Controle des Executions Reparties, 1992.
Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail [pdf]
Friedemann Mattern, Reinhard Schwarz, In Distributed Computing, 1994.
  Friedemann Mattern  
  Secure Multiparty Computation and Broadcast (2 papers)
Player Simulation and General Adversary Structures in Perfect Multiparty Computation [pdf]
Martin Hirt and Ueli Maurer, In Journal of Cryptology, Springer-Verlag, vol. 13, no. 1, pp. 31-60, Apr 2000, Extended abstract in Proc. 16th of ACM PODC'97.
From Partial Consistency to Global Broadcast [pdf]
Matthias Fitzi and Ueli Maurer, In Proceedings of the 32th Annual ACM Symposium on Theory of Computing (STOC '00), ACM Press, pp. 494-503, May 2000.
  Ueli Maurer  
  Secure Multiparty Computation (3 papers)
Player Simulation and General Adversary Structures in Perfect Multiparty Computation [pdf]
Martin Hirt and Ueli Maurer, In Journal of Cryptology, 2000, Extended abstract in Proc. 16th of ACM PODC'97.
Trading Correctness for Privacy in Unconditional Multi-Party Computation [pdf]
Matthias Fitzi, Martin Hirt, and Ueli Maurer, In Advances in Cryptology - CRYPTO'98.
MPC vs. SFE: Perfect Security in a Unified Corruption Model [pdf]
Zuzana Beerliova-Trubiniova, Matthias Fitzi, Martin Hirt, Ueli Maurer, and Vassilis Zikas, In Theory of Cryptography - TCC 2008.
  Ueli Maurer  
  Balls & Bins (2 papers)
Balanced allocation: the heavily loaded case [pdf]
Simplified witness tree arguments [pdf]
Thomas Schickinger and Angelika Steger, In SOFSEM 2000.
  Angelika Steger  
  Aurora/Borealis (3 papers)
Aurora: a new model and architecture for data stream management [pdf]
Daniel J. Abadi, Don Carney, Ugur Cetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Michael Stonebraker, Nesime Tatbul, Stan Zdonik, In the VLDB Journal, 2003.
The Design of the Borealis Stream Processing Engine [pdf]
Daniel J. Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur Cetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag S. Maskey, Alexander Rasin, Esther Ryvkina, Nesime Tatbul, Ying Xing, and Stan Zdonik, In Proceedings of the 2005 CIDR Conference.
Staying FIT: Efficient Load Shedding Techniques for Distributed Stream Processing [pdf]
Nesime Tatbul, Ugur Cetintemel, Stan Zdonik, In VLDB 2007.
  Nesime Tatbul  
  (This presentation should include further exploration of the field and cover the most relevant related work.)
Smart-Its Friends: A Technique for Users to Easily Establish Connections between Smart Artefacts [pdf]
Lars Erik Holmquist, Friedemann Mattern, Bernt Schiele, Petteri Alahuhta, Michael Beigl and Hans-W. Gellersen, In Proceedings of the 3rd International Conference on Ubiquitous Computing, 2001.
  Friedemann Mattern  
  Distributed Systems (3 papers)
Ganymed: Scalable Replication for Transactional Web Applications [pdf]
Christian Plattner, Gustavo Alonso, In Proc. of the 5th ACM/IFIP/USENIX International Middleware Conference, 2004.
DBFarm: A Scalable Cluster for Multiple Databases [pdf]
Christian Plattner, Gustavo Alonso, M. Tamer Özsu, In Proc. of the 7th ACM/IFIP/USENIX International Middleware Conference, 2006.
Extending DBMSs with Satellite Databases [pdf]
Christian Plattner, Gustavo Alonso, M. Tamer Özsu, In VLDB Journal, 2008.
  Gustavo Alonso  
  Signal Processing (3 papers)
Cooperative Diversity by Relay Phase Rotations in Block Fading Environments [pdf]
Ingmar Hammerström, Marc Kuhn, Armin Wittneben, In Proc. of IEEE International Workshop on Signal Processing Advances in Wireless Communications, SPAWC 2004.
Distributed Antenna Systems and Linear Relaying for Gigabit MIMO Wireless [pdf]
Armin Wittneben, Boris Rankov, In Proc. of IEEE Vehicular Technology Conference, VTC Fall 2004.
A Cluster-based Multiuser Cooperative Networks [pdf]
Celal Esli, Armin Wittneben, In IEEE Globecom, 2007.
  Armin Wittneben  
  Consensus (2 papers)
Harmful dogmas in fault tolerant distributed computing [pdf]
Bernadette Charron-Bost, Andre Schiper, In ACM SIGACT News, 2007.
Agreement in synchronous networks with ubiquitous faults [pdf]
Nicola Santoroa, Peter Widmayer, In Theoretical Computer Science, 2007.
  Peter Widmayer  
  Security in Sensor Networks (2 papers)
Secure Time Synchronization in Sensor Networks [pdf]
Saurabh Ganeriwal, Christina Poepper, Srdjan Capkun, Mani B. Srivastava, In ACM Transactions on Information and System Security, 2008.
Jamming-resistant Key Establishment using Uncoordinated Frequency Hopping [pdf]
Mario Strasser, Christina Poepper, Srdjan Capkun, Mario Cagalj, In IEEE Symposium on Security and Privacy, 2008.
  Srdjan Capkun  
  Declarative Routing (2 papers)
Declarative networking: language, execution and optimization [pdf]
Boon Thau Loo, Tyson Condie, Minos Garofalakis, David E. Gay, Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe, and Ion Stoica, In ACM SIGMOD Proceedings, 2006.
Implementing Declarative Overlays [pdf]
Boon Thau Loo, Tyson Condie, Joseph M. Hellerstein, Petros Maniatis, Timothy Roscoe, and Ion Stoica, In ACM SOSP Proceedings, 2005.
  Roscoe Timothy  
  Internet Routing (3 papers)
Scalable High Speed IP Routing Table Lookups [pdf]
Marcel Waldvogel, George Varghese, Jon Turner and Bernhard Plattner, In ACM SIGCOMM Proceedings, 1997.
Router plugins: a software architecture for next generation routers [pdf]
Dan Decasper, Zubin Dittia, Guru Parulkar,and Bernhard Plattner, In ACM SIGCOMM Proceedings, 1998.
The VersaKey Framework: Versatile Group Key Management [pdf]
Marcel Waldvogel, Germano Caronni, Dan Sun, Nathalie Weiler, and Bernhard Plattner, In JSAC: Special Issue on Middleware, 1999.
  Bernhard Plattner  
  Mobile Computing and Context (3 papers)
Activity Recognition of Assembly Tasks Using Body-Worn Microphones and Accelerometers [pdf]
Jamie A. Ward, Paul Lukowicz, Gerhard Troester, and Thad E. Starner, In IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2006.
Recognition of dietary activity events using on-body sensors [pdf]
Oliver Amft, Gerhard Troester, In Artificial Intelligence in Medicine, 2008.
It’s in Your Eyes - Towards Context-Awareness and Mobile HCI Using Wearable EOG Goggles [pdf]
Andreas Bulling, Daniel Roggen, and Gerhard Troester, In Proceedings of Tenth International Conference on Ubiquitous Computing (Ubicomp), 2008.
  Gerhard Troester  
  Real-Time Embedded Systems (2 papers)
System Architecture Evaluation Using Modular Performance Analysis - A Case Study [pdf]
Ernesto Wandeler, Lothar Thiele, Marcel Verhoef, Paul Lieverse, In Software Tools for Technology Transfer, 2006.
Influence of Different Abstractions on the Performance Analysis of Distributed Hard Real-Time Systems [pdf]
Simon Perathoner, Ernesto Wandeler, Lothar Thiele, Arne Hamann, Simon Schliecker, Rafik Henia, Razvan Racu, Rolf Ernst, Michael González Harbour, In Design Automation for Embedded Systems, 2008.
  Lothar Thiele