State Machine replication

[nicola]

• Chain Replication, Chain Replication for Supporting High Throughput and Availability (survey of the field)
  • primary backup
    • primary backup: primary sequence write operations & forward to replica
    • configuration manager: monitor failure detection & promote replicas on failure
  • quorum intersection: perform requests against a replica set
  • head receives an update, propagates the update, tail ack the request
  • head has updates that tail does not (assuming any channel is reliable)
  • reconfigure a chain during failure, centralized configuration manager performs all the failure detection. (replace with predecessor (if tail) or successor (if head), successor + inflight (if in the middle))

Consensus

• Strategies for deciding a slot
  • Content for slots (Paxos)
  • One replica decides (Multi-Paxos, Fast Paxos)
  • Take turns in round-robin
• ⭐️ Paxos, The part-time parliament
  • agreement protocol used by a set of process to agree on one value
  • failures (fail-stop) 2F+1
  • no sync assumption
  • clients submit their values to the replicas, replicas will contend for entries in the log
  • 2 RTT to commit a command: (1) take ownership of a slot (2) propose a command
  • distribute load across replicas
• ⭐️ Multi-paxos, Paxos Made Moderately Complex
  • there is a designated leader (owner of all the slots)
  • takes 1 RTT to commit the command (great for latency & throughput)
  • availability issue (single leader might fail)
• ⭐️ Egalitarian Paxos, There Is More Consensus in Egalitarian Parliaments (video)
  • Paxos with high throughput and low latency
  • parallel logs: one for each replica
  • lamport causality: replicas attach ordering constraints, this gives commutativity of concurrent requests
  • 1 roundtrip for non-concurrent/interfering commands
  • 2 roundtrip for concurrent and interfering commands
  • in practice: defer execution of operations with no return value by adding them to a log

Paxos now

• Flexible Paxos

SMR

SMR now

• Tango: Distributed Data Structures over a shared log
• OpLog
• Dynamic SMR

Public ledger

• public ledger: tamper proof sequence of data that can be read and augmented by everyone