Skip to content

Latest commit

 

History

History
98 lines (70 loc) · 2.91 KB

README.md

File metadata and controls

98 lines (70 loc) · 2.91 KB
Raw

Group-Messenger-with-Total-and-FIFO-Ordering-Guarantees (Distributed Systems PA-2B)

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.

ISIS algorithm for total ordering:

  • 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.

Background theory:
FIFO Ordering
  • 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
Causal Ordering
  • 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
Total Ordering
  • 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