Consensus Protocols

Question 1

What is Consensus in Distributed Systems?

Answer 1

-Multiple processes work together to achieve a common goal.
-Consensus refers to the process of reaching an agreement among processes.
-This often involves coordination to ensure that all processes agree on certain values or decisions during computation.
-Processes typically propose candidate values, communicate with each other to exchange information, and eventually agree on a single value that satisfier the consensus criteria.
-Consensus protocols must tolerate faults to ensure agreement despite failures.

Question 2

What are some Consensus Algorithms?

Answer 2

-Blockchain Technology
-Distributed Databases
-Cloud Computing

Question 3

What do consensus algorithms assume?

Answer 3

-N processes
-Reliable network communication, messages are received in the order they were sent
-Synchronous or asynchronous communications
-Must tolerate: process crash failures, byzantine failures, faulty processes

Question 4

What are some consensus requirements?

Answer 4

-Termination: Eventually every correct process sets its value or perform an action.
-Agreement: All correct processes must decide on the same value or perform an action.
-Integrity: -If all correct processes propose the same value/action, then any correct process that has decided must choose that value/action.

Question 5

How can we combine Consensus and Total Ordering Multicast?

Answer 5

1. Each process can propose its value for consensus and multicast it using total-order multicast to all other processes.
2. Upon receiving proposals, each process can compare the proposed values and attempt to converge towards a single value based on certain rules or conditions. All processes receive the same proposals in the same order, ensuring that they have a consistent view of the proposed values.
3. Through repeated rounds of proposal and communication, processes can converge towards a consensus value that satisfies the criteria of the consensus problem.

Question 6

How do you deal with Crash Failures in Synchronous Systems?

Answer 6

Initial Step :
1. Each process Pi proposes a candidate value vi
2. Each process multicasts their candidate value
3. Each process pi maintains a set of values Vi known to it at round r.
In round r:
1. Each process multicasts any new values they recorded in the previous round.
2. Each process receives multicast messages and records them in Vi r+1.
Final round:
1. Choose vi based on selection criteria.

Number of rounds required depends on the number of crash failures (e.g if we expect F processes to crash we need at least F+2 processes, F+1 rounds)

Question 7

What are some good Consensus solutions for asynchronous systems?

Answer 7

1. Replicating data: Paxos and Raft
2. Distributed transactions: Two-phase commit for atomicity