Decentralized Drone Swarm Coordination via Broadcast-as-Shared-State and Hierarchical PCA-Tree Bisection

Executive Summary

We propose a single coordination primitive — broadcast-as-shared-state with locally-deterministic per-drone computation against a PCA tree of the target manifold — and show that it supports four independently provable operational layers: assignment, recovery, priority allocation, and localization. The four layers compose without interference (slot-disjointness lemma, three-part composition theorem). Every headline number carries bootstrap 95% confidence intervals over ≥10 seeds; the optimality-gap empirical fit form is validated by AIC/BIC against five candidates.

Layer 1 (assignment) lands within 1.43% of the Hungarian optimum at N=10,000 from a single broadcast snapshot. Against CBBA (Choi-Brunet-How 2009, the standard decentralized comparator), hierarchical needs 14× fewer messages while landing at a 3.0% gap (vs CBBA's 7.7% in this simplified single-task variant). Layer 4 (cooperative localization) is the only of three regimes (INS-only, sparse-GPS, Layer 4) that does not degrade monotonically over the mission: 0.082m [0.072, 0.092] at t=78s vs INS-only's 0.409m and sparse-GPS-only's 0.252m under realistic heavy-tailed noise.

Key Contributions

• One primitive, four layers: assignment, recovery, priority allocation, and cooperative localization all reduce to the same broadcast-as-shared-state pattern with PCA-tree-keyed local computation. No leader, no auction round, no consensus phase beyond what the broadcast already carries.
• Slot-disjointness composition theorem: formal proof (Theorem 3a/3b/3c) that the four layers compose without interference because each writes to a disjoint subset of broadcast slots. Non-interference lemma proves slot-disjointness implies commutativity.
• O(1/√N) rounding bound: rigorous proof (Proposition 1) that the rounding contribution to the optimality gap is O(1/√N), matching the empirical b/√N coefficient. Conjecture 4: empirical fit gap = 1.27% [1.22, 1.33] + 14.12 [11.74, 16.50] / √N (M5 form, beats four alternatives by AIC/BIC).
• Witness-alarm primary defense: byzantine detection via mutual physical observation. Each drone with a working GPS fix observes its neighbors via UWB time-of-flight or visual fiducial; physical-vs-broadcast inconsistency raises an alarm; consensus from ≥3 independent witnesses excludes the byzantine. 100% detection above 5σ threshold; 1.3% false-positive rate at the 10σ operating point under heavy-tailed noise.
• Closest-surplus patch protocol: single-death reassignment proven to reach exactly 0.9% of the swarm (one promotion). Cluster recovery (Lemma 7) yields exactly K reassignments with 0 unfilled when surplus ≥ K. Tiered redundancy reduces flight cost 56% when threat correlates with priority.

Key Findings

• 1.43% gap at N=10,000: hierarchical PCA-tree bisection lands within 1.43% of the Hungarian optimum on the sphere manifold, with variance collapsing from ±4.30% at N=10 to ±0.01% at N=10,000.
• 14× messaging advantage over CBBA at N=100: hierarchical 100 messages / 1 round / 3.0% gap vs CBBA 1350 messages / 13.5 rounds / 7.7% gap (10 seeds, bootstrap 95% CIs throughout). Wall-clock crossover with Hungarian at N≈3000.
• Layer 4 holds bounded under drift: 30 seeds × 2000 ticks (78s simulated) under heavy-tailed noise (10% outliers at 5σ): Layer 4 = 0.082m at t=78s vs INS-only 0.409m and sparse-GPS-only 0.252m. The only regime that does not degrade monotonically over the mission.
• Witness-alarm trade-off curve: at 5σ threshold, 100% detection above 5m magnitude but 14.7% false-positive rate under heavy-tailed noise. At 10σ, 100% detection above 10m and 1.3% false positives. Subthreshold-lie damage is bounded by lie magnitude, not free.
• Cluster recovery exact: when surplus ≥ cluster size, recovery yields exactly K reassignments and 0 unfilled (Lemma 7, verified empirically at K=10/S=10).

Comms-Layer Empirical Validation (v1.1)

The v1.1 revision adds a comms-layer empirical validation section (WRITEUP §9.1.5) covering four sweeps at N=100 drones, 200 seeds (Sweep B at 30 seeds), with PROOFS Lemma 9.5 (ETA-deadline quiescence under packet loss) and Theorem 2.5 (mid-flight reconfiguration consensus).

• Quiescence detection under loss: the inverted EN_ROUTE+ETA protocol holds 0% missed-deadline through per-message loss p=0.7 (vs 97.0% for a re-broadcast-augmented presence-based baseline). At p=0.9 still 0% missed-deadline with 6.2% [5.3, 7.0] false-quiescence. Half the bandwidth of naive.
• Spatially-correlated loss (shadowed clusters): with K of 100 drones in a high-loss shadow (p_inside=0.9), the inverted protocol holds 0% missed-deadline and false-quiescence rises gracefully from 0.9% (K=5) to 4.5% (K=50). Naive degrades to 88.6–100% missed-deadline.
• Mid-flight reconfiguration consensus: Option 1 (prior-end-state input) achieves 100% per-drone byte-identical consensus at every reconfiguration moment. Option 2 (live broadcast snapshot) collapses to 50–77% under just 1 tick (40 ms) of snapshot jitter — consensus-safe only under perfect synchronization.
• Channel-denial deferral: under an 80-second jam centered on the deadline, the no-deferral protocol false-quiescences on 100% of drones; the 1-second-channel-silence deferral mechanism reduces this to 0% with 100% transitioned, no deadlock.
• ETA-spoofing attack and defense: a single byzantine drone broadcasting a falsified ETA deadlocks the entire swarm without mitigation. A purely-local sanity bound (reject ETA > t + 2(μ+3σ)) restores 100% transition rate even at K=25 byzantines (25% of fleet), with honest false-quiescence held below 0.5%.

Out of scope and pointed to existing literature: physical-layer scaling at large N (Karn 1990, Akyildiz 2005, IEEE 802.11), cross-platform byte-identity for Theorem 2.5 (Goldberg 1991, Monniaux 2008), coordinated byzantine collusion / replay / Sybil (Castro & Liskov 1999 PBFT, Bracha 1987), and mobile shadow propagation (Goldsmith 2005).

Code and Data

All source code, simulator, benchmark scripts, figures, and the rendered four-phase formation demo live at the GitHub repository github.com/jmcentire/drone-swarm-coordination (tag v1.1.1), with each tagged release auto-archived to Zenodo via the GitHub integration. Software concept DOI: 10.5281/zenodo.19993222 (resolves to the latest version); v1.1.1 version DOI: 10.5281/zenodo.19993920.

Key References