This repository contains an implementation of the Paxos algorithm as described in the Paxos Made Simple paper by Leslie Lamport.
This is not a production-ready implementation of the Paxos algorithm and is written solely for educational purpose.
The Paxos algorithm, as described in the Paxos Made Simple paper, consists of three different roles -
- Acceptor - Nodes/processes that hold the value to be agreed upon by the system.
- Learner - Nodes/processes that needs to know the agreed upon value.
- Proposer - Nodes/processes that propose values to be accepted by the system.
A real-world implementation of the algorithm would have a node taking up one or more than one of these three roles.
In this implementation, we run all the different actors of the Paxos algorithm inside a single thread.
The implementation relies on the Messenger class. The Messenger class is responsible for all the node-to-node communication happening in the system.
To simulate real-world systems, we can plugin various implementation of Messenger to simulate different behaviours. For instance, the library provides ChaosMessenger as an implementation of the Messenger class.
The following diagram summarizes the overall architecture of the repository.
classDiagram
%% ── Interfaces ──────────────────────────────────────────────
class IMessageHandler {
<<interface>>
+node_id() NodeId
+receive(Message~V~)
}
class IQuorum {
<<interface>>
+has_quorum(votes, total) bool
}
class IStorage {
<<interface>>
+save(AcceptorState~V~)
+load() AcceptorState~V~
}
%% ── Roles ────────────────────────────────────────────────────
class Proposer {
-id_ NodeId
-ballot_ BallotNumber
-state_ ProposerState
-highest_prior_ optional~AcceptedValue~
-seen_promises_ unordered_set~NodeId~
-phase_timeout_ticks_ uint32
+create() shared_ptr~Proposer~
+propose(V)
+tick()
-start_phase1()
-start_phase2(V)
-on_promise(Promise~V~)
-on_nack(Nack~V~)
}
class Acceptor {
-id_ NodeId
-promised_ BallotNumber
-accepted_ optional~AcceptedValue~
+create() shared_ptr~Acceptor~
-on_prepare(Prepare~V~)
-on_accept(Accept~V~)
}
class Learner {
-id_ NodeId
-decided_ bool
-votes_ map~BallotNumber, Tally~
+create() shared_ptr~Learner~
+decided() bool
-on_accepted(Accepted~V~)
}
%% ── Messenger ────────────────────────────────────────────────
class Messenger {
-handlers_ map~NodeId, IMessageHandler~
+register_handler(IMessageHandler~V~)
+unregister_handler(NodeId)
+send(from, to, Message~V~)
+broadcast(from, Message~V~)
#should_drop() bool
}
class ChaosMessenger {
-cfg_ Config
-rng_ mt19937_64
-drop_dist_ uniform_real_distribution
#should_drop() bool
}
%% ── Support types ────────────────────────────────────────────
class BallotNumber {
+round uint64
+node_id NodeId
+next(NodeId) BallotNumber
+is_null() bool
}
class AcceptedValue {
+ballot BallotNumber
+value V
}
class AcceptorState {
+promised BallotNumber
+accepted optional~AcceptedValue~
}
class Tally {
+value V
+voters unordered_set~NodeId~
}
class ProposerState {
<<enumeration>>
Idle
Phase1Pending
Phase2Pending
Decided
Conflicted
}
class MajorityQuorum {
+has_quorum(votes, total) bool
}
class InMemoryStorage {
-state_ AcceptorState~V~
+save(AcceptorState~V~)
+load() AcceptorState~V~
}
class Message {
<<variant>>
Prepare~V~
Promise~V~
Accept~V~
Accepted~V~
Nack~V~
}
%% ── Inheritance ──────────────────────────────────────────────
IMessageHandler <|.. Proposer
IMessageHandler <|.. Acceptor
IMessageHandler <|.. Learner
IQuorum <|.. MajorityQuorum
IStorage <|.. InMemoryStorage
Messenger <|-- ChaosMessenger
%% ── Ownership / dependencies ─────────────────────────────────
Messenger o-- IMessageHandler : registry
Proposer --> Messenger : sends via
Acceptor --> Messenger : sends via
Learner --> Messenger : registered with
Proposer --> IQuorum : uses
Learner --> IQuorum : uses
Acceptor --> IStorage : persists via
Proposer --> BallotNumber : owns
Proposer --> AcceptedValue : tracks prior
Proposer --> ProposerState : state machine
Acceptor --> AcceptedValue : accepted_
Acceptor --> AcceptorState : persists
Learner --> Tally : votes_
AcceptorState --> AcceptedValue : contains
This is how the library can be used.
#include "paxos/Acceptor.hpp"
#include "paxos/Learner.hpp"
#include "paxos/Messenger.hpp"
#include "paxos/Proposer.hpp"
#include "paxos/Quorum.hpp"
#include "paxos/Storage.hpp"
#include <iostream>
int main() {
using V = std::string;
// ── 1. Shared infrastructure ──────────────────────────────────────
auto messenger = std::make_shared<Messenger<V>>();
auto quorum = std::make_shared<MajorityQuorum>();
// ── 2. Build a 3-node cluster ─────────────────────────────────────
// Each Acceptor gets its own durable storage.
// Each role registers itself with the Messenger on construction.
auto s1 = std::make_shared<InMemoryStorage<V>>();
auto s2 = std::make_shared<InMemoryStorage<V>>();
auto s3 = std::make_shared<InMemoryStorage<V>>();
auto a1 = Acceptor<V>::create(1, messenger, s1);
auto a2 = Acceptor<V>::create(2, messenger, s2);
auto a3 = Acceptor<V>::create(3, messenger, s3);
// ── 3. One Learner — notified when consensus is reached ───────────
std::string chosen;
auto learner = Learner<V>::create(
10, /*cluster_size=*/3, messenger, quorum,
[&chosen](const V& v) {
chosen = v;
std::cout << "Consensus reached: " << v << "\n";
});
// ── 4. One Proposer ───────────────────────────────────────────────
auto proposer = Proposer<V>::create(99, /*cluster_size=*/3, messenger, quorum);
// ── 5. Propose a value ────────────────────────────────────────────
proposer->propose("hello");
// In the synchronous model, the entire protocol runs inline.
// tick() drives retries if any messages were dropped.
for (int i = 0; i < 20 && !learner->decided(); ++i)
proposer->tick();
// chosen == "hello"
return 0;
}