Module probabilistic_broadcast 

Eager probabilistic broadcast — gossip.

Status: implementation. Space: bounded by a retention window. The first module above the failure detector that is not a transcription; see the guarantee table below for what the window costs.

Cachin, Guerraoui & Rodrigues, Module 3.7 and Algorithm 3.9 (“Eager Probabilistic Broadcast”). Quoted from the book rather than from memory, which matters here more than anywhere else in this repository: docs/postmortem.md records four bugs once reported in the previous implementation of this algorithm, of which three were false positives produced by reading code against remembered pseudocode.

upon event ⟨ pb, Init ⟩ do
    delivered := ∅;

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

upon event ⟨ pb, Broadcast | m ⟩ do
    delivered := delivered ∪ {m};
    trigger ⟨ pb, Deliver | self, m ⟩;
    gossip([GOSSIP, self, m, R]);

upon event ⟨ fll, Deliver | p, [GOSSIP, s, m, r] ⟩ do
    if m ∉ delivered then
        delivered := delivered ∪ {m};
        trigger ⟨ pb, Deliver | s, m ⟩;
    if r > 1 then gossip([GOSSIP, s, m, r − 1]);

The relay is outside the delivery guard, and that is the book’s

Read the indentation. if r > 1 then gossip(...) sits at the same level as if m ∉ delivered, not inside it, so a process relays a message it has already delivered. This looks like a defect. It has been reported as one. It is not: the book names the consequence on the same page — “the algorithm induces a significant amount of redundancy in the message exchanges: any given process may receive the same message many times” — and the redundancy is what makes the probability work out. Relaying only on first receipt would cut the fan-out of every message that reaches a process twice, which is most of them.

What is probabilistic, and what is not

PB1 [probabilistic]  Probabilistic validity — a correct sender's message reaches every correct
                     process with high probability, and on some runs it does not
PB2 [window]         No duplication — within the retention window; see below
PB3 [always]         No creation

PB1 is the whole point and the whole cost. Best-effort broadcast reaches everyone whenever the sender is correct; this does not, and buys in exchange that no process ever sends to all of Π. A run in which some correct process never delivers is not a violation — the suite counts such runs rather than failing on them, and asserts against a stated threshold.

Identity is an identifier, not the message

Departure. The book deduplicates on the message itself — m ∉ delivered — which assumes messages are unique across senders. Every broadcast here instead carries a BroadcastId: its originator and a per-sender sequence number, exactly as reliable_broadcast does, so identical content broadcast twice is delivered twice. The consequence for this module is that delivered holds identifiers rather than payloads, which is also what makes the window below affordable.

The sequence counter is volatile and so is the set it keys, which is the pairing CLAUDE.md requires: a durable set keyed by a volatile counter is the bug, and neither half is durable here.

The identifier also names the originator’s incarnation. A volatile counter restarts at one when its process does, and every other process’s window is keyed on it — so without this, an originator that crashed and came back would have its first window broadcasts discarded everywhere as duplicates of ones it sent before. The incarnation is a value drawn from the seeded generator at Init: distinct across restarts with probability 1 − 2⁻⁶⁴ per pair, decided by the one process that knows it restarted, and needing no storage. A session boundary could not have done this job — a receiver’s link is to a relayer, not to the originator, and a link cannot tell a reconnect from a restart in any case (docs/conditional-guarantees.md). Under the book’s crash-stop model nobody restarts and the field is inert; it exists for the real-world set.

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.” So there is no page to follow, and the mechanism is a design decision with its own cost. delivered keeps the most recent window identifiers per sender and evicts the oldest when that is exceeded, on insert.

Two things follow, and both are deliberate:

• Reclaiming is constant work. One eviction per insert, never a pass over the set. The previous implementation expired by wall-clock age and rebuilt the whole set on every event, so receiving one message cost time linear in everything ever received. That is the one defect in that code which survived scrutiny, and this is the shape that avoids it rather than a smaller version of it.
• PB2 is scoped to the window. A message re-arriving after its identifier has been evicted is delivered again. That is the stated guarantee, not a violation of it, and it is why the table above says [window] where the book says nothing.

Structs

BroadcastId

Which broadcast this is: who originated it, and their sequence number for it.

Config

How this instance gossips.

Gossip

What this layer puts on the wire: the identifier, the rounds still to live, and the payload.

ProbabilisticBroadcast

Gossip: relay to a random few, for a bounded number of rounds.

Enums

Cmd

Requests from the layer above.

Ind

Indications to the layer above.

Type Aliases

Carried

What a link beneath this layer must carry.