Decentralized Drone Swarm Coordination via Broadcast-as-Shared-State and Hierarchical 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 (Theorem 3 in the companion proofs): each layer reads and writes a distinct subset of broadcast slots. Comparisons report bootstrap 95% confidence intervals, and the optimality-gap fit form is selected by AIC/BIC from 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 one of three regimes (INS-only, sparse-GPS, Layer 4) that does not degrade monotonically over the mission: under realistic heavy-tailed noise it stays below 10cm throughout (0.091m [0.077, 0.106] at t=60s), while INS-only drift reaches 0.41m at t=78s and sparse-GPS plateaus near 0.25m.

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.
• Composition theorem: Theorem 3 (companion proofs) establishes that the four layers compose without interference. Each layer reads and writes a distinct subset of broadcast slots, and Layer 4 produces the position estimates that Layers 1–3 consume.
• 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; multiple independent witness alarms mark the drone dead and route the patch protocol. To tolerate f lying witnesses, the standard bound of 3f+1 witnesses per claim applies. Under heavy-tailed noise, the 10σ operating point detects every lie of 10m or more with a 1.3% false-positive rate.
• Closest-surplus patch protocol: with surplus, a single death causes exactly one reassignment (0.9% of the swarm, in every seed), versus a bimodal 23% mean for a full rerun. Cluster recovery scales linearly with primary deaths and leaves 0 leaves unfilled while surplus lasts (Lemma 7). Pure key shadow allocation reduces flight cost 66% versus uniform reserve when threats correlate 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 broadcast slots / 1 round / 3.0% gap vs CBBA 1350 messages / 13.5 rounds / 7.7% gap (simplified single-task CBBA, 10 seeds, bootstrap 95% CIs). 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% of samples drawn at 5× σ): Layer 4 stays below 10cm throughout, while INS-only reaches 0.41m at t=78s and sparse-GPS plateaus near 0.25m. The only regime that does not degrade monotonically over the mission.
• Witness-alarm trade-off curve: at a 5σ threshold (3.6m floor), every above-floor lie is detected but 14.7% of honest drones are falsely flagged under heavy-tailed noise. At 10σ (7.1m floor), lies of 10m or more are detected 10/10 with 1.3% false positives. Subthreshold-lie damage is bounded by lie magnitude, not free.
• Cluster recovery: with 10 surplus drones, patch reassignments scale linearly with the number of primary deaths across clusters of 1 to 10, with 0 primary leaves unfilled (consistent with Lemma 7).

Comms-Layer Empirical Validation (v1.1)

The v1.1 revision adds a comms-layer empirical validation section (WRITEUP §9.1.5) covering five 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. About half the messages of naive (13.7 vs 26.2 msgs/s).
• 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) reaches 100% only with perfect synchronization; consensus falls to 86.7–100% at 1 tick (40 ms) of clock skew and 30–77% at 5 ticks (200 ms).
• Channel-denial deferral: under an 80-second jam centered on the deadline, the no-deferral protocol false-quiescences on 100% of drones; deferring on 1.0s of total channel silence 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 on accepted ETAs (2(μ+3σ)) restores 100% transition even at K=25 byzantines (25% of the fleet), with honest false-quiescence held below 1%.

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 at 10%, 18–20/20 at 25%); catastrophic at 50% deaf (0/20). Consistent with the n/2 majority-vote threshold of textbook voting theory in the SAR setting.
• Methodological discipline: a falsification battery against each load-bearing component (no-broadcast voting baseline, 50% deaf fraction, consensus-round T-sweep) and a fairness audit of the comparator (detection criterion harmonized at KCELLS=1). §9.4.0 maps 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.4.0), with each tagged release auto-archived to Zenodo via the GitHub integration.

• Paper: concept DOI 10.5281/zenodo.19954716 (resolves to latest); v1.4.0 version DOI 10.5281/zenodo.20615823.
• Software: concept DOI 10.5281/zenodo.19954677 (resolves to latest); v1.4.0 version DOI 10.5281/zenodo.20615824.

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. The v1.3 supplemental adds a bounded underwater feasibility track (acoustic detection-map gossip, acoustic link-budget and capacity accounting, vertical GPS/acoustic relay localization). The v1.4 supplemental adds mission-level companion artifacts: unknown-building search and exploration, shared obstacle and door mapping, relay sentinels, target extraction, a deterministic drone-loss stress mode, and threat-responsive manifold disclosure materials.

Key References