Lecture 5: Distributed Agreement

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