Skip to content
/ paxos Public

Python implementation of Synchronous Paxos Algorithm which aims to solve Single Value Distributed Consensus Problem (with ZMQ socket programming).

Notifications You must be signed in to change notification settings

alperari/paxos

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

21 Commits
 
 
 
 
 
 
 
 

Repository files navigation

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

About

Python implementation of Synchronous Paxos Algorithm which aims to solve Single Value Distributed Consensus Problem (with ZMQ socket programming).

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages