1 files changed, 46 insertions, 4 deletions

diff --git a/src/swarm/topology.rs b/src/swarm/topology.rs
index c5a02f1..57856b6 100644
--- a/src/swarm/topology.rs
+++ b/src/swarm/topology.rs
@@ -204,6 +204,13 @@ pub(crate) async fn refresh(state: &AppState) -> Option<NeighbourChange> {
 const RING_LABEL: &[u8] = b"continuum/topology-ring/1";
 const PAIR_LABEL: &[u8] = b"continuum/topology-pair/1";
 
+/// How many members may prefer the same stable member, as a multiple of `k`. Without a
+/// bound, 20 stable members among 2000 get about 500 neighbours each: every
+/// announcement in the swarm lands on them, and the backbone saturates first. Members
+/// that find a stable member full prefer the next one, then go by pair score, so the
+/// graph stays connected and symmetric.
+const STABLE_FANIN_FACTOR: usize = 4;
+
 /// The neighbours of `local` among `members` (which may or may not contain `local`),
 /// skipping members for which `unreachable` holds.
 pub(crate) fn neighbours(
@@ -222,7 +229,7 @@ pub(crate) fn neighbours(
 
 /// Every reachable member's neighbours. Costs about N² hashes (a few milliseconds for
 /// hundreds of members). `stable` members (`swarm::stability`) are preferred for half of
-/// each member's scored slots.
+/// each member's scored slots, each by at most `STABLE_FANIN_FACTOR * k` members.
 ///
 /// Each reachable member walks the ring (by key hash) both ways to the first reachable
 /// member, which gives a ring over the reachable members, and adds the `k - 2`
@@ -231,6 +238,8 @@ pub(crate) fn neighbours(
 ///
 /// Each node judges reachability by itself, so nodes may briefly disagree; that only
 /// adds links (whoever chose a link initiates, the other answers), it never cuts one.
+/// The preference budget is spent in key order, which every node shares, so nodes that
+/// agree on reachability compute the same links.
 pub(crate) fn graph(
     members: &[String],
     k: usize,
@@ -275,6 +284,11 @@ pub(crate) fn graph(
             .expect("more than k + 1 live members")
     };
 
+    // How many members have preferred each stable member so far (`live` iterates in key
+    // order, the same on every node).
+    let budget = STABLE_FANIN_FACTOR * k;
+    let mut preferred_by: BTreeMap<&str, usize> = BTreeMap::new();
+
     for member in &live {
         let at = position[member];
         let next = first_live(at, 1);
@@ -289,15 +303,18 @@ pub(crate) fn graph(
             .collect();
         candidates.sort_unstable();
         // Half the slots (rounded up) prefer stable members, so long-running nodes form
-        // a backbone; the rest go by pair score alone, keeping paths short and the load
-        // on stable members bounded.
+        // a backbone; the rest go by pair score alone, keeping paths short. A stable
+        // member enough others prefer already is skipped, so no hub grows with the swarm.
         let stable_slots = (k - 2).div_ceil(2);
         let preferred: Vec<&str> = candidates
             .iter()
             .map(|(_, other)| *other)
-            .filter(|other| stable(other))
+            .filter(|other| stable(other) && preferred_by.get(other).copied().unwrap_or(0) < budget)
             .take(stable_slots)
             .collect();
+        for other in preferred.iter().copied() {
+            *preferred_by.entry(other).or_default() += 1;
+        }
         let rest = candidates
             .iter()
             .map(|(_, other)| *other)
@@ -476,4 +493,29 @@ mod tests {
             "a stable member has {stable_max} neighbours"
         );
     }
+
+    #[test]
+    fn hub_degree_is_bounded_however_few_stable_members() {
+        // Few stable members among many: without the fan-in budget each would be chosen
+        // by most of the swarm (about 130 neighbours with 10 of 250). With it, a hub has
+        // at most the budget plus the links others choose by pair score and the ring.
+        for (n, stable_count) in [(250, 10), (1000, 10), (1000, 20)] {
+            let k = 12;
+            let ms = members(n);
+            let stable: BTreeSet<String> = ms.iter().step_by(n / stable_count).cloned().collect();
+            let is_stable = |m: &str| stable.contains(m);
+            let g = super::graph(&ms, k, &all_reachable, &is_stable);
+            assert!(connected(&g), "n={n} stable={stable_count}");
+            let hub_max = g
+                .iter()
+                .filter(|(m, _)| stable.contains(*m))
+                .map(|(_, ns)| ns.len())
+                .max()
+                .unwrap();
+            assert!(
+                hub_max <= 8 * k,
+                "n={n} stable={stable_count}: a stable member has {hub_max} neighbours"
+            );
+        }
+    }
 }