Lehekülje Phase king vs raft vs paxos vs zookeeper lähteteksti vaatamine

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

There is also
* An introductory short comparison of blockchain algorithms with the ones above.
* A final chapter: an overview of the compromise algorithm: PBFT (practical byzantine fault tolerance)

Use cases:

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

<b>NB!</b> No consensus algorithm can guarantee termination in a fully asynchronous system.

All practical systems (Raft, Paxos, Zab) rely on partial synchrony and timeouts.

= Comparison to blockchain consensus algorithms =

Blockchain consensus can be viewed as an extension of classical distributed consensus:

* Adds Byzantine fault tolerance (as does phase king)
* Removes trusted membership assumptions
* Introduces incentives and cryptography
* Often retains core ideas:
** Leaders / proposers
** Quorums
** Replicated logs



* Raft prioritizes simplicity and performance in controlled environments
* PBFT extends consensus to Byzantine settings with stronger guarantees but higher cost
* Nakamoto consensus sacrifices efficiency for openness and decentralization


{| class="wikitable"
! Aspect !! Raft !! PBFT (Practical Byzantine Fault Tolerance) !! Nakamoto Consensus (Proof-of-Work)
|-
| Fault model || Crash faults || Byzantine faults || Byzantine + economic adversary
|-
| Network model || Partial synchrony || Partial synchrony || Fully asynchronous (probabilistic guarantees)
|-
| Participants || Fixed, known set || Fixed, known set || Open, permissionless
|-
| Identity model || Static identities || Static identities || Pseudonymous (Sybil-prone)
|-
| Sybil resistance || Not needed || Not needed || Required (PoW)
|-
| Fault tolerance || <math>f < n/2</math> || <math>f < n/3</math> || Depends on hash power (< 50% attacker)
|-
| Consensus type || Leader-based log replication || Leader-based voting protocol || Longest-chain rule
|-
| Leader role || Strong leader || Primary (leader) with view changes || Miner proposes blocks (implicit leader)
|-
| Communication pattern || Leader → followers || All-to-all voting (multiple phases) || Gossip-based block propagation
|-
| Message complexity || <math>O(n)</math> per entry || <math>O(n^2)</math> per decision || <math>O(n)</math> gossip (amortized)
|-
| Latency || 1–2 RTTs || Multiple rounds (≥2–3 RTTs) || Minutes (block confirmation time)
|-
| Finality || Immediate (deterministic) || Immediate (deterministic) || Probabilistic (confidence over time)
|-
| Throughput || High || Moderate || Low
|-
| Energy usage || Low || Low || Very high (mining)
|-
| Incentives || None || None || Economic incentives (block rewards, fees)
|-
| Typical use || Databases, coordination systems || Permissioned blockchains || Public blockchains (e.g., Bitcoin)
|-
| Examples || etcd, Consul || Tendermint, Hyperledger Fabric || Bitcoin, early Ethereum
|}

Note:

A Sybil attack is when one participant pretends to be many. Example:

* One attacker creates 1000 nodes
* System treats them as 1000 independent voters
* Attacker now controls the system

= 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

= Partial Synchrony in Raft =

Raft assumes a ''partially synchronous'' system:

* There is no known fixed upper bound on message delays
* However, after some unknown point in time, the system becomes "well-behaved":
** Message delays become bounded
** Processing speeds stabilize
** Communication is reliable enough for progress

A partially synchronous system can be understood as having two phases:

# '''Unstable period'''
#* Messages may be delayed arbitrarily long
#* Nodes may timeout incorrectly
#* Leader elections may repeatedly fail

# '''Stable period'''
#* Message delays are bounded by some unknown value <math>\Delta</math>
#* Timeouts begin to work reliably
#* A leader can be elected and maintain authority

The transition point between these phases is unknown and not detectable by the algorithm.

== Why Partial Synchrony Is Needed ==

In a fully asynchronous system:

* There is no bound on message delay
* It is impossible to distinguish between:
** A slow node
** A failed node

This leads to the FLP impossibility result:

* No deterministic consensus algorithm can guarantee termination in a fully asynchronous system

Raft avoids this by assuming eventual synchrony.

== How Raft Uses Partial Synchrony ==

Raft relies on timeouts for leader election:

* Nodes start elections if they do not hear from a leader
* Randomized timeouts reduce the chance of election conflicts

During the unstable period:

* Multiple nodes may start elections simultaneously
* Elections may fail repeatedly

During the stable period:

* One node times out first
* It becomes leader
* Other nodes receive its messages in time and follow it

= Phase King vs Raft Consensus Algorithms =

== Big Picture ==

{| class="wikitable"
! 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 ==

{| class="wikitable"
! 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 ===

{| class="wikitable"
! 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."

= How PBFT Differs from Phase King, Raft, Paxos, and ZooKeeper =


Practical Byzantine Fault Tolerance (PBFT) is a consensus algorithm designed to tolerate Byzantine (malicious) faults in partially synchronous systems. It bridges the gap between:

* Theoretical Byzantine algorithms (e.g., Phase King)
* Practical crash-fault systems (Raft, Paxos, ZooKeeper)

PBFT is widely used as a foundation for modern Byzantine fault-tolerant and permissioned blockchain systems.

Examples:
* Tendermint
* Hyperledger Fabric (variants)

== Fault Model ==

{| class="wikitable"
! Algorithm !! Fault Model
|-
| Phase King || Byzantine faults
|-
| PBFT || Byzantine faults
|-
| Raft || Crash faults only
|-
| Paxos || Crash faults only
|-
| ZooKeeper (Zab) || Crash faults only
|}

* PBFT tolerates arbitrary (malicious) behavior
* Requires <math>n \ge 3f + 1</math> nodes
* Crash-fault algorithms only require <math>n \ge 2f + 1</math>

== Timing Assumptions ==

{| class="wikitable"
! Algorithm !! Timing Model
|-
| Phase King || Fully synchronous
|-
| PBFT || Partial synchrony
|-
| Raft || Partial synchrony
|-
| Paxos || Partial synchrony
|-
| ZooKeeper || Partial synchrony
|}


== Algorithm Structure ==

=== PBFT ===
* Leader-based (called the ''primary'')
* Each decision proceeds in multiple phases:
** Pre-prepare
** Prepare
** Commit
* Requires agreement from <math>2f + 1</math> nodes