Lecture 5: Distributed Agreement

Terms you should know

Paul Krzyzanowski

March 4, 2021

Mutual Exclusion

  • Safety
  • Liveness
  • Delay
  • Single point of failure
  • Centralized algorithm
    • Understand how it works
  • Token Ring algorithm
    • Understand how it works
  • Lamport’s mutual exclusion
    • Understand how it works
    • Lamport timestamps
    • Request and Reply messages
    • Contents of a Request message
  • Ricart & Agrawala mutual exclusion
    • Difference from Lamport’s algorithm
    • Request and Reply messages

Leader Election

  • Algorithm assumptions
  • Bully algorithm
    • Understand how it works
  • Ring algorithm
    • Understand how it works
  • Chang & Roberts Ring algorithm
    • Understand what its goals are
    • Don’t try to memorize all the conditions of what to do for each message
  • Partitions
    • What’s the problem with a partition?

Raft consensus

  • FLP impossibility result
  • Quorum
  • Requirements for a consensus algorithm
  • Replicated log
  • Leader, candidate, follower roles
  • Purpose of RequestVotes and AppendEntries RPCs
  • Heartbeats
  • Terms
  • Election timeout
  • Randomized timeouts
  • Committed entries

Google Chubby

  • Purpose
  • Main design goal
  • Chubby cell
  • Role of master
  • Chubby files
  • Reading file data
  • Type of locking provided
  • Events
  • Role of Paxos consensus
  • Cache invalidations
Last modified March 6, 2021.
recycled pixels