Phase king vs raft vs paxos vs zookeeper

The comparisons and notes written in collaboration with Tanel and GPT 5.3

Phase King vs Raft Consensus Algorithms

Big Picture

Aspect	Phase King	Raft
Model	Synchronous	Partially synchronous / asynchronous
Faults	Byzantine (arbitrary/malicious)	Crash faults only
Goal	Theoretical agreement under worst-case faults	Practical replicated state machine
Typical Use	Theory / teaching Byzantine agreement	Real systems (e.g., etcd, Consul)

Assumptions

Phase King

• Fully synchronous system
  • Known upper bound on message delay
  • Lock-step rounds
• Handles Byzantine faults
  • Nodes may lie, equivocate, or collude
• Requires: <math>n \ge 3f + 1</math>

Raft

• Partial synchrony
  • No fixed delay bound, but eventually messages are timely
• Handles crash faults only
  • Nodes may stop but do not behave maliciously
• Requires: <math>n \ge 2f + 1</math>

Guarantees

Phase King

• Agreement: All correct nodes decide the same value
• Validity: If all correct nodes start with the same value, that value is chosen
• Termination: Always terminates in a fixed number of rounds

Raft

• Safety (always):
  • No two leaders commit different values at the same log index
  • Logs remain consistent across nodes
• Liveness (eventual):
  • Progress occurs once the network stabilizes

Algorithm Structure

Phase King

• Runs in <math>f + 1</math> rounds
• Each round:
  • Nodes broadcast their values
  • A majority value is computed
  • A designated king node enforces a decision if needed
• The king resolves ambiguity caused by Byzantine nodes

Raft

• Continuous protocol consisting of:
  • Leader election
  • Log replication
  • Commit mechanism
• Leader-based design:
  • Leader sends log entries to followers
  • Entries are committed once a majority acknowledges

Efficiency

Phase King

• Rounds: <math>f + 1</math>
• Messages per round: <math>O(n^2)</math>
• Total messages: <math>O(n^2 f)</math>
• High communication overhead
• Requires strict synchrony
• Not used in practice

Raft

• Normal operation:
  • <math>O(n)</math> messages per log entry
• Leader election:
  • <math>O(n)</math> messages
• Latency:
  • Typically 1–2 round-trip times (RTTs)
• Efficient and scalable in practice

Key Differences

Fault Model

• Phase King: tolerates Byzantine faults
• Raft: tolerates crash faults only

Timing Model

• Phase King: requires strict synchrony
• Raft: assumes eventual synchrony

Practicality

• Phase King: theoretical and pedagogical
• Raft: widely used in production systems

Mechanism

• Phase King: rotating "king" authority per round
• Raft: stable leader-based replication

Complexity

• Phase King: <math>O(n^2 f)</math>
• Raft: <math>O(n)</math> per operation

When to Teach Each

Phase King

• Byzantine agreement
• Fault tolerance under adversarial conditions
• Theoretical lower bounds (<math>n \ge 3f + 1</math>)

Raft

• Real-world distributed systems
• Replicated state machines
• Engineering tradeoffs in consensus design

Intuition

• Phase King answers:
  • "Can we reach agreement even if some nodes are actively malicious?"

• Raft answers:
  • "Can we build a reliable system from nodes that may crash?"