Phase king vs raft vs paxos vs zookeeper

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

This page compares four important approaches to agreement in distributed systems:

• Phase King – a synchronous Byzantine agreement algorithm used primarily in theory
• Paxos – a foundational consensus protocol with strong theoretical guarantees
• Raft – a practical, leader-based consensus algorithm designed for understandability
• ZooKeeper (Zab) – a distributed coordination service built on atomic broadcast

Use cases:

• Phase King: not really used in practice.
• Raft: embedded inside a system
• Paxos: protocol family
• ZooKeeper: external coordination service

NB! No consensus algorithm can guarantee termination in a fully asynchronous system. All practical systems (Raft, Paxos, Zab) rely on partial synchrony and timeouts.

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

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

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.

ZooKeeper vs Raft and Paxos

Overview

Apache ZooKeeper is a distributed coordination service rather than a standalone consensus algorithm. Internally, it uses a consensus protocol called Zab (ZooKeeper Atomic Broadcast), which is similar in spirit to leader-based consensus algorithms such as Raft and Multi-Paxos.

What ZooKeeper Is

• A distributed coordination service providing:
  • Configuration management
  • Naming/registry services
  • Distributed synchronization (locks, leader election)
• Exposes a filesystem-like hierarchical data model (znodes)
• Clients interact with a replicated state maintained by a cluster

Underlying Algorithm

• ZooKeeper uses Zab (ZooKeeper Atomic Broadcast)
• Zab is:
  • Leader-based
  • Crash fault-tolerant (not Byzantine)
  • Designed for high-throughput broadcast of updates

Assumptions

ZooKeeper (Zab)

• Partial synchrony
• Crash fault model
• Majority quorum:
  • <math>n \ge 2f + 1</math>
• Single leader at a time

Comparison

Aspect	ZooKeeper (Zab)	Raft	Paxos
Fault model	Crash	Crash	Crash
Timing	Partial synchrony	Partial synchrony	Partial synchrony
Leader	Yes	Yes	Optional (explicit in Multi-Paxos)

Key intuition:

• Zab ≈ a specialized form of Multi-Paxos optimized for ordered broadcast
• Very similar operational model to Raft:
  • One leader
  • Followers replicate state
  • Majority acknowledgment required

Where ZooKeeper Is Used

ZooKeeper is widely used as a coordination backbone in distributed systems:

• Apache Kafka:
  • Broker metadata and controller election (historically)
• Apache Hadoop:
  • Coordination of distributed components
• Apache HBase:
  • Master election and region management
• Apache Solr / Elasticsearch (older versions):
  • Cluster coordination

Typical use cases:

• Leader election
• Distributed locks
• Service discovery
• Configuration storage

Intuition

• ZooKeeper:
  • "Provide a shared coordination service for distributed systems."

• Raft:
  • "Provide an understandable consensus building block."

• Paxos:
  • "Provide a minimal, flexible foundation for consensus."