The History Of PAXOS Consensus Algorithm And Objectives

PAXOS

In 1989, Leslie Lamport developed the PAXOS Consensus method, a fundamental method in distributed computing, to address the consensus issue in networks of asynchronous processes. Despite network problems or node failures, its main goal is to guarantee that every machine (node) in a distributed system agrees on a single value. Functionalities like predictable distributed storage for big datasets are made possible by this approach, which enables distributed systems to operate predictably even in the event of server failures or network partitioning.

History of PAXOS

Conception and Inspiration

Leslie Lamport came up with PAXOS in 1989.

Interestingly, Lamport discovered it as a counterexample when attempting to demonstrate that a consensus algorithm with particular qualities couldn’t exist; it wasn’t originally intended as a solution for distributed systems.

A fictional parliament on the Greek island of Paxos served as the inspiration for Lamport’s original depiction, which was distinctive. This parliament was supposed to continue operating despite member turnover (“peripatetic propensity”), misplaced messages, and lawmakers who were prone to forgetfulness. In order to show how consensus may be formed in an unreliable setting with unreliable players, this analogy was used.

Publication and Recognition

In 1990, Lamport produced a research on PAXOS, but critics were unimpressed, finding it difficult to understand because it relied on a fictional parliament and raising doubts about its viability. In 1998, the paper was finally published in a scientific publication. Following its release, PAXOS first had trouble gaining popularity due to its unique presentation and complexity. Its fundamental ability to guarantee data consistency in remote systems, however, gradually came to light. In 2001, Lamport released a follow-up paper called “Paxos Made Simple,” which addressed the complexity by presenting the algorithm in a more clear manner and concentrating on fundamental ideas without using the analogy of a fictitious parliament.

You can also read What Is Mean By SDK Blockchain And Hyperledger Fabric API?

Objectives of the PAXOS Algorithm

While indirectly assisting others, PAXOS concentrates on accomplishing its primary goals.

Core Objectives

• Agreement: Preventing inconsistencies is the primary objective, which is to guarantee that all nodes in the system finally converge on the same value for a particular data item. A majority of acceptors can only vote for one proposal, according to the protocol.
• Liveness (Termination): As long as the network is largely working and there are enough nodes, progress is guaranteed, and a decision will be made eventually. The system won’t become stuck as a result. Learners will ultimately find a value if one is selected.
• Safety: focusses on selecting a legitimate value. By ensuring that the agreed-upon value must have come from a proposal from one of the nodes, it protects data integrity by removing the chance that the system would adopt a random or erroneous value. This guarantees that “nothing bad happens”.
• Validity: It cannot be “created out of thin air”; any determined value must have been honestly suggested through an honest procedure.

Secondary Objectives (Achieved Indirectly)

• Fault Tolerance: Through the maintenance of agreement and liveness, PAXOS naturally aids in fault tolerance. Resilient to hardware or software failures, the system can function even if some nodes fail as long as the majority do. For fault tolerance, PAXOS needs at least 2F + 1 nodes, where F is the number of crash-faulty nodes, presuming that fewer than 50% of nodes encounter crash faults.
• Data Consistency: Data consistency is promoted throughout the distributed system when all nodes concur on a single value.
• Scalability: Theoretically, systems with different numbers of nodes can still use PAXOS.
• Partial Ordering: Applications needing ordered task execution can benefit from its extension to provide a partial order on operations.
• In some failure cases, it may take a little longer to reach a decision because PAXOS prioritises safety over liveness, but it ensures a legitimate resolution.

You can also read Top Hyperledger Fabric Use Cases In Various Industries

Assumptions of PAXOS

In order to function properly, PAXOS assumes certain things about the underlying network and participant nodes:

Network Assumptions

Asynchronous Network: The asynchronous nature of the network is assumed by PAXOS, which means that messages can be sent in any sequence or not at all, with no assurance of prompt delivery or receipt. The reordering, packet loss, and delays that occur in distributed systems are reflected in this. PAXOS is made to deal with these uncertainty.

Node Assumptions

• Unreliable Processors: Because of hardware or software malfunctions, nodes in PAXOS are thought to be unreliable and may crash or stop responding. Without endangering the capacity to establish agreement, PAXOS is built to withstand a certain level of node failures.
• Stable Storage: It is expected that every node has access to reliable storage, which keeps data safe even in the event of a reboot or node crash. This ensures proper resumption following a failure and helps keep important information required for the consensus process.
• No Byzantine Failures: PAXOS assumes no Byzantine failures, in which nodes deliver false or inconsistent signals. Byzantine Paxos and other variants serve this goal, but they are more sophisticated and cannot tolerate Byzantine failures since they undermine consensus.

PAXOS operates on an unexpected network with nodes that fail but are not malicious.

You can also read What is Hyperledger Sawtooth Blockchain Applications

Roles in PAXOS

Different nodes in the network, often known as replicas, serve three different roles in PAXOS:

• Proposer: A node that puts up a value to start the consensus process. This number could be anything from a setting modification to a fresh data entry. Clients submit requests (values) to proposers, who then attempt to persuade acceptors to accept the value. They can participate in the election of leaders as well.
• Acceptor: An entity that takes part in the consensus process by reacting to proposers’ suggestions. Acceptors are essential for confirming ideas and guaranteeing consensus. Reaching a majority consensus is the foundation of their decision-making process. An acceptor’s answer signifies their support for a specific proposition.
• Learner (Optional): a node that eventually discovers the chosen value after watching the consensus process. Each node in the network has the ability to learn. All participating nodes hear the learners’ announcement of the result.

The service that needs consensus frequently coexists with a single node that can function as a proposer, acceptor, and learner in practice.

You can also read Intel Software Guard Extensions SGX In Blockchain Technology

How the PAXOS Consensus Algorithm Works

Despite its many modifications, PAXOS is a complicated algorithm that essentially uses a two-phase procedure. The fundamental procedure entails message exchanges, which are frequently started by a proposer and approved by acceptors.

Prepare Phase (Making a Proposal)

• To start the process, a proposer sends a “prepare” message to each acceptor node along with a unique proposal number, sometimes referred to as a ballot. Ballots can be arranged chronologically because they are unique identifiers that are frequently based on a timestamp, random bit sequence, and machine ID.
• Using the proposal number as a reference, this message asks if the acceptors have already accepted a value for the same round.
• When an acceptor receives a proposal, it looks at the number of proposals it has seen before and compares them. If it has more proposals than it had in the past, it accepts the new one. Whether it accepted or rejected, the highest number of proposals it has ever seen, and any values it has already accepted from other proposers will all be mentioned in the acceptor’s response.
• If a ballot is older than one they already know, replicas won’t save it.

Promise Phase

• The “promise” message that acceptors reply with states that they will not accept proposals with a lower number (proposal ID) than the one they have just received.
• A value is included in an acceptor’s response if it has already been accepted for the same round (perhaps from a prior proposal). The proposer needs this information in order to recognize any current consensus processes or possible conflicts.
• If there are not a majority of replica responses, the coordinator (proposer) declines to move further. The coordinator must be informed of the most recent modifications before proposing a new one, and this majority rule guarantees that only one transaction is altering data at a time.

You can also read EOA Meaning Blockchain: An Externally Owned Accounts

Accept Phase (Accepting a Value)

• The proposer sends the suggested value along with a “accept” message to the nodes based on the promises received. The suggested value and any previously accepted values discovered during the promise phase are included in this message, which enables all nodes to become aware of the proposed value and any potential conflicts.
• The proposer waits for the majority of acceptor nodes to respond.
• The value is deemed accepted by the proposer if the majority of acceptors reply with a guarantee that they haven’t accepted a different value for the round. This shows that the suggested value has gathered enough support to be regarded as the value that was agreed upon.
• After most copies have accepted and maintained the new row in their stable storage, the coordinator gives them instructions to apply the modification to the base table.

Learning the Decided Value

• The decided value can be learnt by learners by passively observing the messages exchanged during the Accept phase. By keeping an eye on “Accept” signals, students can determine the value that is suggested by the majority and come to an agreement on it.
• In order to actively educate learners and guarantee quicker synchronization, proposers can also explicitly transmit “learn” messages to other nodes following the acceptance of a value.

You can also read Remote Procedure Call Explained: Calling Network Functions

Problems with PAXOS and Alternatives

Though theoretically sound, PAXOS is notoriously complex.

Complexity Issues

• Steep Learning Curve: The complexities of message exchanges, failure possibilities, and the general logic are extremely difficult to understand.
• Multiple Variations: There are multiple varieties of PAXOS, and each one makes things more confusing.
• Debugging Challenges: Because of its asynchronous message flow and distributed architecture, PAXOS implementations are challenging to debug. Paxos’ concept may be useful for proving theorems, but the practical implementations differ so much that the proofs are not really useful, according to the Raft inventors.

Performance Issues

• Message Overhead: Because PAXOS depends on several stages of message exchange, there is a considerable message overhead, particularly in large distributed systems.
• Latency Issues: The consensus process may take longer on asynchronous networks due to delays, which could affect system performance as a whole.
• Scalability Concerns: The system’s applicability for very large-scale deployments may be limited as the communication overhead becomes a bottleneck as it grows.

You can also read Distributed Consensus Blockchain Importance And Challenges

Practical Use and Alternatives

• In many real-world distributed systems, PAXOS has not been widely adopted due to its complexity.
• Raft is a well-known substitute that seeks to accomplish comparable outcomes with a more straightforward design and superior performance features, drawing inspiration from PAXOS. Raft prioritises readability and uses a leader-based methodology, which streamlines communication and the entire flow in contrast to PAXOS’s decentralised methodology.
• Simpler crash fault-tolerant algorithms like Raft were developed as a result of PAXOS’s complexity, even though it has shown effectiveness in some real networks, such as Google’s Spanner.
• For example, ScyllaDB used PAXOS to provide Lightweight Transactions (LWT) at first, but is switching to the Raft protocol in order to accomplish consistent transactions without the three roundtrip performance penalty of PAXOS.

Conclusion

Notwithstanding its intricacy, PAXOS continues to be a fundamental component of distributed systems, ensuring consistent data even in unstable settings and impacting the creation of alternative consensus algorithms. Its theoretical underpinnings and fault tolerance characteristics remain useful for upcoming developments in distributed systems, and as systems get more intricate and dispersed geographically, their advantages may find new use. Both RAFT and PAXOS are mostly used in contexts with permissions, where there is little fear of malevolent users.

Note on Paxos Trust Company

It is important to note that Paxos Trust Company, LLC is a financial technology company by the same name. This company offers a range of fully-backed digital assets, including stablecoins like PayPal USD (PYUSD), Global Dollar (USDG), Lift Dollar (USDL), and Pax Dollar (USDP), as well as Pax Gold (PAXG), which is backed by actual gold. It also offers regulated blockchain infrastructure for businesses. The New York Department of Financial Services (NYDFS) oversees Paxos Trust Company, which was the first blockchain infrastructure platform based in the United States to get a significant payments institution license from the Singaporean Monetary Authority. Although it goes by the moniker “Paxos,” this business is not the same as the consensus algorithm.

You can also read What Is FBFT? Knowing Federated Byzantine Fault Tolerance