PAXOS Consensus Algorithm Implementation
Python-based simulation of the PAXOS consensus protocol with fault tolerance testing and performance evaluation.
The PAXOS Consensus Algorithm Implementation project demonstrates a Python-based simulation of the classic PAXOS fault-tolerant consensus protocol. PAXOS ensures that distributed nodes reach agreement on a single value, even in the presence of failures, and is fundamental to distributed systems such as databases, blockchain, and cloud coordination frameworks. This implementation models the three core PAXOS roles — Proposers, Acceptors, and Learners — as independent Python
1. Prepare Phase — Proposers generate unique proposal numbers (tuple of sequence number and process ID) and send them to all acceptors. Acceptors promise not to accept lower-numbered proposals.
2. Accept Phase — Upon receiving majority promises, proposers send their proposed value to acceptors, which accept and store it if conditions are met.
3. Commit Phase — Accepted values are propagated to learners, which confirm majority agreement and commit the decision.
The program includes fault simulation, where acceptor processes can be intentionally crashed to test PAXOS’s resilience. Performance is evaluated over multiple iterations with and without crashes, recording the time required for each proposer and learner to reach consensus.
multiprocessing processes, communicating through manager-backed shared lists and values. The algorithm is executed in three phases: 1. Prepare Phase — Proposers generate unique proposal numbers (tuple of sequence number and process ID) and send them to all acceptors. Acceptors promise not to accept lower-numbered proposals.
2. Accept Phase — Upon receiving majority promises, proposers send their proposed value to acceptors, which accept and store it if conditions are met.
3. Commit Phase — Accepted values are propagated to learners, which confirm majority agreement and commit the decision.
The program includes fault simulation, where acceptor processes can be intentionally crashed to test PAXOS’s resilience. Performance is evaluated over multiple iterations with and without crashes, recording the time required for each proposer and learner to reach consensus.
<!--
See https://www.debugbear.com/blog/responsive-images#w-descriptors-and-the-sizes-attribute and
https://developer.mozilla.org/en-US/docs/Learn/HTML/Multimedia_and_embedding/Responsive_images for info on defining 'sizes' for responsive images
-->
<img
src="/assets/img/Paxos_flowchart.jpg"
class="img-fluid rounded z-depth-1"
width="100%"
height="auto"
title="Flowchart of the PAXOS Algorithm"
loading="lazy"
onerror="this.onerror=null; $('.responsive-img-srcset').remove();"
>
</picture>
</figure>
Flowchart representation of the PAXOS consensus process, illustrating the interactions between proposers, acceptors, and learners during the prepare, accept, and commit phases.
— –>
Experimentation Results
Left: Time taken by proposers to achieve consensus with 5 acceptors and 5 learners (no crashes). Right: Time taken when 2 acceptors are crashed (3 acceptors and 5 learners).
Key Insights
- Initialization Overhead — Proposer 1 takes longer due to acceptor/learner initialization, while Proposer 2 benefits from already-running components.
- Crash Tolerance — Crashing 2 acceptors slightly increases consensus time for Proposer 1 but has negligible effect for Proposer 2.
- Scalability Observations — Increasing acceptors and learners generally increases consensus time, consistent with PAXOS’s majority-based guarantees.
Technologies Used
- Python multiprocessing for role-based process isolation.
- Shared memory objects for inter-process communication.
- Matplotlib for visualizing consensus performance metrics.