Lectures‎ > ‎


Foundations of Distributed Computing


System model (nodes)
  • Execute code
  • Store data
  • A clock

Failure models
  • Crash failure
    • Nodes either crash and perhaps restart later
  • Byzantine failure
    • Nodes act arbitrarily
    • Consider Bitcoin

  • Synchronous
    • Programs execute as same speed
    • Bound on message transfer
    • Accurate clocks
  • Asynchronous
    • No timing assumptions
    • No bound on message transfer
    • Independent clocks
  • Network partitions

The Consensus Problem
  • Agreement - all nodes agree on a value (think key-value store)
  • Integrity - all correct processes agree on a proposed value from some process
  • Termination - all processes eventually reach a decision
  • Validity - If all correct processes propose the same value V, then all correct processes decide V

FLP Impossibility
  • Asynchronous model
  • Crash failure model
  • Reliable network
  • No deterministic algorithm for the consensus (agreement) in a system subject to failures, even if messages can never be lost, at most one process can fail by crashing.

The CAP Theorem
  • Pick two:
    • Consistency
    • Availability
    • Partition tolerance
Eventual consistency

Time and Order

Partial Order

Global vs local clocks

No clocks

Failure detectors