Distributed Prime Number Detection System using Consensus for Paxos

Paxos algorithm is used to achieve consensus among a distributed set of computers that communicate via an asynchronous network.

We will understand the Paxos Algorithm by taking a simple problem such as detecting Prime Numbers in a distributed environment.

In order to start the consensus, first, we need to have a coordinator node in our cluster. It is explained in my previous article how can we decide the master node in a distributed environment using the Bully Algorithm. You can check that here.

Once the master node is decided, it starts its work as described below.

• Firstly master node checks the service registry and figures out the active nodes in the cluster.
• In Paxos algorithm, there are a set of three roles which are proposers, acceptors, and leaners. Proposers provide values to the acceptors. Acceptors reverify the values and send them to the learners. Based on the answers learners decide what should be the final outcome.

Usecase: We are going to decide a given number is prime or not in a distributed manner. We have a file that contains a set of numbers which are both prime and non-prime.

Role of the master node

• In this system, we have 2 acceptors and 1 learner. The rest of the nodes are proposer nodes.
• Once the master node checks the active nodes from the service registry, it decides which are the proposer nodes, acceptor nodes, and the learner node. Then these nodes will be informed about their role. Each node has an API exposed to accept POST request to get to know about their roles such as, http://localhost:port/acceptor, http://localhost:port/learner, http://localhost:port/proposer.

• Then the service registry will be updated by each node.
• Then the master node will randomly pick a number from a file and decide the workload for proposers. As an example, if the number is 49627, and assume if there are 4 proposers, the range will be divided to equal 4 ranges.

Prime Number is a number that is divisible only by itself and 1. In this implementation, if our number is 49627, it needs to be divided from 2 to 49627 to decide if it is a prime or not. This division work will be divided among proposer nodes.

Dividing ranges are as below for proposers.

• Proposer 1: 2 to 12408
• Proposer2: 12409 to 24815
• Propsoer3: 24816 to 37222
• Proposer4: 37223 to 49629

And these ranges will be communicated to the respected proposer node.

• Then the master node tells the learner node how many proposers exist in the cluster. This information is needed for the learner to five the final outcome and for the algorithm to terminate.

Role of the Proposer nodes

• Once the proposer nodes receive the schedule from the master, they will start dividing the number from the numbers in their range. It will be done by the following API.

Below is the logic to decide the Prime Number.

Once the division is done by each node, they will identify the acceptors from the service registry. Then the result of the each node will be sent to a random acceptor that they pick.

• If the number is divided by a certain number, it will send a message saying “Number is not prime, the number is divisible by XYZ number”
• If the number is not divisible by any of the numbers in their range, they will send a message as “The number is Prime”.

Role of the Acceptors

• The acceptor receives the messages from Proposers.
• If the acceptor gets a message saying the number is not prime, it needs to divide and reverify and check the validity of the message. If the response is valid it will send to the learner that the number is not prime.
• If the acceptor gets a message saying that the number is prime, it would not verify this and will assume the proposer was telling the truth and would send a message to the learner saying that the particular number is prime.
• The result will be sent to the learner.

Role of the Learner

• The master node will tell how many proposers are there in the cluster.
• The leaner will count the number of messages from the acceptors.
• If there is even one message saying it is not prime, the leaner will decide that the number is not prime.
• If all the nodes say it is prime, the learner will decide that the number is prime.

The complete implementation for the master election algorithm and the consensus for Paxos can be found here.

To run the project, you can find the instructions here.