Code Monkey home page Code Monkey logo

shobhitk18 / basic-paxos-optimisation-and-verification Goto Github PK

View Code? Open in Web Editor NEW
0.0 1.0 0.0 410 KB

This project aimed at extending the original Paxos implementation specified by Lamport into a version with preemption. As part of this project I also added correctness testing to check that executions with both the original and the extended versions are correct. I measure the running times to learn a consensus value under varying values of 3 parameters: message loss rate, message delay, and wait time before a new round.User can configure the setup by passing arguments to the run.py file for various runs.

Python 100.00%
distributed-consensus optimization paxos multi-paxos

basic-paxos-optimisation-and-verification's Introduction

Project Description:

We will study optimizations of both Basic Paxos and Multi-Paxos. The goal is to better understand these algorithms.


1. Consider Basic Paxos as described using itemized steps by Lamport in his "Paxos made simple" paper.

(1) What liveness problems does the algorithm have? 

(2) What are possible methods for solving them?


2. Consider Multi-Paxos as described in pseudocode by van Renesse in his "Paxos made moderately complex" paper.

(1) What performance problems does the algorithm have? 

(2) What are possible methods for solving them?


3. Take the DistAlgo program for Lamport's Basis Paxos (under da/examples/lapaxos at http://github.com/DistAlgo/distalgo)

(1) Extend it into a version with preemption. You need to add correctness testing to check that executions with both the original and the extended versions are correct. There is no point to have a more live or faster program that is not correct.

(2) Measure the running times to learn a consensus value under varying values of 3 parameters: message loss rate, message delay, and wait time before a new round. You need to select the appropriate ranges of parameter values and their combinations to obtain interesting results.

Remember that, for performance evaluation, your measured results depend on the machine capacity you use. So do the ranges and combinations of parameter values.

Also, the running times (both elapsed time and total CPU time) should be averaged over a number of repeated runs. Here, you should report the range and standard deviation too because the variation is expected to be large.


Your program:

Your program must run under Python 3.6.5 or higher. Your main program must be named "main.da", and must run with a command like the following, where

"p", "a", "l" are the number of proposers, acceptors, and learners, respectively,
"n" is the number of repetitions for each run,
"r" is the message loss rate, between 0 for 0% loss and 1 for 100% loss,
"d" is the message delay, up to the number of seconds specified,
"w" is the wait time, in seconds, before trying a new round,
"tp" and "tl" are the timeout, in seconds, by proposers and learners, respectively, when timeout is used.

python.exe -m da main.da p a l n r d w tp tl

and do the following:

(1) run both versions of Basic Paxos;

(2) report the running times, ranges, and standard deviations, for each of them.

For selecting the argument values: "p", "a", "l" are usually 3, or occasionally 5; and "n" is better at least 10 or more.

You should specify several combinations and ranges of "r", "d", "w", "tp" and "tl", and report the resulting curves or trends for varying each of them. For example, you can provide a combination of all argument values where "r" varies over 5 different values. Generally, you want to vary the values of one parameter at a time.

You have the freedom to decide what additional information to report and what table and/or figure format to use.


Solution:

Project Directory: /

Source Files

1. controller.da:
	I have made use of the controller class to get the performance characteristics for my task
2. orig.da
	This file contains the original Basic Paxos implementation 
3. orig_extended.da
	This file contains the 'PreEmpt' implementation on top of Basic Paxos

4. run.py
	This file implements the testing code which runs various permutations of values for
	Loss rate, Message delays , Wait Delays, generates output files and plot graphs.User
	run the following command from inside the project directory to generate the outputs. 
	COMMAND: python run.py

Output:

There are two output folders:
1. Analyze: 
	This folder will contain the performance data for any particular combination over n iterations.
2. Output_Orig:
	The folder will contain the output data in the form of both csv file and graph which is averaged over n iterations
	Therefore it will contain entries like Avg , Standard Deviation and ranges. Along with Timeout and Correctness results
	In order to capture Timeout and correctness data for a batch of n iteration, I am keeping a threshold of 50% for both of
	them for reporting my
3. Output_Extended:
	This folder contains the output files and graphs for the runs done on orig_extended.da.

*******************************************************************************************
Note: PLEASE DON'T REMOVE THE FILE "temp.csv" GENERATED DURING THE RUN


#************************PREEMPT_CHANGE************************************

# Adding condition to break out of the await when receive a preempt with a proposal
# number value greater than the one on which the proposal is currently waiting to get
# a response
# Line 35:
     	elif some(received(('preempt',val), from_=a), has= val > n):
            n = val
# Getting the maximum proposal number which the acceptor has accepted and sending that
# proposal number back to the proposer with a 'preempt' tag
# Line 85:       
	else:
            preempt_n = max(setof(n2 , sent(('respond', n2, _))))
            send(('preempt', preempt_n), to =p)


#************************CORRECTNESS VERIFICATION***************************
# The decision about correctness is made on two criteria:
# 1. If there is a Timeout with any of the learner, then no learner should 
# learn any value.
# 2. In case of no Timeout with any of the learners, there should be a unique 
# value that must be learnt by all the learners.





********************************Observations**************************************
1.As the loss rate goes above 0.5 the system is mostly timing out due to not able to achieve consensus
The preempt allows the proposer to send another proposal without waiting for the timeout whereas the 
Orig code waits for the entire timeout duration which can one seen from the graph.

********************************************************************************************
References:
1.	https://github.com/DistAlgo/distalgo/blob/master/da/examples/lapaxos/orig.da
2.	https://arxiv.org/pdf/1704.00082.pdf
3.	https://github.com/DistAlgo/distalgo/tree/master/benchmarks/lapaxos					         	   
********************************************************************************************




***********************************************************EOF***********************************************************


basic-paxos-optimisation-and-verification's People

Contributors

shobhitk18 avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.