Group messenger, providing the Total and FIFO ordering guarantees to address the multicast ordering problem and fault tolerance by handling node failures.
PA Specification : https://docs.google.com/document/d/1xgXwZ6GYA152WT3K0B1MPP7F0mf0sPCPzfqr528pO5Y/edit#
Testing scripts and instructions are provided in the specification document.
Protocol to implement Total and FIFO ordering of messages under a crash-stop failure of at most one-node:
Totally Ordered Multicast can be achieved in two ways:
- Using a sequencer
- One dedicated “sequencer” that orders all messages
- Everyone else follows.
- ISIS system
- Similar to having a sequencer, but the responsibility is distributed to each sender.
ISIS system is implemented in this assignment.
- Sender multicasts message to everyone.
- Nodes reply with proposed priority(sequence no.) by appending process id.
- Larger than all observed agreed priorities
- Larger than any previously proposed (by self) priority
- Nodes store message in priority queue
- Ordered by priority (proposed or agreed)
- Mark message as undeliverable
- Sender chooses agreed priority, re-multicasts message
with agreed priority
- Maximum of all proposed priorities
- Nodes upon receiving agreed (final) priority
- Mark message as deliverable
- Deliver any deliverable messages at the front of priority queue
Each message sent to a node is used to detect node failure upon socket read timeout.
- Preserving the process order
- The message delivery order at each process should preserve the message sending order from every process. But each process can deliver in a different order.
- For example,
- P1: m0, m1, m2
- P2: m3, m4, m5
- P3: m6, m7, m8
FIFO Order:
- P1: m0, m3, m6, m1, m4, m7, m2, m5, m8
- P2: m0, m4, m6, m1, m3, m7, m2, m5, m8
- P3: m6, m7, m8, m0, m1, m2, m3, m4, m5
- Preserving the happened-before relations
- The message delivery order at each process should preserve the happened-before relations across all processes. But each process can deliver in a different order.
- For example,
- P1: m0, m1, m2
- P2: m3, m4, m5
- P3: m6, m7, m8
- Cross-process happened-before: m0 -> m4, m5 -> m8
Causal order:
- P1: m0, m3, m6, m1, m4, m7, m2, m5, m8
- P2: m0, m1, m3, m6, m4, m7, m2, m5, m8
- P3: m0, m1, m2, m3, m4, m5, m6, m7, m8
- Every process delivers all messages in the same order.
- For example,
- P1: m0, m1, m2
- P2: m3, m4, m5
- P3: m6, m7, m8
Total order:
- P1: m7, m1, m2, m4, m5, m3, m6, m0, m8
- P2: m7, m1, m2, m4, m5, m3, m6, m0, m8
- P3: m7, m1, m2, m4, m5, m3, m6, m0, m8