Efficient Algorithms (Seminar)

Seminar:
Robert Elsässer, Nikolaus Augsten
Language:
English
Semester:
Wintersemester 2015/2016
PlusOnline:
Seminar

Introduction

The seminar works as follows:

  1. you pick one of the papers listed below,
  2. you present the paper in a 45 min talk (plus 15 minutes questions),
  3. you write a seminar report (8–10 pages) where you summarize the core results of the paper.

For the paper choice you will be sent a link. Please choose two papers within Tu Oct 13, 4pm. We will assign you a paper by Fr Oct 16.

Schedule

The schedule will be finalized during the seminar on Oct 23.

Date Speaker Topic
Oct 9 - kick-off meeting
Oct 23 Ábel Elekes Compatible Euler-tours
- finalize schedule
Nov 20 Hasic Dynamo: amazon's highly available key-value store
Nov 27 Kaaser Distributed Voting with Two Choices
Bilke Graph Models and Community Detection in Social Networks
Dec 4 Mann An Empirical Evaluation of Set Similarity Join Techniques
Langford Distributed Computing on Core-Periphery Networks: Axiom-Based Design
Dec 11 Miller Fast and Exact Majority in Population Protocols
Auer An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol
Dec 18 Lugstein Networks, Crowds, and Markets - Chapter 21: Epidemics
Tesfaye A Survey of Shortest Path and Range Query Algorithms
Jan 08 Büchele The Google File System
Friedrich MapReduce: Simplified Data Processing on Large Clusters
Jan 22 Gruschina Bigtable: A Distributed Storage System for Structured Data
Mann An Empirical Evaluation of Set Similarity Join Techniques
Jan 29 Fuchs Pregel: A System for Large-Scale Graph Processing
Kocher Spanner: Google's Globally-Distributed Database

Papers

  1. Distributed Computing on Core-Periphery Networks: Axiom-Based Design,
    (pages 399-407, Sec. 4 to be omitted), 2014
  2. Fast and Exact Majority in Population Protocols, (pages 1-8, Sec. 5 to be omitted), 2015
  3. Local Information in Influence Networks, (proofs from Sec. 4.4-4.6 to be omitted), 2015
  4. Privacy-Conscious Information Diffusion in Social Networks, (Sec. 2.1 and proof of Theorem 7 to be omitted), 2015
  5. An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol, 2004
  6. Networks, Crowds, and Markets - Chapter 21: Epidemics,
    (important: sections/pages 21.1-21.4/645-658 and 21.8 A/672-679), 2010
  7. The Google File System, 2003
  8. MapReduce: Simplified Data Processing on Large Clusters, 2004
  9. Bigtable: A Distributed Storage System for Structured Data, 2006
  10. Dynamo: amazon's highly available key-value store, 2007
  11. Large-scale Incremental Processing Using Distributed Transactions and Notifications, 2010
  12. Pregel: A System for Large-Scale Graph Processing, 2010
  13. Spanner: Google's Globally-Distributed Database, 2012