sh*shqa

sh*shqa

Jan 1, 0001

Single-Decree Paxos

Propose(v) -> v*

Roles

  • Proposer
  • Acceptor

Intuition

(n, v) - proposal

n - unique, monotonic for each proposer

  1. Lock (lease) all acceptors
  2. Accept proposal on all acceptors

Algorithm

single-decree-paxos-algorithm.png

Scenarios

single-decree-paxos-intuition.png

When value is selected?

single-decree-paxos-when-selected.png

When (n, v) is chosen on majority

Agreement

single-decree-paxos-agreement-proof.png

Termination?

single-decree-paxos-livelock.png

Exponential backoff

Sleep before retry operations $t_{\text{backoff}} = t_{\text{backoff}} * C$