Tips to understand Paxos

author-image
CIOL Bureau
Updated On
New Update

BANGALORE, INDIA: Paxos is a protocol for achieving consensus in a distributed system. Consensus is an important problem in distributed systems. By consensus, we mean agreeing on a single outcome and Paxos is an algorithm that helps in reaching an agreement for a single value at any point in time.

Advertisment

The world today is abound with several varieties of distributed systems, the Facebook servers, Twitter systems and the new breed of cloud computing systems like Windows Azure, Google AppEngine and Amazon Elastic Cloud are just a few examples wherein large scale distributed systems and architecture are deployed. Central to these systems are several class of algorithms which when implemented produce a single system consisting of a massive collection of computing nodes which is not only scalable, but self reliant, fault tolerant and also highly available.

In a distributed system, an individual functional entity- for example a file is distributed across a set of nodes. Distribution increases availability, fault-tolerance and also helps in balancing loads. But mere distribution is not enough to build a completely reliable system. To understand the problem of consensus and why it is required, let us think of distributing a single variable across a set of nodes. Several distinctive clients, each a different process, are interested in updating this single variable.

Clearly, since the request for updates is from several places and there is no direct control on ordering of the updates, the single variable in question loses the ability to maintain consistency, resulting in unpredictable results. Consensus algorithms help in alleviating problems of such kind by automatically ordering the set of updates even under worst conditions of network failure or when processes die unexpectedly so that updates occurring to a single variable distributed across the set of nodes all appear same.

Advertisment

Paxos was originally proposed by Leslie Lamport. He is one of the forerunners in the areas of distributed system and to his credit lies several different algorithms distributed system related to Time and Clocks, Byzantine Fault tolerance, consistency, and snapshots among others. He is also particularly noted for his contribution to LATex. Paxos was invented while he was on in his vacation in the beautiful Greek inland, Paxos and the original paper actually is a description of a parliament session organized by a lost civilization.

The characters in the papers are named after several computer scientists and depicted in a humorous way, unlike other serious computer science papers. It is however filled with complex maths and only after several years people started showing interest in this seminal work.

{#PageBreak#}

Advertisment

Consequently, Lamport wrote one more paper titled 'Paxos Made Simple' and explained the core ingredients of the algorithm using every day English and minimalistic proof. In this article, we will try to understand what Paxos is all about and what the different varieties of Paxos that exists today are. And to do so we will proceed incrementally; understanding the simplest problem first and then gradually deep dive into the complexities that a distributed system poses. But before we move ahead, there are a few set of terminologies that we have to learn.

In Paxos, there are three prominent and different kinds of roles: 'Proposer', 'Acceptor' and 'Learner'. A Proposer proposes a new value, Acceptors accept the value sent by the Proposer or reject it and Learner simply learns from the acceptor that a new value is accepted.

In most cases, however, the three roles as defined may not be separate processes in different machines but rather separate processes in the same machine. For example, acceptors may be learners as well and acceptors can be proposers also. In case of latter, this means that updates may arise from multiple different locations and the consensus algorithm some how has to select one among many.

Advertisment

Apart from these roles, there is yet another role known as a 'leader'. A leader is a distinguished entity whose primary job is to act as a point of contact for other members of the same community and responsible for accepting, informing and executing instructions. For example, in case of a leader of the proposer community, it is the responsibility of the leader to choose the update among the set of updates received to the set of proposers and inform the acceptors.

Similarly, in case of the learning community, a leader may be the sole point of contact which first receives an instruction to learn and subsequently convey it to its group members. Though, leadership brings about an aura of Server Centric computing but designers often choose to have leaders to reduce the complication of involving multiple partners of equality.

Further, leaders are selected or elected by an election mechanism where participating members select one among a few based on some known criteria. We will not jump into this topic as this itself is a significant topic on its own and calls for a separate publication.

Advertisment

Click here to read more!

tech-news