Simulation of fault-tolerant consensus algorithms in Hash
This is a simulator for consensus algorithms. This project is tied to the Bachelor-Thesis of Roy Adler at the Technical University Berlin 2022 named "Simulation fehlertoleranter Konsensalgorithmen in Hash" (Simulation of fault-tolerant consensus algorithms in Hash). It can be found under the link: https://www.overleaf.com/read/sygqyrpcscfn
3 different Algorithms were implemented:
- Multi-Ben-Or,
- Multi-Paxos and
- Multi-Raft.
All algorithms are based on their original ones named without the Multi prefix. The changes were made to make the algorithms comparable with each other.
Functional parameters
The Simulation will change based on the different values in the globals.json. The following list will give an overview of all the parameters:
algorithm
chooses algorithm to simulate.
0: Multi-Ben-Or
1: Multi-Paxos
2: Multi-Raft
3: Distribution Test Program for messageMaxDelay
numberOfAgents
defines number of agents in a simulation.
natural number
f
setups fault-taulerance of Multi-Ben-Or.
natural number
valueListSize
length of the intput list (and therefore output list) for each agent
natural number
valueIntervalSize
Input/Output value interval is between [0, valueIntervalSize], but restriction of this work is binary consensus, so it is normally set to 2.
natural number
standard: 2 (binary consensus)
acceptanceThreshold
decides how many faulty agents the gamemaster will tolerate, until it finishes a simulation
natural number
agent failure
agentDeaths
defines the agent failures in string format:
agentID1,Value1;agentID2,Value2;...agentIDn,Valuen (agentID, Value are natural numbers)
deathByStepOrRound
interpretation of value in agentDeaths.
step: value means the simulation step, where the agent failes
round: value means the global round, where the agent failes
randomDyingPercentage
percentage with wich an agent can die in a step
real number between 0 and 100
messageListRandomized
when the same messages being recieved in the same step for different agents, the order of messages is the same for every agent. If messageListRandomized is true, it shuffles the recieved messageList to simulate a different order the messages where recieved. It has the biggest effect on Multi-Ben-Or, simulated with messageMaxDelay = 0.
binary
seed
seed for pseudonumbergeneration.
string
randomScale
range of numbers generated by random function (pseudoNumberGenerator).
natural number
delayFunction
defines the distribution function (used by getMessageDelay(x) function in init.js).
lin: uniform distribution
log: logarithmic distribution
exp: exponential distribution
gaus: normal distribution
messageMaxDelay
sets the maximum delay of a message agent.
natural number
g
parameter to change the compression of the normal distribution compression.
real number
timeoutConstant
For Multi-Paxos and Multi-Raft timeouts of agents are being set in the init.js depending on messageMaxDelay and timeoutConstant. The constant adds (or subtracts) every agent the same absolute delay. This helps for some simulations where timeout isn't high enough and the agent doesn't wait long enough to recieve enought messages to procceed with the protocol.
integer
Extra
For Multi-Paxos and Multi-Raft if nothing is defined in agentDeaths, the leader that has been first chosen will stay the leader for the whole simulation. To change that or specificly test the leader election, the following parameters where implemented:
leaderDecidesOnlyOneValue
if true, after the leader decides one value it changes its role to be a follower/acceptor again.
binary
timoutChangeAfterLeaderDecided
if leaderDecidesOnlyOneValue = true, the new leader will probably be the same agent again, because either the timeout is the fastest of all agents (Multi-Raft) or the agentID is the heighest (Multi-Paxos). To prevent that, after a leader decided one value his timeout can be delayed be the here specified value to make a leaderchange possible.
natural number
Visual parameters
The visualization of the Simulation can be altered, too. This has no effect on the procedures of the consensus protocols, but only on the visuals in the 3D Viewer. The following list will give an overview of all the visual parameters:
message_distance
distance between message agents to the sending agent.
real number
Height
during the simulation different heights can describe the phase of an agent. The different heights can be setup in the following variables:
phase0Height
height for agents in phase 0. real number
phase1Height
height for agents in phase 1.
real number
phase2Height
height for agents in phase 2.
real number
phase3Height
height for agents in phase 3.
real number
objectsMaxHeight
this sets the maximum height for timeout agents and the input/output block lists. The heightest point of these agents will always be maximum the defined value in objectsMaxHeight, and every other timeout and block will be relativly scaled.
real number
Visibility
The following parameters will define, if some agents are visible or not.
hideMessages
if true: hides visually the message agents. (they still exist and work, but do not have any visualization)
binary
hideTimouts
if true: hides visually the timeout agents.
binary
showInputblocks
if true: shows the towers of input values behind the agents.
binary
Colors
The agents have different colors based on their role. All the role colors can be setup in the follower parameters:
color0
standard: "blue"
color1
standard: "yellow"
color2
if valueIntervalSize = 3, the color for the third value x=2 is exemplary defined in this value.
standard: "#123944"
colorDead
standard: "black"
colorUnkown
standard: "red"
colorCandidateProposer
standard: "pink"
colorLeader
standard: "purple"
colorFollower
standard: "green"
colorDivider
standard: "black"
Run the simulation
Click the Play button or the Step Simulation button in the bottom right under the viewer. Click reset to reset the simulation to the initial state.