Distributed Decision Making

Question 1

What are the fault tolderant consesnsuses?

Answer 1

• 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

Question 2

Properties of consensus protocols?

Answer 2

• 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

Question 3

What are the roles in Paxos?

Answer 3

• 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

Question 4

What are the phases of Paxos?

Answer 4

Voting: Preparation, Promise
Replication: Accept, Accepted

Question 5

What is the Preparation phase in Paxos?

Answer 5

A proposer selects a proposal number n and sends a “prepare” request to acceptors

Question 6

What is the Promise phase in Paxos?

Answer 6

• 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

Question 7

What is the Accept phase in Paxos?

Answer 7

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

Question 8

What is the Accepted phase in Paxos?

Answer 8

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.

Question 9

What is the main idea behind Raft?

Answer 9

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.

Question 10

What are the roles in Raft?

Answer 10

• 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

Question 11

How does Log Replication work in Raft

Answer 11

• 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

Question 12

What is the main difference between the purpose of Paxos (+Raft) and Byzantine

Answer 12

Paxos and Raft assume the messages are valid and true (aka there are no malicious parties)