INF346: Foundations of Distributed Systems

Part of INF346: Distributed Systems

P3/2014

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

News
Slides and exercises
Literature
Papers to present
Current paper assignment

News (last updated: 10.04.2014)

• 12.03.2014: Slides for the first three lectures and two quizes online.
• 25.03.2014: The list of papers to present is published.
• 28.03.2014: The class of Wednesday April 2 is shifted to Thursday April 3, same time, B312.
• 08.04.2014: The current paper assignment is available.
• 10.04.2014: The presentation schedule is set.
• 27.04.2014: Presentation schedule is available.
08.05.2014: Slides of the presentation are available. Please add your slides, if you don't find them there.

Slides and exercises

Literature

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

Papers to present

We may also accept a small number of related papers suggested by you.

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. Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: large-scale graph computation on just a PC. In Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation (OSDI'12). USENIX Association, Berkeley, CA, USA, 31-46. pdf
26. Reynold S. Xin, Josh Rosen, Matei Zaharia, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2013. Shark: SQL and rich analytics at scale. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13). pdf

Assignment and schedule