13 - consesus Flashcards
Quickly explain the problem of the two general’s problem
If two generals try to establish a time of attack, and they both need to participate to win the attack.
Ga is uncertain of any message to Gb untill a confirmation is received. The irony is that Gb is uncertain that his confirmation is received untill Ga confirms it. This means that every sent message always leaves uncertainty an no consensus can be reached in asynchronous systems.
What is the definition of consesus? and how is it different from a decision?
In consensus, all processes need to be aware that all other processes are aware of the decision. This is different from normal decisions, where it plainly assumes everyone came to the same conclusion (Without verifying this).
What is the difference between consesus and agreement?
In both cases all processors in a system need to eventually decide on the same value. However in consensus all processes have a suggestion of the value, and in agreement only one process does.
The problems are concidered equally difficult.
What is the difference between a Fault and a Failure?
A fault only applies to one process, while a failure applies to the whole system.
Give examples of possible faults
- Fail-stop / crash: one process just stops
- Omission: a processor fails to send/receive messages
- Timing: a processor does not meet timing specifications
- Byzantine: a Processor has random/malicious behaviour
- transient: temporarit fault that corrects eventually.
What is the difference between synch and async consensus?
Reaching consensus in asynchronous systems is much more difficult: long delays / link faults are very hard to detect.
What impact does authentication have on agreement?
Without authentication, reaching agreement is much more difficult.
What assumption is true for all (fault) system models?
Assume a complete network connectivity
What are the four consensus properties?
– Termination: every correct process eventually decides some value
– Validity: If a process decides v, then v was proposed by some process.
– Integrity: No process decides twice.
– Agreement: No two correct processes decide differently.
Explain the solution for the synchronous, crash fault model.
Assume at most f faulty processes in network. Then, for f+1 rounds every process broadcasts all its encountered proposals (W). It also receives numerous proposals that round that it adds to W. When W only contains one element, that element is decided.
Explain how the agreement property is satsified in the solution for the synchronous, crash fault model.
Because there are f+1 rounds with at most f faulty processes, there is at least one round in which no process crashes. During this round all processes will send the same value of W, and thus reach consensus.
The processes are deterministic, and thus decide on the same value
What is the byzantine agreement problem?
In agreement, one process starts with the final value. And all other correct processes have to agree on the same value. However, with byzantine faults it can occur that different values are introduced during consensus. This means it is impossible to conclude wich process is byzantine (including the source).
What are the conditions for reaching agreement with byzantine faults?
At least N>3f nodes in the system are required.
Minimal number of rounds in deterministic solution = f+1
In moddeling, what is OM?
Oral Message, it is used to describe a communication without authentication: It can be falsified.
Explain the solution for Byz. agreement in the unauth. sync model.
The original source (C) broadcasts its value to all other nodes in the network (Li). For every OM(f-1) layer, each Li will act as the original broadcaster by broadcasting its value “as the thruth” to the other Lj’s. Then each Li will decide based on the majority of all values that is has received.
