Paxos Demo

This Paxos demo is intended for learning purposes. This Paxos cluster has 5 nodes, which only has the capability to write one value once, and all subsequent queries must be reads. Figuring out how to extend the algorithm to support storing multiple key-value pairs, override an existing value, and other features are left as an exercise to the reader. This implementation is based on the algorithm described in the Paxos Made Simple paper. The source code for this project can be found here.

How to use

The cluster starts uninitialized with no value. To begin the process of writing a value to the cluster, click the "Initiate Paxos" button on any of the 5 nodes. Think of this as you sending a request to that particular node to write a value.

The algorithm is done when the node's learner component's LV (learned value) field is populated. After that, no more values can be successfully written, and any more writes you attempt to do will actually be the node reading the value from the cluster.

Nodes

Each node is made up of 3 components: the Proposer, the Receiver, and the Learner.

Proposer

The proposer is the initiator of writes. It proposes a value for itself and other nodes in the cluster to accept. When you send a node a write request, a proposer state gets initialized (in pink). Then, the proposer sends a request to each of the other nodes in the cluster. The proposer state is composed of the following parts:

• PN (proposal number): the "id" associated with the write/proposal request. Higher ids take precedence over lower ids.
• PV (proposed value): the value that is being proposed.
• responses: how many responses the proposer has received from its proposal request. The proposer needs at least a majority of all nodes to accept its proposal request (so, itself and 2 of the other 4 nodes).
• phase: the current phase of the Paxos algorithm the proposer is in. There are 2 phases: the Prepare phase and the Accept phase.

Receiver

The receiver is responsible for handling proposer requests. The receiver state (in green) is composed of the following parts:

• promised PN (promised proposal number): the "id" that the receiver has promised to honor. The receiver will always honor the request with higher proposal number.
• accepted: the value that the receiver has accepted. When a node (learner) learns that a majority of the nodes (receivers) have accepted a certain value, then the node (learner) is certain that the value is the cluster's value.

Learner

The learner's job is to read the value from the cluster. The learner state (in yellow) is composed of the following parts:

• responses: how many responses the learner has received. The learner needs a majority of nodes to respond before making a judgement on what the cluster's value is.
• LV (learned value): what the node thinks the cluster's value is (and the node will always be correct, assuming there are no bugs)

Messages

When a node sends a message/request to other nodes, you'll see messages appear to the right of the nodes. These are "in-flight" messages (haven't reached the target node yet). You can choose to either deliver the message, or drop the message to simulate a network error.

DEMO:

Legend

Colors (for nodes)

• Pink = proposer
• Green = receiver
• Yellow = learner

Abbreviations

• PN = Proposal Number
• PV = Proposed Value
• LV = Learned Value

FAQs

Why does the proposer node instantly receive 1 response even though I haven't "delivered" any messages yet?

The proposer node automatically receives the message that it sends itself!

After I successfully write a value, why does writing another value not work?

It's not supposed to work. After you successfully write the first value, the cluster will stay consistent with that one value forever, and subsequent "writes" that you try to do are actually reads.