tag: Subject/Distributed-System

Notes Dynamo is similar to a Distributed Hash Table meaning it uses consistent hashing. Dynamo is called a zero-hop DHT because each node has enough information about the whole consistent hashing ring that it can directly transfer any client to the server responsible for serving that key. Causes for the system not being linearizable Initializing replication factor but not having the same number of writes/reads Membership changes Discovery of membership changes is at different times, due to gossip protocol, causing writes to happen at different servers than intended. When key exchanges are happening and data is being written to the old server. Vector Clock

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. S1, S2, S3 are normal servers and S4 is a malicious one. Let’s say S1 prepares and accepts a value with itself S1, S3 and S4. v1 is decided for number 1. S1 goes down and S2 comes up. S2 tries to prepare a new number and receives 1,v1 from S3 but 2,v2 from S4. How do you decide which is the correct value? We outvote it meaning we’ll have to increase number of good servers. ...