Module lazy_probabilistic_broadcast 

Lazy probabilistic broadcast — gossip, then pull back what it missed.

Status: implementation. Space: bounded by a retention window.

Cachin, Guerraoui & Rodrigues, Module 3.7 and Algorithms 3.10 and 3.11. The book splits it in two — a data half and a recovery half — and this module quotes both, verbatim from the source rather than from any recollection of it.

Algorithm 3.10: Lazy Probabilistic Broadcast (part 1, data dissemination)
Implements: ProbabilisticBroadcast, instance pb.
Uses:
    FairLossPointToPointLinks, instance fll;
    ProbabilisticBroadcast, instance upb.        // an unreliable implementation

upon event ⟨ pb, Init ⟩ do
    next := [1]^N; lsn := 0; pending := ∅; stored := ∅;

procedure gossip(msg) is
    forall t ∈ picktargets(k) do trigger ⟨ fll, Send | t, msg ⟩;

upon event ⟨ pb, Broadcast | m ⟩ do
    lsn := lsn + 1;
    trigger ⟨ upb, Broadcast | [DATA, self, m, lsn] ⟩;

upon event ⟨ upb, Deliver | p, [DATA, s, m, sn] ⟩ do
    if random([0, 1]) > α then
        stored := stored ∪ {[DATA, s, m, sn]};
    if sn = next[s] then
        next[s] := next[s] + 1;
        trigger ⟨ pb, Deliver | s, m ⟩;
    else if sn > next[s] then
        pending := pending ∪ {[DATA, s, m, sn]};
        forall missing ∈ [next[s], . . . , sn − 1] do
            if no m′ exists such that [DATA, s, m′, missing] ∈ pending then
                gossip([REQUEST, self, s, missing, R − 1]);
        starttimer(Δ, s, sn);

Algorithm 3.11: Lazy Probabilistic Broadcast (part 2, recovery)

upon event ⟨ fll, Deliver | p, [REQUEST, q, s, sn, r] ⟩ do
    if exists m such that [DATA, s, m, sn] ∈ stored then
        trigger ⟨ fll, Send | q, [DATA, s, m, sn] ⟩;
    else if r > 0 then
        gossip([REQUEST, q, s, sn, r − 1]);

upon event ⟨ fll, Deliver | p, [DATA, s, m, sn] ⟩ do
    pending := pending ∪ {[DATA, s, m, sn]};

upon exists [DATA, s, x, sn] ∈ pending such that sn = next[s] do
    next[s] := next[s] + 1;
    pending := pending \ {[DATA, s, x, sn]};
    trigger ⟨ pb, Deliver | s, x ⟩;

upon event ⟨ Timeout | s, sn ⟩ do
    if sn > next[s] then
        next[s] := sn + 1;

Two children, and why the second one matters

Uses: names both fll and upb. Data is gossiped by the unreliable broadcast beneath; requests and their answers travel directly over the link, bypassing the gossip. That is what makes the second phase a pull and the algorithm lazy. Routing a request through upb would flood the membership to repair one process’s gap, which is exactly the cost this phase exists to avoid. So this layer multiplexes two children onto one wire, as crate::uniform_reliable_broadcast does for its broadcast and its detector.

Three readings the page settled, each of which was about to go the other way

• next := [1]^N. Sequence numbers start at one. A zero-based next leaves every process waiting for a message no sender ever sends.
• The timeout skips past the gap. if sn > next[s] then next[s] := sn + 1 abandons the message at sn too, not just those before it. Setting next[s] := sn would deliver a message the process has already given up on.
• Draining pending is a standing condition. upon exists … such that sn = next[s] is re-evaluated whenever next or pending changes, so closing one gap can release a long run at once. Written here as a loop after every mutation of either, which is the same thing.

The α, which the book states twice and inconsistently

The pseudocode stores when random([0,1]) > α, so α is the probability of not storing. Page 99 says in prose that a process stores “with probability α”, which is the opposite. Page 100 breaks the tie: it describes setting α = 0 as every process storing, which only holds under the pseudocode’s reading.

docs/postmortem.md disagrees with itself on this too — its re-examination reaches the same conclusion, and its own worked sketch writes gen_bool(alpha). This module ends the question by not using α at all: Config::store_probability is the probability of storing, named for what it does, and the book’s α is one minus it.

What this buys, and what it costs

PB1 [probabilistic]  Probabilistic validity — strictly better than the eager algorithm's under
                     loss, because a gap is repaired rather than lost
PB2 [window]         No duplication — within the retention window
PB3 [always]         No creation

Recovery depends on some reachable process having stored the message, so PB1 here is conditional on store_probability and on that process being reachable — not absolute. A gap nobody stored is skipped by the timeout, which converts a permanent stall into a lost message, and a stall would be the worse outcome.

The retention window, which is this project’s and not the book’s

Page 100: “garbage collection of the stored message copies is omitted in the pseudo code for simplicity.” Both stored and pending are bounded here by a per-sender window and evicted on insert, for the reasons crate::probabilistic_broadcast gives at length. A request for something evicted is answered as unavailable, and the requester’s timeout moves it past the gap.

Identity is scoped to the originator’s incarnation — departure

The book’s s is a process, and next[s], pending and stored are keyed by it. lsn is volatile, so a process that crashes and comes back numbers its messages from one again — and every receiver, holding next[s] = 4, would drop its first three as already delivered, silently, through the sn < next[s] case the pseudocode does not even write. Under the book’s crash-stop model that case never arises; in the real-world set it is the first thing a restart does.

So the sender of a Data is a Sender — the originator and its incarnation, a value drawn from the seeded generator at Init exactly as crate::probabilistic_broadcast draws its own — and every per-sender structure is keyed by that. A restarted originator is a new sender with next = 1, and its messages are delivered.

What bounds it: a receiver remembers the two most recent incarnations of each originator, and admitting a third retires the oldest — its next, its pending and stored messages, its timers. Two rather than one because relayed copies from the incarnation just retired can still be arriving while the new one’s begin, and a one-deep memory would flip between them, losing both. Two rather than more because a process has one live incarnation and at most one being retired; a message from an incarnation older than that is a straggler this abstraction may lose. State is therefore bounded by 2 × membership × window, and a restart costs one purge, not a leak.

Structs

Config

How this instance recovers.

Data

[DATA, s, m, sn] — this layer’s header, carried as the gossip’s payload.

LazyProbabilisticBroadcast

Gossip with recovery.

Sender

An originator in one incarnation — what next, pending and stored are keyed by.

Enums

Cmd

Requests from the layer above.

Ind

Indications to the layer above.

Recovery

What travels over the link directly, outside the gossip: [REQUEST, …] and its answer.

Wire

The wire, multiplexing the two children Algorithm 3.10 names.

Type Aliases

Gossiper

The gossip this layer rides on: Algorithm 3.9 carrying Data, over G — the fair-loss link the book names unless the caller says otherwise.