Phase king vs raft vs paxos vs zookeeper

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

Do Real Systems Use the Phase King Algorithm?

Short Answer

No — real-world distributed systems do not use the Phase King algorithm.

Why Phase King Is Not Used in Practice

1. Unrealistic Timing Assumptions

• Requires a fully synchronous system:
  • Known upper bounds on message delays
  • Lock-step execution of rounds across all nodes
• Real systems are typically asynchronous or only partially synchronous
• Even small timing violations can break correctness

2. High Communication Cost

• Message complexity: <math>O(n^2 f)</math>
• Each round requires all-to-all communication
• Does not scale well to larger systems

3. Strong (and Expensive) Fault Model

• Designed to tolerate Byzantine faults:
  • Nodes may lie, equivocate, or collude
• Most real systems assume weaker fault models:
  • Crash faults (nodes stop but do not misbehave)
• Byzantine tolerance is used only when necessary due to cost

4. Lack of Practical Ecosystem

• No widely adopted implementations
• Not integrated with:
  • Storage systems
  • RPC frameworks
  • Production infrastructure
• Exists mainly in textbooks and theoretical research

What Real Systems Use Instead

Crash Fault-Tolerant Systems

• Raft
• Paxos / Multi-Paxos
• Used in systems such as:
  • etcd
  • Consul
  • ZooKeeper (Zab protocol, Paxos-like)

Byzantine Fault-Tolerant Systems

• Practical Byzantine Fault Tolerance (PBFT)
• Tendermint
• HotStuff

• These protocols:
  • Work under partial synchrony
  • Are optimized for real-world networks
  • Avoid strict round-based synchrony like Phase King

Why Study Phase King?

Phase King remains important for theoretical and educational reasons:

• Demonstrates that Byzantine agreement is possible
• Establishes the bound:
  • <math>n \ge 3f + 1</math>
• Introduces key ideas:
  • Majority filtering
  • Role-based tie-breaking (the “king”)

Intuition

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

• Practical systems (Raft, PBFT) answer:
  • "How can we build reliable systems under realistic assumptions?"

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?"