ECE419 — Distributed Systems

Course focuses on the design, implementation, and theory of distributed systems. Follows ECE344 — Operating Systems. Lab work is done in Go.

Quick links:

• Course page
• Suggested textbooks are:
  • Distributed Systems, by Maarten van Steen and Andrew S. Tanenbaum
  • Distributed Systems notes and lectures by Tim Harris
  • Designing Data-Intensive Applications, by Martin Kleppmann

Concepts covered

• Goals of distributed systems
  • Abstraction
  • Scalability
  • Fault tolerance
  • Data consistency
  • Security
• Concurrency
  • Primitives
    • Atomics
    • goroutine
  • Synchronisation
    • Race condition
    • Mutex
    • Channel
• System models
  • Network behaviour
  • Node behaviour
  • Timing behaviour
• Remote procedure call (RPC)
  • Idempotence
• Clock synchronisation
  • Time-based clocks
    • Computer clock
    • Atomic clock
    • Cristian’s algorithm
  • Event-based clocks
    • Logical clock
    • Vector clock
• Broadcast communication
  • FIFO
  • Causal
  • Total order
• Fault tolerance
  • Crash recovery
    • Shadow copy
    • Write-ahead logging
  • Replication
    • Quorum-based replication
    • Broadcast-based replication
      • Primary-backup (PB)
      • State machine replication (SMR)
    • Consensus
  • Byzantine fault tolerance (BFT)
    • Security
      • Cryptographic hash function
      • Message authentication code
      • Public-key cryptography
      • Digital signature
    • Practical Byzantine fault tolerance (PBFT)
    • Bitcoin
• Data consistency
  • Models
    • Linearisability
    • Sequential consistency
  • CAP rule
  • BASE methodology
• Transaction
  • Serialisability
  • Two-phase locking (2PL)
  • Optimistic concurrency control (OCC)
  • Two-phase commit

Case studies

• Raft
• ZooKeeper
• Memcached
• Dynamo
• Bitcoin

Labs

• Go
• Nim

Lab notes

Lab 3:

• https://www.eecg.toronto.edu/~ashvin/courses/ece419/current/lab3.html
• https://www.eecg.toronto.edu/~ashvin/courses/ece419/current/lab3-advice.html
• https://www.eecg.toronto.edu/~ashvin/courses/ece419/current/raft-extended.pdf
• https://pdos.csail.mit.edu/6.824/labs/lab-raft1.html
• https://pdos.csail.mit.edu/6.824/labs/raft-locking.txt
• https://pdos.csail.mit.edu/6.824/notes/l-raft-QA.txt
• https://thesquareplanet.com/blog/students-guide-to-raft/
• https://chelseatroy.com/2020/08/30/raft-10-leader-elections-part-1/

Lab 4:

• https://pdos.csail.mit.edu/6.824/labs/lab-kvraft1.html
• https://www.eecg.toronto.edu/~ashvin/courses/ece419/current/lab4.html

Tips

When I took this course, it was a new iteration (overhaul of curriculum, new professor). It was a little rough around the edges, but otherwise a good experience.

• For labs 3/4 (Raft, key-value storage), it does not suffice to test once. It does not even suffice to test 10 or 20 times. Because Raft relies on probabilistic election timeouts, there will inevitably be a small edge case that you’ve missed. For this reason, you should be testing several hundred times.
  • For example, my initial 3A implementation failed 1/500 testing runs (for one test) because of a subtle bug relating to how my goroutines were spawned. My 3B implementation failed 1/50 testing runs (for one test).
  • That is to say, your implementation won’t be exhaustively correct unless you test this many times. This will help you out in the long-run — since the labs build on each other, this will expose any bugs from previous parts (even if you got 100%!) and it’s better to have a working solution than needing to backtrack.
  • For this reason, I recommend creating a testing script of your own to run the tests many times and report a success rate.
• The labs’ RPC runtime mimics real-world networks. Just like real-world networks, the runtime can be exhausted if you send too many RPCs at once, and RPCs will begin to fail irrespective of what your implementation does.
• There were very few prep resources for exams. I found:
  • Past ECE419 exams useful for clock questions. For consistency questions, they were good to take a look at, but are designed differently now (past questions were quite confusingly designed).
  • Past 6.824 exams useful for case study-related questions.