Consensus Flashcards
What is the consensus problem?
A group of processes must agree on a value afte one or more proposes a value, even in the event of arbitrary failure.
What are the assumptions for consensus? (3)
N Processes
Reliable Communication
Must tolerate process failures. (Crash, Byzantine)
Which systems can consensus be reached in?
Synchronous and sometimes asynchronous (with no failures for async)
What is a faulty process?
A process that exhibits some specified types of faults.
How does a system reach consensus?
Process begins in undecided state.
Each processes initial process drawn from set D.
Values exchanged
Each process decides on a value and enters a decided state.
What are the requirements of a consensus solution? (3)
Termination: Every processes sets a value
Agreement: Every process decides on the same value
Integrity: If all processes propose V, V must be chosen by all correct processes.
How is consensus reached with no failures? (3)
All processes propose a value.
Wait for all responses.
Choose majority value
How are T,A,I achieved with Reliable Multicast?
T and A guarenteed by reliable multicast.
Majority vote ensures I.
What are the 2 types of failure?
Crash: Processes stop sending values (Difficult to detect in async)
Arbitrary: Due to bug or deliberate lie (Byzantine) (Difficult to detect)
What is RTO Multicast?
Reliable Totally Ordered Multicast
What is the implementation of consensus using RTO multicast?
Each process proposes value.
Wait for all values.
Each process chooses first value delivered.
What is used in synchronous systems for sending consensus messages?
Basic Multicast
What is the algorithm for consensus in synchronous systems?
Each process has set V with proposed values (initially only their own).
At each round, each process multicasts V (only new values) and updates V with new values from other processes.
After f+1 rounds, minimum value is chosen.
Why are f+1 rounds used for consensus in Synchronous Systems?
If there can only be f failures, each process must send a value in one of the f+1 rounds, since they cannot fail in all of them.
Why can’t consensus always be reached in asynchronous systems?
We can’t use timeouts to detect failures so we don’t know if a process has crashed or is just slow, therefore there is no guarentee of consensus, only consensus with some probability.
