Interactive Programming Education Platform

Logic Practice

Introduction:

The Paxos Algorithm serves as a crucial agreement protocol enabling multiple systems or nodes to reach a consensus on a single value, even amidst node failures, message delays, or losses. This protocol proves especially valuable in distributed computing scenarios where maintaining consistency through system-wide agreement is paramount.

Let's see what is Paxos:

Paxos essentially offers a method for a collection of distributed systems to achieve a consensus. Picture multiple machines (or "nodes") striving to come to a unanimous decision, such as identifying the present leader in a network, validating a transaction, or harmonizing shared data. Paxos guarantees that in the event of certain computers failing, the rest can still reach an accord.

The algorithm functions through two primary stages (accompanied by several sub-stages) and is commonly divided into different tasks and accountabilities to streamline its structure.

It primarily involves three types of participants, as shown below:

✅ Proposers - These propose values for consensus.
✅ Acceptors - These vote on proposed values.
✅ Learners - These learn the agreed-upon value once consensus is reached.

Implementation:

Example


#include <iostream>
#include <unordered_map>
#include <vector>
#include <optional>
using ProposalID = int;
// Represents a value proposal
struct Proposal {
    ProposalID id;
    int value;
};
// Represents an Acceptor in Paxos
class Acceptor {
private:
    std::optional<ProposalID> promised_id;
    std::optional<Proposal> accepted_proposal;
public:
    // Phase 1: Prepare
    bool prepare(ProposalID proposal_id) {
        if (!promised_id || proposal_id > *promised_id) {
            promised_id = proposal_id;
            return true;
        }
        return false;
    }
    // Phase 2: Accept
    bool accept(const Proposal& proposal) {
        if (!promised_id || proposal.id >= *promised_id) {
            accepted_proposal = proposal;
            promised_id = proposal.id;
            return true;
        }
        return false;
    }
    // Get the last accepted proposal (if any)
    std::optional<Proposal> getAcceptedProposal() const {
        return accepted_proposal;
    }
};
// Represents a Proposer in Paxos
class Proposer {
private:
    ProposalID proposal_id = 0;
    int proposal_value;
    int quorum_size;
public:
    Proposer(int value, int quorum) : proposal_value(value), quorum_size(quorum) {}
    // Phase 1: Prepare and get promises
    bool propose(std::vector<Acceptor>& acceptors) {
        proposal_id++;
        int promises = 0;
        std::optional<int> highest_value;
        // Send prepare requests to all acceptors
        for (auto& acceptor : acceptors) {
            if (acceptor.prepare(proposal_id)) {
                promises++;
                auto accepted = acceptor.getAcceptedProposal();
                if (accepted && (!highest_value || accepted->id > proposal_id)) {
                    highest_value = accepted->value;
                }
            }
        }
        // If a majority of promises are received, proceed to accept phase
        if (promises >= quorum_size) {
            int value_to_propose = highest_value.value_or(proposal_value);
            return accept(acceptors, value_to_propose);
        }
        return false;
    }
private:
    // Phase 2: Accept and get a consensus
    bool accept(std::vector<Acceptor>& acceptors, int value) {
        int accepts = 0;
        // Send accept requests to all acceptors
        for (auto& acceptor : acceptors) {
            if (acceptor.accept({proposal_id, value})) {
                accepts++;
            }
        }
        return accepts >= quorum_size;
    }
};
// Represents a Learner that records the chosen value
class Learner {
public:
    void learn(int value) {
        std::cout << "Learner: Value " << value << " chosen by consensus.\n";
    }
};
// Paxos Simulation with a single proposer, multiple acceptors, and a learner
void paxos_simulation(int proposal_value) {
    const int num_acceptors = 3;
    const int quorum = (num_acceptors / 2) + 1;
    Proposer proposer(proposal_value, quorum);
    std::vector<Acceptor> acceptors(num_acceptors);
    Learner learner;
    // Run the Paxos algorithm
    if (proposer.propose(acceptors)) {
        learner.learn(proposal_value);
    } else {
        std::cout << "Consensus not reached.\n";
    }
}
int main() {
    int value = 42; // The value to reach consensus on
    paxos_simulation(value);
    return 0;
}

Output:

Output


Learner: Value 42 chosen by consensus.

Explanation:

Step 1: The Role of Acceptors

Acceptors play a crucial role in the Paxos protocol as they hold the authority to approve or reject proposals initiated by Proposers. Their responsibilities involve two primary functions:

✅ Prepare Phase - Committing to a Proposal: Acceptors are tasked with evaluating new proposals presented by Proposers, each proposal accompanied by a distinct identifier for differentiation. If the proposal's identifier surpasses all previous ones observed by the Acceptor, it commits to a "promise" to the Proposer. This commitment signifies that the Acceptor will only entertain proposals with higher identifiers in the future. By maintaining the uniqueness and increasing order of proposal identifiers, the system effectively prevents conflicts, establishing a groundwork for achieving consensus.
✅ Accept Phase - Endorsing a Proposal: After gathering commitments from a majority of Acceptors, the Proposer proceeds to request their endorsement for the proposal. Acceptors validate the proposal by confirming that its identifier matches or surpasses the identifiers of previously committed proposals. By accepting the proposal under these conditions, the Acceptor essentially casts a supportive vote for the proposed value.

By completing these two actions, Acceptors establish a method to systematically choose a single proposal for agreement by evaluating identifiers and exclusively approving or committing to proposals that satisfy their standards.

Step 2: The Role of the Proposer

The Initiator kicks off the consensus procedure. Its responsibility is to propose a value intended for universal agreement among all nodes, and it proceeds through two stages to achieve this goal:

✅ Initiate and Gather Commitments (Prepare Phase): The Initiator creates a distinct proposal ID for each new suggestion. Subsequently, it transmits this ID together with its proposed value to the Acceptors, requesting them to commit to not accepting any prior proposals. Once the Initiator garners a majority of commitments, it can confidently proceed. This requirement for a majority is crucial as it ensures adequate support from Acceptors for the proposal, thereby enhancing the chances of reaching an agreement.
✅ Obtain Approvals (Accept Phase): Upon securing a sufficient number of commitments, the Initiator dispatches an "accept" plea to the Acceptors, including the agreed-upon proposal ID and value. The Acceptors then have the option to approve the proposal, provided they have not received a higher proposal ID in the interim. If a majority of Acceptors approve the proposal, a consensus is achieved.

This dual-stage method guarantees that the Proposer proceeds with a proposal only if most Acceptors are ready to endorse it, establishing the foundation for a unified, consensual value.

Step 3: The Role of the Learner

Once the Acceptors achieve agreement on a specific value, the responsibility of the Observer is to document or "observe" this selected value. The Observer functions as a recorder, documenting the result to enable other system components to depend on the established outcome. In practical distributed systems, Observers are crucial in guaranteeing that all entities are informed of the ultimate determination. In this context, the Observer merely displays the value, although in a more extensive system, it might modify a database or inform other modules.

The recipient obtains the ultimate approved value from the initiator after a sufficient number of acceptors have acknowledged it, signaling the conclusion of the Paxos protocol for this particular proposition.

Complexity analysis:

Time Complexity:

Basic Rounds:

✅ Paxos requires two rounds of communication for each proposal to reach a consensus:
✅ Prepare Phase: The Proposer sends a "prepare" message to all Acceptors and waits for a majority response (promises).
✅ Accept Phase: Once it receives enough promises, it sends an "accept" message and waits for a majority of Acceptors to agree.
✅ In total, these two rounds make Paxos relatively efficient in terms of rounds, especially when there are no failures or conflicts.

Latency Impact:

✅ In a distributed system, each round can take time proportional to the network's latency.
✅ Under ideal conditions with no failures, Paxos has a time complexity of O(2) rounds to reach consensus.
✅ If there are conflicts (e.g., multiple Proposers competing) or node failures, additional rounds may be required, increasing latency.

If certain nodes encounter failures or experience message delays, it becomes imperative to initiate extra retry attempts. This situation can result in increased latency in real-world scenarios. The intricacy involved is directly influenced by the quantity of retry attempts, a factor that fluctuates based on the system's resilience to faults and the reliability of the network.

Space Complexity:

Acceptors maintain the maximum proposal ID they have committed to accept, in addition to any accepted proposal. Typically, this requires a fixed amount of memory, resulting in O(1) complexity per Acceptor.

Proposers:

✅ Individuals putting forth proposals must maintain records of unique proposal IDs and certain internal information (like the specific value being proposed). As they are not required to retain responses long-term, the space complexity per Proposer remains at O(1).

Learners:

✅ Individuals retain the ultimate, selected value after agreement is achieved. With every suggestion they "absorb," the spatial complexity stays at O(1) per Individual.

Overall Spatial Complexity:

✅ Throughout the complete system, every node retains a fixed quantity of data for each proposal, resulting in an overall space complexity of O(N), where N represents the total number of nodes.
✅ In more extensive setups or in systems with high data processing rates, logs or durable storage could augment the space requirements, but the fundamental algorithmic aspect per node remains unchanged.

Properties:

✅ 1. Safety (Consistency) Property: Paxos ensures that if a value has been chosen by consensus, all nodes that learn the selected value will agree on the same value. This property holds even in the presence of network delays or node failures. Explanation: This consistency is achieved by carefully controlling the proposal process. Paxos guarantees that no two different values will be chosen as long as the algorithm operates under its fault tolerance limits.
✅ Fault Tolerance Property: Paxos can tolerate up to half of the nodes failing without losing the ability to reach consensus. Explanation: This fault tolerance is achieved because Paxos only requires a majority of nodes (a quorum) to agree. If fewer than a majority fail, the remaining nodes can still form a quorum and proceed with the consensus.
✅ Non-Blocking for Proposers Property: Proposers can operate independently and do not need to wait for responses from all Acceptors-only a majority. Explanation: This property allows Proposers to remain active and retry proposals if they detect other conflicting Proposers. If one Proposer fails, others can continue the proposal process.
✅ Property: Paxos ensures that if a value has been chosen by consensus, all nodes that learn the selected value will agree on the same value. This property holds even in the presence of network delays or node failures.
✅ Explanation: This consistency is achieved by carefully controlling the proposal process. Paxos guarantees that no two different values will be chosen as long as the algorithm operates under its fault tolerance limits.
✅ Property: Paxos can tolerate up to half of the nodes failing without losing the ability to reach consensus.
✅ Explanation: This fault tolerance is achieved because Paxos only requires a majority of nodes (a quorum) to agree. If fewer than a majority fail, the remaining nodes can still form a quorum and proceed with the consensus.
✅ Property: Proposers can operate independently and do not need to wait for responses from all Acceptors-only a majority.
✅ Explanation: This property allows Proposers to remain active and retry proposals if they detect other conflicting Proposers. If one Proposer fails, others can continue the proposal process.

Paxos Algorithm In C++