sh*shqa

sh*shqa

Jan 1, 0001

Multi-Paxos

While we use Consensus, there is nothing scary

The intuition

multi-paxos-algorithm.png

Empty slots?

multi-paxos-empty-slots.png

Leader election

$\Omega(t) \rightarrow p$ (Distinguished Proposer)

  • decompose Linearizability from Safety

multi-paxos-leader-election.png

multi-paxos-leader-election-problem.png

The algorithm so far

  • new command comes to node
  • node follows to leader
  • leader proposes
  • leader commits
  • node answers to client

$\rightarrow$ 4 RTT

Better:

  • new command comes to node $\rightarrow$ redirect to leader
  • leader proposes
  • leader commits
  • leader answers to client

$\rightarrow$ 3 RTT

Better!!

Use pipelining! (similar to instruction-pipelining)

multi-paxos-pipelining.png

  • new command comes to node $\rightarrow$ redirect to leader
  • leader commits
  • leader answers to client

$\rightarrow$ 2 RTT

New meanings

  • n - epoch (leader)
  • n_p - leader, replica follows
  • Propose - election
  • Accept - new rule