Thicket broadcast engine — T interior-node-disjoint spanning trees over one overlay, with each node's forwarding load bounded (Ferreira, Leitão & Rodrigues, Thicket: A Protocol for Building and Maintaining Multiple Trees in a P2P Overlay, SRDS 2010). This is broadcast engine #2 behind partisan_broadcast_engine; Plumtree is engine #1.

The problem it solves

A single epidemic-broadcast tree (Plumtree) concentrates forwarding work on its interior nodes. When many sources broadcast over the same overlay — one tree per source — the same well-placed nodes tend to be interior in every tree, so a few nodes carry the whole cluster's fan-out while the rest stay leaves. Thicket spreads that load: it builds the T trees so that, as far as the overlay allows, each node is interior in only a few of them, and it caps how many with max_load.

The idea

There is one tree per broadcast source, identified by the source node (tree/0 is node/0, the analogue of Plumtree's Root). A node is interior in a tree when it forwards that tree's traffic — it has more than one active peer in it — and a leaf when it merely receives. Thicket keeps the trees interior-node-disjoint: a node interior in one tree is preferentially a leaf in the others, so forwarding is shared out. Two quantities make this work and are piggybacked on every message: a node's own per-tree forwarding fan-out (its load), and its neighbours' most recent loads (load_est), so peers can steer new interior duty toward the least-loaded node that can take it.

Per-node state (the #thicket{} record)

• active :: #{tree() => nodeset()} — for each tree, the neighbours this node exchanges that tree's traffic with (its parent and children). |active(t)| > 1 means interior in t; = 1 means a leaf; = 0 means disconnected from t.
• backup — neighbours currently used in no tree; the spare capacity that repair and branching draw on.
• received :: #{msg_id() => tree()} — delivered message ids only (the paper's receivedMsgs), for loop-avoidance and announcement filtering. No payloads — see Payload delegation below.
• announcements — {id, tree, sender} triples learned from summaries: who can re-supply a message this node is missing. This set doubles as the repair server-directory, and is bounded by an age window (see Bounded announcements).
• load_est :: #{{node(), tree()} => load} — the last forwarding load each neighbour reported for each tree; the persistent directory repair and reconfiguration steer by.
• repair / rejected / unsummarised — the per-tree repair countdown, the servers that recently rejected a graft (so a different one is tried next), and the recently-received ids still due to be advertised in summaries.

The four mechanisms

Thicket is four interacting mechanisms, matching the paper's four algorithms:

1. Construction. On a novel DATA message a node disconnected from that tree adopts the sender as its tree link (adopt_and_forward/6), and a node not yet interior anywhere may branch, taking on children up to the fan-out (tree_branching/2). Adoption and branching reuse a link already carrying another tree when no idle one is free (§4.4 link-reassignment), which is what lets a late source's tree still span the overlay.
2. Repair. Periodically a node advertises its recent ids to its backup peers as a summary; a peer missing an advertised id records an announcement and arms a repair timer; when the timer fires it grafts the best server it knows of (tick/1 → fire_repairs/1 → graft_best/2 → best_announcer/2). Repair is what turns the randomised construction — which leaves gaps — into full coverage.
3. Reconfiguration. The load-aware balance/4: on a novel message from its current parent, a node whose parent is heavily loaded swaps to a lighter announced alternative — but only one that is a currently-missing upstream server, the §4.4 precondition that proves the swap cannot form a cycle.
4. Overlay dynamics. neighbor_up/2 and neighbor_down/2 fold membership changes into the peer sets; repair then recovers any tree a failed neighbour was carrying.

Invariants

• Interior-load bound (safety). No node is ever interior in more than max_load trees. Every step that could raise interior load — branching, adoption, accepting a graft — is gated on the current interior_load/1, so the bound holds by construction, for every configuration and message ordering.
• Coverage (liveness). Every node eventually delivers every broadcast. This holds when max_load ≥ T (the cap a ceiling at or above the tree count) over up to four divergent trees — a regime that necessarily includes T > f, where interior-node-disjoint trees cannot fit and coverage rests on link-reassignment and on branching into the headroom max_load allows. max_load < T still holds the load bound but does not guarantee coverage.

Two implementation decisions worth knowing

• Payload delegation. The engine stores no payloads. It keeps only delivered ids for loop-avoidance and delegates payload storage and re-supply to the registered broadcast handler, exactly as Partisan's Plumtree engine does. When repair must re-supply a specific missing message the engine emits a {fetch, Peer, MsgId, Tree, Load} action, which the shell resolves through the handler's graft/1. Re-supply is therefore per-missing-id — never a dump of a tree's whole history — and no engine structure grows with the payload volume.
• Bounded announcements. Because announcements doubles as the repair server-directory, the paper's drop-on-receipt pruning would starve repair here. Instead each announcement carries a rounds-left age, refreshed on re-advertisement and dropped when it expires, bounding the set to a sliding window.

Purity and testing

Every event returns {state(), [action()]}, where an action is {send, Peer, Msg}, {deliver, MsgId, Payload} or {fetch, Peer, MsgId, Tree, Load}; the engine never performs I/O. That makes the whole protocol exercisable in a deterministic simulation — prop_partisan_thicket_engine, the primary validator, since an off-by-default engine is invisible to partisan_SUITE.

Configuration

Configure via new/3 Opts, following the paper's guidance (§4.6 and the §5.1 experimental setup), which is also the regime the property model validates:

• max_load (default 7) — the ceiling on how many trees a node may be interior in. Treat it as a generous safety ceiling, not a tight budget: repair settles most nodes to be interior in a single tree, and max_load only catches the few that must do more for coverage. Keep it comfortably above the tree count (the paper runs max_load = 7 with 5 trees). Not recommended: max_load = 1 with more than one tree.
• fanout (default 5) — the number of children a node branches to when building a tree.
• trees (default 1) — the number of trees T, used to size the degree-budget reservations. Bound it by the fanout (T ≤ f): with fanout f only about f interior-node-disjoint trees fit over one overlay, so asking for more forces nodes to forward for several trees (bounded by max_load). The paper uses T = f = 5.

The overlay should give each node a degree on the order of f × T, so it has enough neighbours to play its role in every tree (the paper uses degree 25 for f = T = 5). new/3 rejects clearly-invalid values (max_load < 1, fanout < 2, trees < 1).

Reading guide

The EVENTS section — broadcast/3, handle/2, tick/1 — is the whole protocol at a glance; each dispatches into the PRIVATE section, whose functions run construction → forwarding → reconfiguration → repair → peer-set bookkeeping, in that order. new/3 and the record it builds define the state everything else operates on.