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

• Please make your choice of a paper to present by March 27
• Bidding for papers to present is open.
• The exercise session of March 6 is shifted to March 11 . On March 11, we are going to have two lectures instead.
• The lecture of March 2 will exceptionally begin at 9h00

Slides and exercises

Literature

• Lecture Notes: Robust Concurrent Computing
• M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008, ebook
• N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers. 1996
• H. Attiya, J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Wiley. 2004
• R. Guerraoui, M. Kapalka. Principles of Transactional Memory. Morgan and Claypool Publishers, 2010

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.