Distributed Computing
ETH Zurich

Seminar in Distributed Computing (FS 2017)

The Seminar is now over. We thank everybody for participating.

Organization

When & Where: Tuesdays 10:15 @ ETZ G 91
First seminar: 21.02.2017
Last seminar: 30.05.2017

Coordinators: 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 (this year: 12). Therefore, we encourage you to contact Pankaj Khanchandani and the mentor corresponding to your favorite topic as early as possible (by email) to claim your presentation slot.

Presentation

Below we will have a series of suggested papers (or groups of papers) which will be assigned on a first-come-first-serve basis. You will be advised by the corresponding mentor (see list).

All presentations 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. Furthermore you may want to have a look at how to design slides, e.g. this article (or these ones).

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.

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.

Evaluation

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 questionnaire handed out to ETHZ students where they are asked to evaluate their professors.

For signed-up students

We established the following rules to ensure a high quality of the talks and hope that these will result in a good grade for you:

Schedule

Date Presenter Title Slides
21.02.2017 Jukka Suomela Local Algorithms on Grids [pdf]
28.02.2017 Reto Achermann Frontiers in Communication [pdf]
07.03.2017 Sascha Schmid Botnet [pdf]
14.03.2017 Jinank Jain Android App Taint Analysis [pdf]
21.03.2017 Oliver Richter Information Cascades on Arbitrary Topologies [pdf]
28.03.2017 Manuel Eichelberger Fast and Robust GPS Fix Using One Millisecond of Data [pdf]
04.04.2017 Silvan Clemens Egli GPS [pdf]
11.04.2017 Milan Pandurov Wireless Localization [pdf]
25.04.2017 Philipp Gamper Distributed Oblivious RAM for Secure Two-Party Computation [pdf]
02.05.2017 No Seminar
09.05.2017 Marc Gähwiler Avoiding Censorship [pdf]
16.05.2017 Noah Hollmann Android Performance [pdf]
23.05.2017 François Wirz Wifi Spying [pdf]
30.05.2017 Erfan Abdi An Improved Distributed Algorithm for Maximal Independent Set [pdf]

Papers

Title Presenter Mentor
Information Cascades on Arbitrary Topologies
Jun Wan, Yu Xia, Liang Li, and Thomas Moscibroda. ICALP 2016.
Oliver Richter Darya Melnyk
Color-coding
Noga Alon, Raphael Yuster, and Uri Zwick. STOC 1994.
Darya Melnyk
Finding a Maximum Density Subgraph
A. V. Goldberg. Technical report 1984.
Darya Melnyk
Routing under balance
Aline Ene, Gary Miller, Jakub Pachocki, Aarond Sidford. STOC 2016.
Georg Bachmeier
Distributed resource discovery in sub-logarithmic time
Bernhard Haeupler, Dahlia Malkhi. PODC 2015.
Georg Bachmeier
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai. STOC 2016.
Georg Bachmeier
Avoiding Censorship Bundle:
Website fingerprinting in onion routing based anonymization networks
Andriy Panchenko, Lukas Niessen, Andreas Zinnen and Thomas Engel. WPES 2011.
Alibi Routing
Dave Levin et al. SIGCOMM 2015.
Marc Gähwiler Thomas Ulrich
Android App Taint Analysis Bundle:
FlowDroid: precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for Android apps
Steven Arzt et al. PLDI 2014.
Android taint flow analysis for app sets
William Klieber, Lori Flynn, Amar Bhosale, Limin Jia and Lujo Bauer. SOAP 2014.
Scalable and precise taint analysis for Android
Wei Huang, Yao Dong, Ana Milanova and Julian Dolby. ISSTA 2014.
Jinank Jain Gino Brunner
Android Performance Bundle:
Mining test repositories for automatic detection of UI performance regressions in Android apps
María Gómez, Romain Rouvoy, Bram Adams and Lionel Seinturier. MSR 2016.
How developers detect and fix performance bottlenecks in Android apps
Mario Linares-Vásquez, Christopher Vendome, Qi Luo and Denys Poshyvanyk. ICSME 2015.
Analyzing GUI running fluency for Android Apps
Tian Huang, Zhenyu Zhang and Xue-Yang Zhu. MSCC 2016.
Noah Hollmann Gino Brunner
NTP Bundle:
Time’s Forgotten: Using NTP to understand Internet Latency
Ramakrishnan Durairajan, Sathiya Kumaran Mani, Joel Sommers, Paul Barford. HotNets 2015.
Practical Limitations of NTP Time Transfer
Andrew N. Novick and Michael A. Lombardi. IFCS 2015.
Usage Analysis of the NIST Internet Time Service
Jeff A. Sherman and Judah Levine. Journal of Research of the National Institute of Standards and Technology 2016.
Manuel Eichelberger
Frontiers in communication Bundle:
Passive Wi-Fi: Bringing Low Power to Wi-Fi Transmissions
Bryce Kellogg, Vamsi Talla, Shyamnath Gollakota, and Joshua R. Smith. NSDI 2016.
Ripple II: Faster Communication through Physical Vibration
Nirupam Roy and Romit Roy Choudhury. NSDI 2016.
Visible Light Communication, Networking and Sensing: A Survey, Potential and Challenges
Parth H. Pathak, Xiaotao Feng, Pengfei Hu, Prasant Mohapatra. IEEE Communications Surveys & Tutorials. 2015.
Reto Achermann Manuel Eichelberger
Wireless Localization Bundle:
Accurate indoor localization with zero start-up cost
Swarun Kumar, Stephanie Gil, Dina Katabi and Daniela Rus. MobiCom 2014.
Decimeter-Level Localization with a Single WiFi Access Point
Deepak Vasisht, Swarun Kumar and Dina Katabi. NSDI 2016.
PhyCloak: Obfuscating Sensing from Communication Signals
Yue Qiao, Ouyang Zhang, Wenjie Zhou, Kannan Srinivasan, and Anish Arora. NSDI 2016.
Milan Pandurov Michael König
Botnet Bundle:
Internet Census 2012
Carna Botnet.
Characterizing botnets-as-a-service
Wentao Chang, An Wang, Aziz Mohaisen and Songqing Chen. SIGCOMM 2014.
Sascha Schmid Michael König
Optimal Dynamic Distributed MIS
Keren Censor-Hillel, Elad Haramaty and Zohar Karnin. PODC 2016.
Pankaj Khanchandani
Parallel exhaustive search without coordination
Pierre Fraigniaud, Amos Korman, and Yoav Rodeh. STOC 2016.
Pankaj Khanchandani
Optimal deterministic routing and sorting on the congested clique
Christoph Lenzen. PODC 2013.
Pankaj Khanchandani
Mic-Bundle:
Gyrophone: Recognizing Speech from Gyroscope Signals
Yan Michalevsky, Dan Bonehy and Gabi Nakibly. USENIX Security 2014.
The Visual Microphone: Passive Recovery of Sound from Video
Abe Davis et al. SIGGRAPH 2014.
Pascal Bissig
GPS Bundle:
Energy Efficient GPS Sensing with Cloud Offloading
Jie Liu, Bodhi Priyantha, Ted Hart, Heitor S. Ramos and Antonio A.F. Loureiro. SenSys 2012.
COIN-GPS: Indoor Localization from Direct GPS Receiving
Shahriar Nirjon, Jie Liu, Gerald DeJean, Bodhi Priyantha, Yuzhe Jin and Ted Hart. MobiSys 2014.
Silvan Clemens Egli Pascal Bissig
An improved distributed algorithm for maximal independent set
Mohsen Ghaffari. SODA 2016.
Erfan Abdi Sebastian Brandt
A discrete and bounded envy-free cake cutting protocol for four agents
Haris Aziz, Simon Mackenzie. STOC 2016.
Sebastian Brandt
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Peter W. Shor. ANTS 1994.
Sebastian Brandt
WiFi Spying Bundle:
Tracking Keystrokes Using Wireless Signals
Bo Chen, Vivek Yenamandra, Kannan Srinivasan. MobiSys 2015.
See Through Walls with WiFi!
Fadel Adib and Dina Katabi. SIGCOMM 2013.
We Can Hear You with Wi-Fi!
Guanhua Wang, Yongpan Zou, Zimu Zhou, Kaishun Wu, Lionel M. Ni. MobiCom 2014.
François Wirz Simon Tanner
Distributed Oblivious RAM for Secure Two-Party Computation
Steve Lu, Rafail Ostrovsky. TCC 2013.
Philipp Gamper Yuyi Wang
Byzantine Agreement in Polynomial Expected Time
Valerie King, and Jared Saia. STOC 2013.
Yuyi Wang
Multidimensional approximate agreement in Byzantine asynchronous systems
Hammurabi Mendes and Maurice Herlihy. STOC 2013.
Yuyi Wang