docs topology

1 files changed, 122 insertions, 0 deletions

diff --git a/docs/topology.md b/docs/topology.md
new file mode 100644
index 0000000..31abcf5
--- /dev/null
+++ b/docs/topology.md
@@ -0,0 +1,122 @@
+# Topology and dissemination
+
+Two choices decide how a change gets from the member that wrote it to every other:
+
+* the **topology** (`--topology`): who a member's neighbours are, the members it syncs
+  with;
+* the **dissemination** (`--dissemination`): whom a member pushes a change to at once;
+  every other neighbour hears of it by announcement and pulls it.
+
+Underneath both, neighbours sync pairwise with Automerge, which delivers everything in
+the end; the two choices only decide how soon, and at what cost. Announcements, pulls
+and the slow round repair whatever a dissemination misses, whichever is in use.
+
+Both are the swarm's, not each node's: the genesis node records its own in the
+document (`_continuum/topology`, `_continuum/dissemination`), every node follows what
+the swarm records, and a protocol writer may change them there (every node swaps as the
+change reaches it, starting from the neighbours it had). A node uses its own options
+only where the swarm records none it knows. While a switch passes through the swarm,
+nodes that switched and nodes that haven't yet disagree about who their neighbours are:
+that costs pulls and late arrivals for a few seconds, never data.
+
+## Topologies
+
+**ring-and-pairs** (the default). Every node computes the same graph from the member
+list: a ring by key hash, plus each member's pairs with the lowest pair score, `k` in all
+(`--neighbours`, 12 by default, recorded by the genesis node). A swarm of up to `k + 1`
+members is a full mesh. Where a link the graph gives doesn't work, members record it,
+and the graph every node computes follows (`swarm::working_links`). Because every node
+can compute every other node's neighbours, writers' trees can be built on it.
+
+**hyparview** (an experiment). Each node keeps an active view: neighbours that each
+agreed to be one (NEIGHBOUR, NEIGHBOUR_REPLY, DISCONNECT), about `k` of them (5 unless
+`--neighbours` is set, the paper's size for up to about 10 000 members). Members that
+fail leave it, and others are asked; each neighbour is asked again every minute whether
+it still is, so a link lost at one end (a lost DISCONNECT) doesn't stay at the other. The passive view, whom to ask, is drawn from the
+member list, not from the paper's JOIN and SHUFFLE (`swarm::hyparview`). There is no
+graph every node shares: writers' trees, recorded links, indirect probes and the
+dashboard's intended links do nothing.
+
+## Disseminations
+
+**writers-trees** (the default with ring-and-pairs). Every node computes, from the
+shared graph, each writer's tree: fewest hops from the writer, over links that work,
+and among parents as close, the one with the shortest round trip (`swarm::tree`); it
+pushes the writer's changes to its children in it. Shallow (about 2 hops at 50 members), no control messages. Needs the
+shared graph: with HyParView there are no trees, and changes pass on by announcement
+alone, a round (200 to 400 ms) and a pull per hop.
+
+**plumtree** (an experiment). Eager links push at once, lazy ones only
+announce; a link that delivers a duplicate is pruned, one whose announcement brought a
+change first is grafted (PRUNE, GRAFT). Its tree forms from the links that delivered
+first, one for all writers: deeper than writers' trees (5 to 6 hops at 50 members over
+Mycelium's round trips). Needs no shared graph.
+
+**flood** (the default with hyparview; a baseline otherwise). Every change pushed at once to every neighbour but the one it
+came from. The fastest path always carries it, with no tree to compute or repair, but
+each link carries it about twice: the cost grows with `k`.
+
+## Combinations
+
+| topology | dissemination | |
+|---|---|---|
+| ring-and-pairs | writers-trees | **Recommended.** Fewest messages, and fast: a few tens of ms behind flooding at a fifth of its messages. |
+| ring-and-pairs | flood | The fastest, at five to six times the messages with the default 12 neighbours: a baseline. Warned of. |
+| ring-and-pairs | plumtree | Works; slower than writers' trees and about twice their messages. For comparing. Warned of. |
+| hyparview | flood | The best with HyParView: about 25 % slower than writers' trees, at about twice their messages. |
+| hyparview | plumtree | Works; slower than flooding with HyParView, at about as many messages: with 5 neighbours there is little to prune, and announcements cost what pushes would. |
+| hyparview | writers-trees | **Not recommended**: no trees, announcements alone. Warned of. |
+
+Unset, `--dissemination` follows `--topology` (flood with hyparview), and so does
+`--neighbours` (5 with hyparview).
+
+## Numbers
+
+From the benchmark (`cargo benchmarks`, `docs/development.md`), November 2026: 50
+members, 100 writes at 5 a second; the median of three runs (`BENCH_REPEAT=3`), with one
+writer and with writers in turn: the mean delay until a write arrives, and the messages
+per write, every kind counted.
+
+| | Mycelium's round trips, lossy | | Tor's round trips | |
+|---|---|---|---|---|
+| | delay | messages | delay | messages |
+| ring-and-pairs, writers-trees | 126 / 112 ms | 99 / 119 | 324 / 325 ms | 135 / 164 |
+| ring-and-pairs, flood | 70 / 93 ms | 642 / 656 | 259 / 264 ms | 662 / 684 |
+| ring-and-pairs, plumtree | 174 / 238 ms | 255 / 306 | 496 / 751 ms | 219 / 408 |
+| hyparview, flood | 148 / 136 ms | 207 / 222 | 407 / 404 ms | 212 / 250 |
+| hyparview, plumtree | 262–315 / 336–405 ms (two runs) | 166 / 191–200 | 614 / 888 ms | 172 / 277 |
+| hyparview, writers-trees | 675 / 587 ms | 145 / 195 | 1180 / 1017 ms | 113 / 194 |
+
+By the links' latencies alone, the fastest paths take 65 ms to a member over
+Mycelium's round trips and 267 ms over Tor's: flooding on the member list's graph comes
+to that (its 12 neighbours give more paths than the bench's figure counts), writers'
+trees take 94 and 324 ms. PlumTree's gap is its tree's depth: along eager links alone
+a member is 5 to 6 hops from another over Mycelium's round trips (writers' trees: 1.9),
+3.4 to 4.3 over Tor's (1.8). `docs/future-work.md` (Swappable topology and
+dissemination) says how it got there and what was tried.
+
+HyParView's active views settle at 5 neighbours each, nearly all held at both ends (up
+to 3 links of about 125 at one end only, at the end of a run). A member one short asks
+again only every 5 minutes, as those that refuse are mostly full (asking at once, up to
+300 NEIGHBOUR messages went in 20 quiet seconds); what goes in a quiet swarm now is each
+member asking its neighbours whether they still are, once a minute (about 80 in 20 s at
+50 members). The figures above are with both (patches 1025, 1027): before, with the
+views still changing and members being asked counted as neighbours too, flooding had
+more paths, and over Mycelium's round trips took 107 / 122 ms.
+
+## Which, when
+
+* **A swarm whose members share a member list, up to a few hundred members**:
+  ring-and-pairs with writers' trees. Every node computing every node's neighbours is
+  cheap there, and the trees it allows are shallow.
+* **Links whose latency changes over time** (circuits that slow down for a while):
+  writers' trees go by hops first, and by the round trips measured only among parents
+  as close; PlumTree follows which links deliver first. The benchmark can't model
+  links that change mid-run, so this is untested.
+* **Members whose views of the member list differ for long** (partitions, slow
+  registration): writers' trees can orphan a member whose parent computes another tree
+  (repaired by pulls and the slow round); PlumTree and HyParView can't, needing no
+  shared view.
+* **Swarms too large for every node to compute the whole graph**: HyParView, whose
+  views stay small whatever the swarm's size; with a passive view from JOIN and
+  SHUFFLE instead of the member list, once that list is too large to hold.