Consensus

Question 1

What are the types of unreliability in distributed systems?

Answer 1

Link failures, processor crashes, and Byzantine failures.

Question 2

What is a link failure?

Answer 2

A link failure occurs when a communication link becomes inactive, potentially disconnecting the network and causing messages to not be delivered.

Question 3

What is a processor crash?

Answer 3

A processor crash happens when a processor stops functioning and disappears from the network, ceasing to send or receive messages.

Question 4

What are Byzantine failures?

Answer 4

Byzantine failures involve processors sending arbitrary or misleading messages, making consensus difficult. Named after the Byzantine Generals problem.

Question 5

What is the Byzantine Generals problem?

Answer 5

A problem illustrating the difficulty of reaching consensus with unreliable communication, where generals must agree to attack but messages may fail to deliver.

Question 6

What are the properties of the consensus problem?

Answer 6

Validity, Agreement, Termination, and Integrity.

Question 7

What is the Validity property in consensus?

Answer 7

Any value decided must be a value proposed. If all processes start with the same value, that value must be the one decided.

Question 8

What is the Agreement property in consensus?

Answer 8

No two correct processes decide differently. All non-faulty processes must agree on the same value.

Question 9

What is the Termination property in consensus?

Answer 9

Every correct process eventually decides. The algorithm must ensure that all processes reach a decision in a finite amount of time.

Question 10

What is the Integrity property in consensus?

Answer 10

No process decides twice. Once a process decides on a value, it cannot change its decision.

Question 11

Is consensus possible in asynchronous systems with failures?

Answer 11

No, it is impossible to reach consensus in asynchronous systems with even a single failure (link, crash, or Byzantine).

Question 12

Is consensus possible in synchronous systems with failures?

Answer 12

Yes, in synchronous systems, consensus can tolerate crash and Byzantine failures, but not link failures.

Question 13

What is a simple algorithm for consensus?

Answer 13

Each processor broadcasts its input to all processors and decides on the minimum value. Works in a single round if there are no failures.

Question 14

Why does the simple consensus algorithm fail with crash or link failures?

Answer 14

If a processor crashes or a link fails, not all values are broadcast, leading to inconsistent decisions.

Question 15

Why does the simple consensus algorithm fail with Byzantine failures?

Answer 15

Faulty processors may send arbitrary values, violating the validity property.

Question 16

What is an f-resilient consensus algorithm?

Answer 16

An algorithm that can tolerate up to f crash failures, requiring f+1 rounds of information exchange.

Question 17

How does an f-resilient consensus algorithm work?

Answer 17

Processors broadcast their values in each round, and after f+1 rounds, they decide on the minimum value received.

Question 18

Is consensus possible with Byzantine failures if more than one-third of processors are faulty?

Answer 18

No, no f-resilient algorithm exists for n processes if more than one-third of the processors are Byzantine.

Question 19

What is the role of blockchains in consensus?

Answer 19

Blockchains provide a decentralized and fault-tolerant way to achieve consensus, suitable for applications requiring high reliability, such as financial transactions.