INF346: Distributed Systems

Algorithms

P3/2015

Prof. Petr Kuznetsov, Office hours: C213-2, appointment by email
INFRES, Telecom ParisTech

News
Slides and exercises
Literature
Papers to present
Paper assignment

News

Slides and exercises

Date Class Exercises
24.02.2015 Introduction, theory and practice of distributed systems Quiz 1
27.02.2015 Correctness: Safety and Liveness Quiz 2
02-04.03.2015 Basics of read-write shared memory Quiz 3
06.03.2015 Asserting atomicity Quiz 4
06-13.03.2015 Consensus and universal construction Quiz 5
11.03.2015 Exercise session 1
Bakery correctness proof (Lynch)
13.03.2015 Linked lists: fine-grained, optimistic and lazy synchronization Quiz 6
23.03.2015 Hands-on session on linked lists Synchrobench: git, paper
25-27.03.2015 Transactional memory Quiz 7
03.04.2015 Paxos State Machine Replication Quiz 8

Literature

Papers to present

  1. Leslie Lamport, Robert E. Shostak, Marshall C. Pease: The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4(3): 382-401 (1982) pdf
  2. Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565 (1978) pdf
  3. Nir Shavit and Dan Touitou. Software transactional memory. PODC 1995. pdf
  4. C. A. Ellis and S. J. Gibbs. 1989. Concurrency control in groupware systems. SIGMOD Rec. 18, 2 (June 1989), 399-407. pdf
  5. Maurice Herlihy, Victor Luchangco, Mark Moir: Obstruction-Free Synchronization: Double-Ended Queues as an Example. ICDCS 2003: 522-529 pdf
  6. Nancy Lynch and Seth Gilbert, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, Volume 33 Issue 2 (2002), pp. 51-59. pdf
  7. Miguel Castro, Barbara Liskov: Practical Byzantine-Fault-Tolerant System. In OSDI 1999. pdf
  8. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. SIGCOMM 2001 pdf
  9. Maymounkov, P., Mazieres, D. (2002). Kademlia: A peer-to-peer information system based on the xor metric. In Peer-to-Peer Systems (pp. 53-65). pdf
  10. Byers, J., Considine, J., & Mitzenmacher, M. (2003). Simple load balancing for distributed hash tables. In Peer-to-peer systems II (pp. 80-87). Springer Berlin Heidelberg. pdf
  11. Dave Dice, Ori Shalev, and Nir Shavit. 2006. Transactional locking II. In Proceedings of the 20th international conference on Distributed Computing (DISC'06) pdf
  12. Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. 2007. Paxos made live: an engineering perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (PODC '07). pdf
  13. Ghemawat, S. Gobioff, H. and Leung, S.-T. The Google File System. Proceedings of the 19th ACM Symposium on Operating Systems Principles. pp 29--43. Bolton Landing, NY, USA. 2003. pdf
  14. Borthakur, Dhruba. The Hadoop Distributed File System: Architecture and Design. 2007, The Apache Software Foundation. pdf
  15. Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM 51, 1 (January 2008) pdf
  16. G. Decandia et al. (2007). "Dynamo: Amazon's Highly Available Key-value Store". Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles - SOSP '07. pdf
  17. Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. 2010. ZooKeeper: wait-free coordination for internet-scale systems. In Proceedings of the 2010 USENIX conference on USENIX annual technical conference (USENIX ATC'10). pdf
  18. A. J. Feldman et al. 2010. SPORC: group collaboration using untrusted cloud resources. In Proceedings of the 9th USENIX conference on Operating systems design and implementation (OSDI'10). pdf
  19. Valiant, L. G. (2011). A bridging model for multi-core computing. Journal of Computer and System Sciences, 77(1), 154-166 pdf
  20. James C. Corbett et al. Spanner: Google's Globally Distributed Database. ACM Trans. Comput. Syst. 31, 3, Article 8 (August 2013) pdf
  21. Brian F. Cooper et al. 2008. PNUTS: Yahoo!'s hosted data serving platform. Proc. VLDB Endow. 1, 2 (August 2008), 1277-1288. pdf
  22. Tim Kraska, Gene Pang, Michael J. Franklin, Samuel Madden, and Alan Fekete. 2013. MDCC: multi-data center consistency. In Proceedings of the 8th ACM European Conference on Computer Systems (EuroSys '13). ACM, New York, NY, USA, 113-126. pdf
  23. Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno Preguica, and Rodrigo Rodrigues. 2012. Making geo-replicated systems fast as possible, consistent when necessary. In Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation (OSDI'12). USENIX Association, Berkeley, CA, USA, 265-278. pdf
  24. Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2011. Don't settle for eventual: scalable causal consistency for wide-area storage with COPS. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (SOSP '11). ACM, New York, NY, USA, 401-416. pdf
  25. Tudor David, Rachid Guerraoui, Vasileios Trigonakis. Everything You Always Wanted to Know About Synchronization but Were Afraid to Ask, SOSP 2013 pdf

Assignment and schedule

Choose the paper to present using this form.

You may check the paper assignments here.

The exam schedule is here.