The Plumtree tree engine — a self-optimising epidemic broadcast that combines an eager-push spanning tree with lazy-push redundancy (Leitão, Pereira & Rodrigues, Epidemic Broadcast Trees, SRDS 2007). This is broadcast engine #1 behind partisan_broadcast_engine; Thicket is engine #2 (partisan_thicket_engine).

The idea

A pure flood is reliable but wasteful — every node receives every message on every link. A pure spanning tree is efficient but fragile — one failed interior node cuts off a whole subtree. Plumtree gets both: it lets a spanning tree emerge from an initial flood and keeps the pruned links as a cheap standby.

Each node partitions its peers, per broadcast source (Root), into two sets:

• eager peers — the tree links. A message is pushed to them in full, immediately.
• lazy peers — the standby links. Instead of the payload, a node sends them an i_have(MessageId) advertisement.

A node forwards a full message only to its eager peers, so the eager links form the spanning tree. The tree builds and heals itself with two rules:

• Prune. When a node receives a message it has already seen over an eager link, that link is a redundant second path into the tree. The node demotes the sender to lazy (prune), removing the duplicate edge.
• Graft. A lazy peer's i_have names a message the node has not received. If, after a short wait, the message still has not arrived over the tree, the node grafts that peer back to eager and asks for the payload — filling a gap the tree left, and re-attaching a subtree orphaned by a failure.

Over a stream of broadcasts the eager set converges to a low-cost spanning tree while the lazy set stays ready to repair it.

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

• eager_sets / lazy_sets :: #{Root => nodeset()} — the eager and lazy peers for each source's tree.
• common_eagers / common_lazys — the default partition a newly-seen root starts from (initially all members eager, none lazy), so a first message from a new source floods and then self-prunes into a tree.
• all_members — the current membership, the universe the peer sets are drawn from.
• outstanding_tab — an ETS table of lazy pushes queued but not yet sent as i_have; lazy_tick/1 flushes it. It is owned by the group process and created in init/1.

The mechanism, callback by callback

The engine is pure: each callback returns {engine_state(), [action()]} and never sends. The group shell (partisan_plumtree_broadcast) computes the handler's verdicts — is this message novel? is this i_have stale? — and executes the returned actions.

• broadcast/4 — originate: eager-push to the tree and schedule lazy pushes.
• handle_broadcast/8 — a message arrived over an eager link. If novel, deliver it, forward it on down the tree, and schedule lazy pushes; if a duplicate, prune the sender.
• handle_ihave/7 — a lazy i_have arrived. If the id is not already held, record it and arm a graft timer; if stale, ignore it.
• handle_graft/7 — a peer asks us to re-supply a message and re-join the tree: promote it to eager and send the payload the handler returned.
• handle_prune/3 — a peer tells us its eager link to us was redundant: demote it to lazy.
• lazy_tick/1 — flush the outstanding lazy pushes as i_have summaries.
• select_exchange_peer/2 — pick a peer for a periodic anti-entropy exchange, the backstop that heals anything the eager/lazy mechanics missed.

update_members/2 reconciles the peer sets when membership changes; neighbors_down folds a departed peer out of every tree and lets graft re-attach whatever it carried.

Where this sits

The engine owns tree topology and repair only. The group shell owns the process, the mailbox, the membership poll, handler dispatch (novelty via claim/merge, re-supply via graft), the transport, and the ticks. That split is what lets Thicket drop in behind the same behaviour with no change to the shell (see partisan_broadcast_engine).