Notes Consistency is a spectrum with weak to strong levels.
GFS/Eventual consistency is an example of weak consistency.
Linearizability is an example of strong consistency.
Consistency can be defined as the following properties:
Completion to Invocation(C2I) Globally Locally Sequential ordering If all of these properties are satisfied then the system is linearizable. If only local C2I and sequential ordering is guaranteed then the system is sequential consistency(second strongest consistency model). Sequential consistency is the one being used in x86 CPUs’ memory model....
Readings - Practical Byzantine Fault Tolerance.pdf Byzantine PAXOS.pdf
Notes What can be potential byzantine failures? Wrong replies which cannot be detected Halt consensus(same as crash so not really byzantine) Internal state mismanagement(same as crash) Forgery(Use public/private keys to encrypt data) Converting paxos to byzantine paxos Strategy 1(Outvoting) Increase the number of servers and increase quorum requirement to N = 3f + 1, Q = 2f + 1 Normal paxos wouldn’t work where let’s say- Thought process of increasing servers: There are 4 servers....
Notes Background Already existing scheme used db query for replication Replication scheme was in such a way that any follower could query any other follower Due to this when they tried to implement RAFT there was a mismatch between the architecture and algorithm. So they decided to change the algorithm to implement in existing architecture.
Problem Querying will not give you the term number meaning you don’t know if you’re pulling from the leader or not and if the log entries are correct or not....
Notes Runs in 2 phases -
Phase 1 - get a promise from majority of servers Phase 2 - get a majority of servers to commit Two important rules Two numbers should be used to track the system Highest seen Highest accepted Majority will only happen if the values getting selected are happening at the same number It can’t be that one value got accepted at 1,v1 and another got accepted at 3,v1....
RAFT Notes What kind of system is RAFT? Exactly once/At least once/ At most once? Two ways to approach this:
Application layer is responsible for de-duplication and the command is just appended (albeit with the same ID). Consensus layer(RAFT) is responsible for checking duplicates. Let the client handle ID generation instead of servers.
PAXOS Notes Majority concept is for making sure that two different groups of systems cannot reach different consensus as two majorities will always overlap....