4 - Reliable Broadcast Flashcards
What are the three properties of the perfect link abstraction?
- reliable delivery: If a correct process sends a message m to a correct process q, then q eventually delivers m.
- no duplication: No message is delivered by a process more than once.
- no creation: If some process q delivers a message m with sender p, then m was previously sent to q by process p.
What is the difference in reliable delivery for known and unkown topologies?
For known topologies, the messages can be routed to their destination.
However, for unknown topologies, the message must reach all nodes in the system (breadcast). Then this requires implementing the reliable communication abstraction
What are the three properties of the reliable communication abstraction?
- validity: If a correct process p broadcasts message m, then every correct process eventually delivers m.
- no duplication: No message is delivered by a process more than once.
- integrity: If a correct process delivers a message m with sender p, then m was previously broadcast by process p.
Explain briefly how Dolev’s Algorithm works.
The broadcaster sends a identical message to all its neighbours. These neighbours will append the previous sender to the path of the message, and send to the nodes that have not yet received that message. Message is delivered untill it had gone through f+1 unique paths.
What are the requirements for the Dolev Protocol in a non-perfect network?
If f nodes are allowed to be byzantine nodes; then the network must have a connectivity of 2f+1
Analyse the validity of Dolevs Protocol.
It assumes that there is an honest broadcaster, but there are no measurements for when this is not the case. Unpredictible behaviour will ensue.
Explain Best-Effort broadcast?
In the fully-connected abstraction, BE broadcast states that all (correct) nodes will eventually deliver m. However, it does not validate this exchange or the message in any way.
What is Consistent Broadcast?
It is an extention on the reliable broadcast (abstraction) that adds a property:
Consistency: If a correct process delivers m and another correct process delivers m’ then
m=m’.
Explain the rough implementation of Consistent Broadcast.
A broadcaster sends message m to all nodes (virtually). it will wait for enough Echo-responses of m in order to deliver it.
Explain what the number of nodes should be in order to implement Consistent broadcast.
Not all replies might arrive in a bounded time: (-f) values
Among those replies, f might be incorrect: (-f) equal answers
To be convinced of those answers, we need (N-f)-f > f
N>=3f+1
Explain the Consistent Broadcast Crash Fault problem and a proposed solution.
- Validity is not ensured if the
sender crashes mid-broadcast - Idea: a process that receives a
message for the first time (Send)
rebroadcasts it to all processes. This way if one correct process delivers it, all do.
Explain Reliable Broadcast.
Extents the 4 Consistent broadcast properties (see if you know them ;)
Totality: If m is delivered by a correct process, then all correct processes eventually deliver m
How is Reliable broadcast implemented?
After a correct node has received enough Echo’s, (or f+1 Readys) they broadcast a Ready. Once 2f+1 Readys have been received, a correct process delivers message m.
What type of broadcast is this:
- All correct processes deliver or none do
- Two correct processes can only deliver the same message
Reliable
What type of broadcast is this:
– Correct processes might not deliver any message
– Two correct processes might deliver different messages
Best effort
