Skip to content

Latest commit

 

History

History
115 lines (94 loc) · 5.09 KB

Readme.md

File metadata and controls

115 lines (94 loc) · 5.09 KB
Raw

Introduction

  • Paxos is a distributed consensus algorithm that allows a group of processes (or nodes) in a network to agree on a single value despite the presence of faults or failures.

  • Paxos algorithm ensures that a single value is chosen and that any proposed value is chosen as the final value, only if a majority of processes agree. It also guarantees that if a value is chosen, it will be the same value chosen by any other correct process that starts the Paxos protocol.

This implementation is Binary Value & Synchronous version of Paxos Consensus. Which means all nodes will move together. A multiprocessing barrier will handle that. And the proposed value will be binary (0 or 1).

Plus, this Paxos version will satisfy following properties:

  1. ✅ Agreement: If multiple rounds result in decisions, decided values must be the same.
  2. ✅ Validity: Any decided value must be one of the values provided by the clients.
  3. ❌ Termination: All nodes must eventually terminate. (In this implementation, termination will not be guaranteed again since it will allow any number of nodes to fail at anytime.)

Specs

  • This implementation is using python's multiprocessing library to simulate a network of nodes as processes.
  • Processes can communicate using ZMQ sockets (PULL-PUSH)
  • Each process creates N+1 many sockets.
  • 1 socket will be PULL socket for receiving any messages coming from other nodes.
  • N sockets will be PUSH sockets for broadcasting message in the network.
  • Crash of a node is simulated as a node sending "CRASH" message with a probability, instead of a node is literally crashing.
  • In each round, the node that satisfies the condition roundNumber % numProc = nodeID will be proposer of this round.

An example of ZMQ socket pipelining can be shown as folows: image

There are 2 phases in this implementation:

  1. START-JOIN phase
  2. PROPOSE-VOTE phase

START-JOIN Phase

  • Proposer of current round will broadcast "START"
  • Other nodes will respond "JOIN " with crash probability.
  • If joining nodes constitute majority, then proposer will move to PROPOSE-VOTE phase.
  • Else, it will broadcast "ROUNDCHANGE". Then everybody will move to the next round and a new proposer will do the same thing.

PROPOSE-VOTE Phase

  • If there is a value decided in the end of previous rounds, proposer will propose this value again, by sending "PROPOSE <max_value_from_previous_rounds"
  • Else, proposer will propose a new value for the first time in the network. It will propose 0 or 1 because of Binary Consensus.

How To Run?

Command line arguments will be:

python paxos.py <numProc> <prob> <numRounds>

numProc: Number of nodes in the network prob: Probability of crash of a node numRounds: Number of rounds that paxos will be applied in.

Example Run

python paxos.py 4 0.1 1

NUM NODES: 4 , CRASH PROB: 0 . 1 , NUM ROUNDS: 3
ROUND 0 STARTED WITH INITIAL VALUE: 1
LEADER OF 0 RECEIVED IN JOIN PHASE: START
ACCEPTOR 2 RECEIVED IN JOIN PHASE: START
LEADER OF 0 RECEIVED IN JOIN PHASE: JOIN −1 None
ACCEPTOR 1 RECEIVED IN JOIN PHASE: START
LEADER OF 0 RECEIVED IN JOIN PHASE: JOIN −1 None
ACCEPTOR 3 RECEIVED IN JOIN PHASE: CRASH 0
LEADER OF 0 RECEIVED IN JOIN PHASE: CRASH 0
LEADER OF 0 RECEIVED IN VOTE PHASE: PROPOSE 1
ACCEPTOR 1 RECEIVED IN VOTE PHASE: PROPOSE 1
ACCEPTOR 2 RECEIVED IN VOTE PHASE: PROPOSE 1
ACCEPTOR 3 RECEIVED IN VOTE PHASE: PROPOSE 1
LEADER OF 0 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 0 RECEIVED IN VOTE PHASE: CRASH 0
ROUND 1 STARTED WITH INITIAL VALUE: 1
LEADER OF 0 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 0 DECIDED ON VALUE: 1
ACCEPTOR 3 RECEIVED IN JOIN PHASE: START
ACCEPTOR 0 RECEIVED IN JOIN PHASE: START
ACCEPTOR 2 RECEIVED IN JOIN PHASE: START
LEADER OF 1 RECEIVED IN JOIN PHASE: START
LEADER OF 1 RECEIVED IN JOIN PHASE: JOIN 0 1
LEADER OF 1 RECEIVED IN JOIN PHASE: JOIN 0 1
LEADER OF 1 RECEIVED IN JOIN PHASE: JOIN 0 1
ACCEPTOR 0 RECEIVED IN VOTE PHASE: PROPOSE 1
ACCEPTOR 2 RECEIVED IN VOTE PHASE: PROPOSE 1
ACCEPTOR 3 RECEIVED IN VOTE PHASE: PROPOSE 1
ROUND 2 STARTED WITH INITIAL VALUE: 1
ACCEPTOR 0 RECEIVED IN JOIN PHASE: START
ACCEPTOR 3 RECEIVED IN JOIN PHASE: START
LEADER OF 2 RECEIVED IN JOIN PHASE: START
LEADER OF 1 RECEIVED IN VOTE PHASE: PROPOSE 1
LEADER OF 2 RECEIVED IN JOIN PHASE: JOIN 1 1
LEADER OF 2 RECEIVED IN JOIN PHASE: JOIN 1 1
LEADER OF 1 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 1 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 1 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 1 DECIDED ON VALUE: 1
ACCEPTOR 1 RECEIVED IN JOIN PHASE: START
LEADER OF 2 RECEIVED IN JOIN PHASE: JOIN 1 1
ACCEPTOR 1 RECEIVED IN VOTE PHASE: PROPOSE 1
ACCEPTOR 3 RECEIVED IN VOTE PHASE: PROPOSE 1
ACCEPTOR 0 RECEIVED IN VOTE PHASE: PROPOSE 1
LEADER OF 2 RECEIVED IN VOTE PHASE: PROPOSE 1
LEADER OF 2 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 2 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 2 RECEIVED IN VOTE PHASE: VOTE
LEADER OF 2 DECIDED ON VALUE: 1