Multicast in Practice: Ordering, Reliability, and View Changes

A packet can arrive before the application is allowed to use it. That distinction is the starting point for multicast ordering: the network supplies arrival events; the protocol decides when a message is safe to deliver.

The earlier clock notes introduce happened-before. Here I work through the implementation rules from the course, then add failures and membership changes. The examples assume crash failures, not malicious processes. The ordering algorithms first use a fixed group; changing that group is a separate problem.

Three questions, three contracts

A correct process does not crash in the execution being considered. Reliability statements about correct processes do not promise that a crashed process finishes its work.

FIFO preserves each sender’s order. Causal order also preserves dependencies across senders, so it implies FIFO within the same group. Total order makes recipients agree on the relative order of delivered messages; it does not, on its own, preserve send order or causality. A causal-total protocol provides both.

For example, if every recipient delivers a reply before its original post, their order is total but not causal. If recipients all deliver the original first but disagree on the order of two independent replies, their order can be causal but not total.

FIFO: wait for the missing sequence number

Each sender has a monotonically increasing sequence number. Receiver i stores delivered[j], the last sequence number delivered from sender j. This is a delivery counter, not the largest number seen on the network.

on receiving (sender j, sequence s, payload):
    if s <= delivered[j]: discard this duplicate
    if s > delivered[j] + 1: buffer the message
    if s == delivered[j] + 1:
        deliver the message
        delivered[j] = s
        repeat with any buffered successor from j

Suppose P3 has delivered none of P1’s messages:

flowchart LR
  A["Network: message 2"] --> B["Buffer: waiting for 1"]
  C["Network: message 1"] --> D["Deliver 1"]
  D --> E["Expected number becomes 2"]
  B --> F["Deliver buffered 2"]
  E --> F

Nothing in this rule orders a message from P2 relative to a message from P1. Also, buffering does not recover loss: if message 1 never arrives, message 2 stays blocked. Retransmission and failure handling must supply the missing progress guarantee.

Causal multicast: a message carries its prerequisites

FIFO is insufficient when P2 reads P1’s post and then sends a reply. A third process must see the post before the reply, even though they have different senders.

The course’s causal protocol maintains a vector V of multicast counters. At process i, entries for other senders count messages already delivered; the local entry counts its own multicasts. Sending advances the sender’s entry by one and attaches the entire vector.

This is not the general vector-clock rule that increments on every local event. Here the numbers count multicasts. The model assumes that relevant communication goes through this group protocol; untracked communication outside it can create dependencies the vector does not capture.

For a message from sender j carrying vector T, receiver i waits until both conditions hold:

T[j] == V_i[j] + 1                 // next multicast from this sender
T[k] <= V_i[k], for every k != j   // all other prerequisites delivered

It then delivers the message, sets V_i[j] = T[j], and rechecks its buffer. It must not merge a buffered message’s vector into the delivery vector: learning that a prerequisite exists is not the same as delivering it. The sender’s own multicast is accounted for locally once; a network echo must not advance its counter again.

Worked example: two replies overtake their original post

Use vector positions [P1, P2, P3, P4]:

1. P1 multicasts post a with [1,0,0,0].
2. P2 delivers a, then multicasts reply b with [1,1,0,0].
3. P4 independently delivers a, then multicasts reply c with [1,0,0,1].
4. P3 receives both replies before the original post.

sequenceDiagram
  participant P1
  participant P2
  participant P3
  participant P4
  P1->>P2: a [1,0,0,0]
  P1->>P4: a [1,0,0,0]
  P2->>P3: b [1,1,0,0]
  Note over P3: Buffer b: missing a
  P4->>P3: c [1,0,0,1]
  Note over P3: Buffer c: missing a
  P1->>P3: a [1,0,0,0]
  Note over P3: Deliver a, then b and c<br/>in either order

Only the messages needed to explain P3’s decisions are drawn; each send is a multicast to the group.

Releasing c before b is also valid. Their vectors each have a component larger than the other’s, so neither reply depends on the other. Causality orders the prerequisites without inventing an order between independent work.

This implementation carries O(N) counters per message for a group of N processes. The metadata buys enough information to test dependencies; it does not eliminate waiting for a slow prerequisite.

Total order: let a sequencer assign the positions

A sequencer maintains one global counter. For each multicast it assigns the next position, such as 41 or 42. Each receiver stores lastDelivered and waits for both the payload and its assigned position.

deliver message m only when:
    payload m is present
    sequencer's assignment (m, s) is present
    s == lastDelivered + 1

flowchart TD
  A["Sender A: message x"] --> S["Sequencer"]
  B["Sender B: message y"] --> S
  S --> X["Assign x = 41, y = 42"]
  X --> R1["Replica 1: deliver x, then y"]
  X --> R2["Replica 2: deliver x, then y"]
  X --> R3["Replica 3: deliver x, then y"]

If replica 2 receives y and its assignment 42 while lastDelivered = 40, it still waits for 41. Network arrival can differ; application order remains the same. In the lecture’s protocol, the sender multicasts the payload and the sequencer multicasts the assignment with the message; this diagram focuses on the ordering decision.

The simple algorithm assumes the sequencer remains available. Electing a replacement is not enough to establish safe recovery: the replacement must also preserve earlier assignments and prevent two active sequencers from assigning incompatible histories. That requires additional protocol machinery.

Terminology also matters. The lecture introduces total order alongside “atomic broadcast.” In a complete specification, atomic broadcast includes reliable delivery properties as well as ordering. A counter alone establishes neither fault tolerance nor those full guarantees.

Reliable multicast: recipients help finish the send

Sending a message to every member in a loop is not sufficient. Suppose P1 sends m to P2, then crashes before reaching P3. Reliable point-to-point links cannot finish a loop that no process is executing.

The lecture’s basic repair is forwarding: on first receipt of m, every recipient sends it to all group members. A unique message identifier prevents repeated forwarding and duplicate application delivery.

sequenceDiagram
  participant P1
  participant P2
  participant P3
  P1->>P2: m
  Note over P1: Crashes before contacting P3
  P2->>P3: Forward m on first receipt
  Note over P2,P3: Both correct recipients can deliver m

Assume a fixed group, reliable links between correct processes, and correct processes that continue executing. If correct P2 receives m, it eventually forwards m to every correct member, including P3. Assuming P3 never receives it contradicts those assumptions. A sequential implementation must not block forever trying to contact a failed member before reaching the healthy ones.

The reliability contract needs more than “everyone has the same set,” since delivering nothing would satisfy that sentence:

• Validity: a correct sender’s multicast is eventually delivered by the correct recipients.
• Agreement: if a correct process delivers a message, all correct recipients eventually deliver it.
• Integrity: a message is delivered at most once, and only if it was multicast.

The forwarding argument above concerns correct processes. Uniform agreement strengthens the premise to any process that delivers, including one that later crashes. A process that delivers and crashes before forwarding gives a reason not to assume the stronger property without a suitable protocol.

This simple forwarding scheme can use O(N²) point-to-point transmissions per multicast. It makes the correctness argument easy to see, but is not a claim about an efficient production transport. Permanent partitions also invalidate the eventual communication assumption.

Virtual synchrony: finish a view before crossing its boundary

A view is a membership configuration with an identity, such as V7 = {P1,P2,P3}. A view change installs a new configuration after a join, departure, or suspected failure. View identity matters: two configurations can contain the same names but belong to different epochs.

Virtual synchrony relates membership events to multicast delivery. Processes that move together from the same old view to the same next view must agree on the set of messages delivered in the old view. In the lecture’s model, each delivered message also belongs to a view containing its sender.

Consider P3 sending m in V7, then crashing. P1 and P2 will install V8 = {P1,P2}. If P1 has delivered m in V7, P2 cannot cross into V8 without the corresponding old-view delivery and still claim the same transition.

flowchart LR
  V["V7: P1, P2, P3"] --> M["P3 sends m, then crashes"]
  M --> F["P1 and P2 resolve old-view delivery"]
  F --> A["Both deliver m in V7"]
  A --> N["Install V8: P1, P2"]

This diagram illustrates the required outcome, not a complete membership or flush algorithm.

If a failed sender’s message was never delivered by any surviving member, omitting it can be valid. Once a surviving member has delivered it in the old view, “drop it everywhere” is no longer an available way to repair the history. The protocol must complete a compatible transition or exclude a member that cannot participate, according to its membership rules.

Same view does not mean the same wall-clock time

P1 and P2 can install V8 at different physical times. The guarantee concerns their histories and view boundaries, not synchronized clocks. Ordering within a view is another choice: FIFO, causal, total, or a hybrid. Equal message sets do not alone imply equal message order.

The lecture also shows a partitionable case: one side continues with {P1}, another with {P2,P3}. Do not read the common-view guarantee as a promise that arbitrary disconnected components maintain one global sequence of views. Virtual synchrony alone does not prevent competing decisions across partitions. A system that requires one authoritative history needs an additional membership or quorum policy; the abstraction does not evade the consensus limitations discussed in the Paxos notes.

Check your reasoning

1. A reply arrives first. Can FIFO alone hold it back? Not when the reply and original have different senders. Causal metadata expresses that dependency.
2. Every replica uses the same sequence numbers. Is the multicast reliable? Not necessarily. They may wait forever for a missing payload or assignment.
3. P1 and P2 delivered the same messages but assigned one message to different views. Is that virtual synchrony? No. The boundary is part of the contract.
4. Does causal order mean concurrent replies must appear identically everywhere? No. Add total order if the application requires that property.

To replay the basic ordering cases, use the multicast section of the interactive CS 425 guide.

Source notes

Based on Cloud Computing Concepts, Part 1: 2.1 Multicast Ordering, 2.2 Implementing Multicast Ordering 1, 2.3 Implementing Multicast 2, 2.4 Reliable Multicast, and 2.5 Virtual Synchrony, using both the slides and accompanying transcripts. The diagrams and traces here are reconstructed teaching examples. The forwarding proof and view examples retain the course’s crash-failure assumptions; implementation cautions identify what those simplified algorithms leave unspecified.