Course Plans‎ > ‎

Distributed Systems

Target: Graduate students, and senior undergraduate students

Pre-requisites: Undergraduate Computer Networking. 

Text book: 
  • Christian Cachin, Rachid Guerraoui, and Luis Rodrigues. Introduction to Reliable and Secure Distributed Programming 
  • Research Papers
Assumptions
  • 2 lectures per week
  • 75 minutes per lecture
  • 14 weeks per semester minus spring/fall break => 13 weeks and 26 lectures
Lesson Plan:

  1. Basic concepts and Introduction (2 lectures)
    • Distributed systems definitions
    • Communication abstractions and channels
    • Sockets
    • Remote Procedure Calls, Apache Thrift
    • Architecture -- Client-server and Web Services, peer-to-peer (Introduction only)
  2. Time (2 lectures) 
    • Global state and state transitions
    • Physical time and clock synchronization (Google TrueTime)
    • Logical time -- Lamport clocks, Vector clocks
  3. Group Communication (2 lectures) 
    • Reliable broadcast
    • Guarantees
    • Ordered broadcasts -- FIFO, Causal 
    • "Uniform" guarantees
  4. Leader Election (1 Lecture)
    • Ring
    • Mesh
  5. Consensus and atomic broadcast (2 lectures)
    • Definitions, guarantees and Applications
    • Paxos
    • Atomic broadcast based on consensus and sequencers
  6. Distributed transactions (4 lectures)
    • Definitions, guarantees (ACID) and applications
    • 2PC and 3PC
    • Sinfonia and mini-transactions [Research paper]
    • Synchronized time and Google Spanner [Research paper]
  7. Consistent hashing and Key-value Stores (4 lectures)
    • Consistent hashing, redundant consistent hashing [Research paper]
    • Distributed hash tables -- Chord, Pastry [Research paper]
    • Key-value stores -- Amazon Dynamo [Research paper]
  8. Eventual consistency (1 lecture)  [Research paper]
  9. Distributed Mutual Exclusion (2 Lectures)  [Research paper]
    • Token, ring-based algorithms
    • Lamport's shared priority queues
    • Lock services -- Chubby and Zookeeper
  10. Map reduce, HDFS and data analytics (2 Lectures)  [Research paper]
  11. Messaging (2 Lectures)  [Research paper]
    • Message queues
    • Publish/Subscribe -- topic and content/based
Comments