Phase king vs raft vs paxos vs zookeeper

Allikas: Lambda
Redaktsioon seisuga 23. märts 2026, kell 06:18 kasutajalt Tammet (arutelu | kaastöö)
Mine navigeerimisribale Mine otsikasti

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

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

Raft vs Paxos: Use Cases, Assumptions, and Risks

Raft and Paxos are both consensus algorithms designed for crash fault-tolerant distributed systems. They provide similar theoretical guarantees but differ significantly in design philosophy, usability, and typical deployment scenarios.

Where assumptions differ

Raft

  • Strong leadership:
    • A single leader manages log replication and client interaction

Paxos

  • No fixed leader in basic Paxos:
    • Roles (proposer, acceptor, learner) are logically separate
    • Leader optimization (Multi-Paxos) is commonly used in practice

Design Philosophy

Raft

  • Explicit goal: understandability
  • Decomposes consensus into:
    • Leader election
    • Log replication
    • Safety rules
  • Strong, stable leader simplifies reasoning

Paxos

  • Minimal and abstract
  • Focuses on safety properties with minimal assumptions
  • More flexible but harder to understand and implement correctly

Risks and Failure Modes

Raft

  • Leader dependency:
    • System performance depends on leader health
    • Leader failure triggers re-election delays
  • Availability risks:
    • Requires a majority of nodes to be available
    • Network partitions can stall progress
  • Simplicity tradeoff:
    • Less flexible for certain optimizations compared to Paxos variants

Paxos

  • Liveness challenges:
    • Basic Paxos can experience repeated conflicts between proposers
    • Requires leader optimization (Multi-Paxos) for efficiency
  • Operational difficulty:
    • Harder to debug and reason about in production systems

Efficiency and Performance

Raft

  • Leader-based replication:
    • <math>O(n)</math> messages per log entry
  • Typically commits in 1–2 round-trip times (RTTs)
  • Predictable performance under normal operation

Paxos

  • Basic Paxos:
    • Multiple phases per decision
    • Higher latency without optimization
  • Multi-Paxos (common in practice):
    • Similar efficiency to Raft after leader is established
    • <math>O(n)</math> messages per decision

Key Differences Summary

Aspect Raft Paxos
Design goal Understandability Minimality and flexibility
Leadership Strong, explicit leader Implicit or optional (explicit in Multi-Paxos)
Ease of implementation Easier Difficult
Typical use Production systems, teaching Research, highly optimized systems
Risk profile Operational simplicity, leader bottleneck High complexity, subtle correctness issues

Practical Insight

  • Raft is generally preferred for new systems due to its clarity and strong engineering model.
  • Paxos (especially Multi-Paxos) remains influential and is used in systems where fine-grained control and optimization are required.
Pärit leheküljelt "http://www.lambda.ee/w/index.php?title=Phase_king_vs_raft_vs_paxos_vs_zookeeper&oldid=22793"