Module majority_ack_uniform_reliable_broadcast 

Majority-ack uniform reliable broadcast.

Cachin, Guerraoui & Rodrigues, Module 3.3 and Algorithm 3.5 (“Majority-Ack Uniform Reliable Broadcast”).

Status: transcription. Space: unbounded. pending, ack and delivered grow exactly as in crate::uniform_reliable_broadcast; removing the detector removes a timing assumption, not the collection debt. See docs/bounded-space.md.

Assumption: a correct majority, N > 2f. That is the whole of what this layer rests on. It is a standing property of the deployment rather than a moment-to-moment property of the network, and it is the same trade the leader-driven consensus algorithms make.

What changed, and what it bought

Algorithm 3.4 delivers when every process still believed correct has relayed a message. That belief comes from a perfect failure detector, and uniform_agreement_breaks_when_the_timing_assumption_is_withdrawn shows what one wrong belief costs: a live process is dropped from correct, the condition is satisfied too early, and a message is delivered by some processes and not others.

Algorithm 3.5 asks a different question of the same record, and the book states the change exactly:

// Except for the function candeliver(·) below and for the absence of ⟨ Crash ⟩ events
// triggered by the perfect failure detector, it is the same as Algorithm 3.4.

function candeliver(m) returns Boolean is
    return #(ack[m]) > N/2;

There is no set of believed-correct processes, so no process is ever excluded, so no wrong judgement about who has crashed can be made. What is left is arithmetic over a record this layer already kept. The rest of the algorithm — pending, the relay on first sight, the identifier carrying the originator — is crate::uniform_reliable_broadcast unchanged:

upon event ⟨ urb, Broadcast | m ⟩ do
    pending := pending ∪ {(self, m)};
    trigger ⟨ beb, Broadcast | [DATA, self, m] ⟩;

upon event ⟨ beb, Deliver | p, [DATA, s, m] ⟩ do
    ack[m] := ack[m] ∪ {p};
    if (s, m) ∉ pending then
        pending := pending ∪ {(s, m)};
        trigger ⟨ beb, Broadcast | [DATA, s, m] ⟩;

upon exists (s, m) ∈ pending such that candeliver(m) ∧ m ∉ delivered do
    delivered := delivered ∪ {m};
    trigger ⟨ urb, Deliver | s, m ⟩;

When the assumption fails, this layer blocks rather than diverges

With N ≤ 2f — half or more of the processes crashed, or a partition leaving no majority anywhere — no message reaches a majority and nothing further is delivered. That is a worse liveness failure and no safety failure at all, which is the opposite of what happens to Algorithm 3.4 when its detector is wrong. A blocked cluster can be repaired by restoring processes; a split delivery cannot be repaired by anything.

Departures from the page

• The predicate is written 2 · #(ack[m]) > N rather than #(ack[m]) > N/2. The book means real division; integer division gives the same answer for every N, but only by an argument the reader has to reconstruct.
• N is the full membership including this process, and a process’s own relay counts like any other, because best-effort broadcast sends to the sender too.
• ack and delivered are keyed by an identifier carrying the originator and a per-sender sequence number, not by message content — as in the all-ack version, so that identical content broadcast twice is delivered twice.
• This layer has one child, so it has no wire type of its own: the message is the broadcast child’s. It is the first place in this stack where a wire type gets simpler going up, and removing an assumption is what did it.
• There is no Init event and no Start command. new establishes the state and there is nothing to start, failure detection having gone.
• Neither ack nor pending is garbage collected, as in the book. Long runs grow.

Over a link that reports scope boundaries

L is a parameter, so this one module is also what session_majority_ack_uniform_reliable_broadcast used to be. Algorithm 3.5 has no scope events; the establishment clause is this layer’s, and it is the same one the all-ack version carries — resend everything pending, unconditionally, directed at the peer whose scope returned.

Unconditional matters here for an extra reason. ack[m] records who relayed m to this process. It says nothing about whether this process’s relay reached them, and that relay is the token they are waiting for. Filtering the resend by q ∉ ack[m] deadlocks; the argument is recorded at resend_to, where a test found it. The delivery predicate changing does not change that argument, so the clause is carried over unchanged, including its cost: a re-establishment sends every pending message to that peer.

When the assumption fails, this layer blocks rather than diverges

A partition leaving one side with fewer than half the processes delivers nothing on that side, rather than delivering something the majority will never deliver. When the sides rejoin, the minority catches up through the same resend clause. Compare the all-ack version, where each side accuses the other and both proceed — which is a split, and permanent.

URB1 [always]       Validity — conditional on the reachability below
URB2 [incarnation]  No duplication — `delivered` is volatile, so a restart forgets it
URB3 [always]       No creation
URB4 [always]       Uniform agreement — conditional on the reachability below

URB2 is [incarnation] by docs/scope-annotated-modules.md Corollary 7.2: the redundancy that would have to survive is the delivered set, it is held in memory, and the boundary it cannot cross is this process’s own ⟨Init⟩.

URB1 and URB4 are [always] only while a majority remains mutually reachable, which is an assumption and not a property of this code. A partition leaving no side with more than N/2 blocks both sides rather than splitting them, and both properties survive the block — nothing is delivered that should not be. What does not survive a permanent split is liveness: the layer waits for ever, which is the honest outcome and the one the all-ack version cannot offer, because its detector’s accusations let both sides proceed. See without_a_majority_the_layer_blocks_rather_than_diverges.

Unlike crate::uniform_reliable_broadcast, no timing assumption is among them: removing the detector removed the synchrony it needed, not just a dependency.

Structs

MajorityAckUniformReliableBroadcast

Broadcast with uniform agreement, resting on a correct majority and on nothing else.

Enums

Cmd

Requests from the layer above. Broadcasting is the only one.

Ind

Indications to the layer above.

Type Aliases

Carried

What a link beneath this layer must carry.

Msg

The message type: the broadcast child’s, unwrapped.