What are the fault tolderant consesnsuses?
- Practical Byzantine Fault Tolerance: Needs at least 3f + 1 nodes with f faulty nodes
- Paxos, Raft: Need at least 2f + 1 nodes with f faulty nodes
Properties of consensus protocols?
- Safety: never return an incorrect result
- Availability: able to provide an aswer if n/2 + 1 servers are operational
- No clocks: Do not depend on RTCs to work
- Immune to stranglers: if n/2 + 1 nodes vote, the restult is considered safe
What are the roles in Paxos?
- Proposer: chooses a value or receives it from a client and sends it to acceptors to collect votes
- Acceptor: votes to accept or reject the values proposed by the proposer, for fault tolerance, the algorithm requires a majority or acceptors
- Learner: adopts the value when a large enough number of acceptors have accepted it
What are the phases of Paxos?
Voting: Preparation, Promise
Replication: Accept, Accepted
What is the Preparation phase in Paxos?
A proposer selects a proposal number n and sends a “prepare” request to acceptors
What is the Promise phase in Paxos?
- If n is higher than every previous proposal number, the acceptor returns Promise to the proposer, and ignores all future proposal numbers less than n
- If the acceptor accepted a proposal at some point in the past, it must include the previous proposal number m and the corresponding accepted value w in the reponse to the proposer
What is the Accept phase in Paxos?
If the proposer received a response from the majority of acceptors, it sends an accept request for a proposal numbered n, the highest numbered proposal among the responses
What is the Accepted phase in Paxos?
If an acceptor received an accept request for proposal numbered n, it accepts the proposal unless it has already reponded to a prepare request having a number greater or equal than the proposal number.
What is the main idea behind Raft?
It separated leader election and log replication states. When crashes are detected, choose new leader. The leader accepts commands from clients, and appends to its log. Then, it replicates its log to other servers.
What are the roles in Raft?
- Candidate: candidate for being a leader asking for votes
- Leader: accepts log entries from clients, replicates them on other server
- Follower: replicates the leader’s state machine
How does Log Replication work in Raft
- Each log has an index identifying its position in the log
- The leader sends append_entries message to append an entry to the log
- A log entry is committed once the leader that created the entry has replicated it on a majority of the servers
What is the main difference between the purpose of Paxos (+Raft) and Byzantine
Paxos and Raft assume the messages are valid and true (aka there are no malicious parties)
