5 - causal and total order Flashcards
When is message ordering important?
Whenever there are dependent reactions in a system: Events that have been incited by other events, and must therefor also be processed after the original event.
Explain the Causal order Broadcast (cob) Properties.
- Validity. If a process cob-delivers a message m then there is a process that cob-broadcast m.
- Integrity. No message is cob-delivered twice.
- Termination. If a process cob-broadcast a message m, then eventually all processes cob-deliver it.
- Agreement. If a process delivers a message m then all processes eventually cob-deliver it.
- Causal order. If m1-> m2, no process cob-delivers m2 before m1.
What are the main ideas behind no-waiting causal order broadcast?
- Remember all previously delivered messages
- When broadcasting, join all previously delivered messages
- The causal past of a message.
What is another name for the Birman-schiper-stephenson algorithm?
Waiting Causaul order broadcast
What are the main ideas of the waiting causal order broadcast?
- Local causality: Every process numbers its broadcast messages, then other processes can check its order.
- global causality: Processes send their own knowledge about their states with each broadcast. A receiving processor can check if it has not missed messages.
What concept is used to implement waiting causal order broadcast, and for what purpose?
Vector clocks, only for checking message order
What is the condition for delivering a message with waiting causal order broadcast?
VCi + [1] ≥ VCm
When is the clock updated in causal order broadcasting?
Increment own vector clock when starting a broadcast, and vector clock at sender’s index when co-delivering.
What is different in causal order point-to-point compared to broadcast?
No longer will all nodes in the system be aware of every event. This means that local states have little value, as (missing) messages were not meant for you in the first place.
What is another term for the [Schiper-Eggli-Sandoz] algorithm?
Point-to-point causal ordering
How is the point to point causal order implemented?
Each nodes keeps track (map of clocks) of what it assumes other nodes know. (Send messages that might not have been received yet). It appends this map to each outgoing message, as well as its own vector state, such that nodes can inspect what other believe they should be aware off, indicating a missing message.
When is the local clock updated in p2p causal order?
Before sending the message, such that the new state is already appended to the message. When delivering, take max values.
Explain the difference in causal and total order.
In causal order, you want to assure that before delivery, you have delivered all the dependencies of that message. However, in total order, you want all the processes to deliver in the exact same order, even if there is no (causal) dependency.
What are the properties of strong total order broadcast?
It is the properties of waiting causal order, plus:
Total order: If a process to-delivers m1 before m2, then all processes to-deliver m1 before m2
What are the properties of weak total order broadcast?
It is the properties of waiting causal order, plus:
Total order: If a process to-delivers m1 before m2, then all processes to-deliver m1 before m2
But without:
** Causal order**. If m1 -> m2, no process to-delivers m2 before m1
