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).

Composition with operational mission classes (v1.2)

The v1.2 supplemental (WRITEUP §9.4) extends the empirical envelope across three operational mission classes — drift handling, online replanning over partially-known cost fields, and Bayesian search-and-rescue — with Phase A literature audit positioning the work in the canonical decentralized-Bayesian-SAR lineage (Bourgault, Furukawa, Durrant-Whyte 2003), the consensus-on-PDF lineage (Bandyopadhyay-Chung 2014/2018), the channel-filter lineage (Grime-Manyika-Makarenko-Durrant-Whyte), and the connectivity-preservation-with-fault-injection lineage (Minelli, Panerati, Kaufmann, Ghedini, Beltrame, Sabattini 2020 RAS). The contribution is reframed from "novel substrate" to "engineering composition with characterized empirical envelope": broadcast as shared state, deterministic per-drone compute, and majority-vote aggregation under degraded comms.

• Drift handling (§9.4.1): drift × reset × directive × inter-drone ranging across σ_drift ∈ 1 m/√s and reset/directive intervals. External error tracks σ·√T·1.6 within 1% of analytical 3D Maxwell-Boltzmann; reset clamps to σ_reset noise floor regardless of drift; ranging caps shape error at ∼0.079m (500× reduction at MEMS-grade). Internal coherence exactly zero across all 27 drift × reset × directive cells.
• Online replanning (§9.4.2): A*-style adaptive replanning across 3 environments. 60/60 reach goal, 100% byte-identical decisions per tick under reliable broadcast. Cost gap vs oracle: 28% / 39% / 140% across single-threat / two-threats / dense-field. The substrate-level claim (deterministic replanning with byte-identical decisions) is demonstrated; closing the cost gap with a SOTA partially-known-terrain planner is left to future work.
• Distributed Bayesian SAR (§9.4.3): 2220 runs across 7 scenarios × 10 algorithms × 13 channel models with KCELLS=1 detection. Voting baseline (iid_100%) produces 0/20 found — broadcast is empirically load-bearing. SAROPS-class particle filter (with all 85 Allen Leeway object-class parameters from OpenDrift's OBJECTPROP.DAT) wins on all four drift scenarios. Bandyopadhyay-Chung consensus filter dominated across T ∈ 50 on the regime tested.
• Asymmetric-deaf cliff (§9.4.3): graceful degradation at 10-25% deaf-fraction (20/20 found, unanimity 0.1); catastrophic at 50% deaf (0/20). Consistent with the n/2 majority-vote threshold of textbook voting theory in the SAR setting.
• Methodological discipline: 3-session pre-publish stress test (unsupported-claims inventory, weakest defensible interpretation, hostile reviewer simulation), followed by /review across 7 parallel agents, followed by sim-review iteration to convergence. Reframed architectural claim per stress-test findings; added §9.4.0 mapping the v1.1 two-component substrate (broadcast + determinism) onto the v1.2 three-component composition (+ majority-vote aggregation).

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.2), with each tagged release auto-archived to Zenodo via the GitHub integration.

• Paper: concept DOI 10.5281/zenodo.19954716 (resolves to latest); v1.2 version DOI 10.5281/zenodo.20092214.
• Software: concept DOI 10.5281/zenodo.19993222 (resolves to latest); v1.2 version DOI 10.5281/zenodo.20092230.

The v1.2 supplemental adds detailed companion notes (NOTE_DRIFT, NOTE_ASTAR, NOTE_SEARCH) and a Phase A literature audit (audit/00–07) for reproducibility transparency.

Key References