Phase Diagram of Decentralized Coordination Under Communication Delay

We map coordination quality over communication delay for a family of decentralized primitives in a simplified 3-D kinematic swarm simulator, locate the collapse boundary — the delay cliff — and show that the collapse is governed by delay rather than by the choice of coordination algorithm.

Chris Adams

Arboria Labs, Alpharetta, GA United States

Corresponding Author email: cadams@arborialabs.com

ORCID - Christopher Adams 

Abstract

Decentralized coordination assumes agents can exchange state fast enough to act on it. When communication delay approaches the coordination timescale, that assumption fails — but where it fails, and whether the failure depends on the coordination algorithm, has not been mapped directly. We treat delay as a controlled axis and measure a normalized coordination quality $Q \in [0,1]$ over a grid of coordination primitive $\times$ delay $\times$ swarm size $\times$ task, using a simplified 3-D kinematic simulator in which each agent acts on a delayed view of its peers while its own physics advances on true state. Across two peer-derived-target tasks — mutual rendezvous and consensus — three otherwise-distinct primitives (gossip-consensus, flocking, and CRDT-intent) collapse together from $Q \approx 1$ at zero delay through a boundary near $10$–$20$ integration steps, reaching a floor by delay $40$. A no-communication reference holds that floor, delay-independent. The overlap of the three primitives is the central result: within this regime the collapse is primitive-independent — delay, not the algorithm, sets where coordination breaks — and it is invariant across swarm sizes $N \in \{500, 2000\}$. We then test the mechanism directly: varying the intrinsic convergence rate through the gossip consensus gain $\alpha$, the collapse onset $d_c$ scales inversely with $\alpha$ ($d_c\,\alpha \approx 2.8$ across a factor of four in gain and two swarm speeds), and beyond onset every gain relaxes onto a single gain-independent master curve — so the boundary is set by the ratio of delay to the swarm’s own coordination timescale, now measured rather than inferred. We anchor the substrate to an external result by reproducing the Vicsek order–disorder transition ($\psi: 1.00 \to 0.63$ across the noise range) before trusting its coordination measurements. All figures regenerate from committed experiment records ($900$-cell phase grid plus a $520$-cell intrinsic-timescale grid, $5$ seeds each; $0$ NaN, $0$ agent faults). We scope the claim precisely: this is a simulation-based algorithmic result about coordination primitives under delay, not physical-device validation.

Keywords

Decentralized Coordination, Communication Delay, Delay-Coupled Systems, Phase Transition, Consensus, Rendezvous, Multi-Agent Systems

1. Introduction

1.1. Background and Motivation. Decentralized multi-agent systems — swarms, sensor fields, and, increasingly, distributed compute fabrics that must coordinate across physical separation — rest on a hidden premise: agents exchange state quickly relative to how fast the task changes. As the ratio of communication delay to the coordination timescale grows, agents act on stale information about their peers. The practical question is not whether coordination degrades but where the useful regime ends, and whether that boundary can be pushed by choosing a better coordination algorithm.

1.2. Problem Statement. We ask: at what communication delay does decentralized coordination collapse, and does the collapse boundary depend on the coordination primitive? We make delay a controlled experimental axis rather than a nuisance parameter, and we score every primitive on one normalized substrate so their collapse curves are directly comparable.

1.3. Contributions.

• A delay-coupled evaluation harness in which the coordination decision consumes a delayed view of peer state while the physics integrates true state — the mechanism by which delay degrades coordination (§3).
• A unified coordination-quality metric $Q \in [0,1]$ and two peer-derived-target tasks (rendezvous, consensus) on which flocking, gossip-consensus, and CRDT-intent are scored head-to-head (§3.2).
• A phase diagram: the location of the collapse boundary and the empirical finding that, in this regime, it is primitive-independent and size-invariant across $N \in \{500, 2000\}$ (§5).
• An external anchor: reproduction of the Vicsek order–disorder transition on the same engine, validating the substrate before we trust its coordination numbers (§5.1).

1.4. Outline. §2 relates this to delay-coupled dynamics and consensus theory. §3 defines the harness, primitives, and metric. §4 gives the experimental setup. §5 presents the anchor and the phase diagram. §6 discusses scope and limitations. §7 concludes.

2. Related Work / Background

2.1. Delayed consensus and networked control. Delay-coupled dynamics have a long history in coupled-oscillator and networked-control theory. Delayed average-consensus of the form $x_i(t{+}1) = x_i(t) + \alpha \sum_j a_{ij}\,\big(x_j(t{-}d) - x_i(t{-}d)\big)$ is known to slow and, past a delay threshold set by the algebraic connectivity of the interaction graph, to destabilize convergence [1, 2, 3]. Rate-limited and information-theoretic treatments of feedback under delay [4, 5] establish that a finite channel capacity imposes a hard bound on stabilizable dynamics. These results are analytical and per-scheme: they characterize one control law at a time. We complement them with a measured phase diagram across heterogeneous primitives on a shared task substrate.

2.2. Active matter and the Vicsek transition. Self-propelled particle models — Vicsek [6] and its hydrodynamic Toner–Tu description [7], surveyed by Chaté [8] — exhibit a noise-driven order–disorder transition in the polar order parameter $\psi$. We do not study that transition for its own sake here; we reproduce it (§5.1) purely as an external anchor to validate that the engine’s collective dynamics behave correctly before we trust its coordination measurements.

2.3. Coordination primitives. The primitives themselves are standard: Reynolds’ Boids flocking [9], gossip/average-consensus [1, 10], and CRDT-backed intent replication [11]. Our framing wraps each as a swappable primitive behind one act interface, so only the coordination logic differs across collapse curves and the comparison is apples-to-apples.

2.4. Positioning. Our contribution is not a new stability theorem but the head-to-head map that per-scheme stability analyses do not provide: where the useful regime ends, whether that boundary moves with the algorithm, and whether it moves with swarm size — measured on one substrate, with an external anchor.

3. Method

3.1. Delay-coupled harness. At integration step $t$ the engine advances every agent’s true position and velocity. The coordination primitive, however, does not observe the current swarm: it observes the true snapshot from $t - d$, where $d$ is the one-way communication delay in steps. Concretely, the runner maintains a ring buffer of the last $d{+}1$ true states and hands the primitive the oldest slot as its perceived peer view. The primitive returns a desired velocity; the actuation is re-referenced to each agent’s true current velocity, so an agent always knows its own state exactly and delay affects only its knowledge of peers. This is the “self-current, peers-delayed” delayed-coupling model; without the true-velocity re-reference, the perceived/true mismatch injects energy each step and the swarm diverges on an engine that does not clamp speed.

3.2. Unified coordination quality. Each task exposes a normalized quality $Q(\text{state}) \in [0,1]$, higher is better:

Both are peer-derived-target objectives: the target (the swarm centroid; the agreed value) is not known to any isolated agent, so coordination is necessary — an agent cannot solve the task alone. This is what makes $Q$ sensitive to delayed peer information. $L_0$ and $\operatorname{Var}_0$ are fixed length/variance scales tied to the initial spread, so $Q$ is domain-size invariant.

3.3. Primitives. All primitives are wrapped behind one act(pos, vel, dt) -> accel interface and receive the delayed peer view:

• gossip-consensus — one synchronous average-consensus round over the radius graph, steering toward the neighborhood mean;
• flocking — fixed-weight Boids (cohesion/alignment/separation);
• CRDT-intent — boids steering plus an intent/age-of-information plane over the same neighbor graph;
• no-comm (reference) — agents damp their own velocity only, using no peer information; the “coordination buys nothing” floor.

4. Experimental Setup

Runs use Gossamer (v0.3.1) coordination primitives driven through Maneuver.Map’s vectorized policy seam, with the Leviathan engine (velocity-Verlet integrator) advancing true physics. The energy and fault modules are disabled ($\texttt{energy\_rate}=0$, $\texttt{fault\_prob}=0$) so that agent attrition cannot confound the delay axis. The grid is primitive $\times$ task $\times$ delay $\times$ $N$ $\times$ seed $= 5 \times 3 \times 6 \times 2 \times 5 = 900$ cells; delays are $\{0, 5, 10, 20, 40, 60\}$ integration steps ($\mathrm{dt}=1$), the task-timescale $\tau = 300$ steps, and $N \in \{500, 2000\}$. Every reported point is a mean over $5$ seeds; the full run produced $0$ non-finite values and $0$ agent faults.

We fix $\tau$ throughout and note that it is inert for the two tasks studied here: $Q_{\text{rendezvous}}$ and $Q_{\text{consensus}}$ measure the swarm’s internal compactness and variance, neither of which reads a goal that moves on the $\tau$ clock. The operative timescale in this paper is therefore not $\tau$ but the swarm’s intrinsic convergence time — the rate at which the coordination law contracts the group toward its peer-derived target, set by the primitive’s gain, the swarm speed, and the interaction radius. We hold $\tau$ fixed only to keep the environment stationary; §5.4 measures the intrinsic timescale directly by sweeping the gossip gain. (A companion study imposes an external task timescale, via a moving goal that only a fraction of agents observe, to test the delay/$\tau_{\text{task}}$ ratio separately.)

5. Results

5.1. Substrate anchor. Before trusting coordination measurements, we validate the engine against a known external result — the Vicsek order–disorder transition. With a faithful constant-speed Vicsek update on the same engine, the polar order parameter $\psi$ falls monotonically from $\psi = 1.00$ at zero angular noise to $\psi = 0.63$ at $\eta = 5$, with seed spread below $0.02$ (Fig. 1). The substrate reproduces the expected ordering, so its coordination numbers are trustworthy.

5.2. The phase boundary. Fig. 2 is the main result. On both peer-derived-target tasks the three communicating primitives collapse from $Q \approx 1$ at zero delay through a boundary near $10$–$20$ steps and reach the floor by delay $40$. On consensus the collapse is sharp — gossip holds $Q = 0.93$ at delay $5$, $0.77$ at delay $10$, $0.14$ at delay $20$, and $0.00$ by delay $40$. On rendezvous the decay is smoother ($1.00 \to 0.63 \to 0.43 \to 0.20 \to 0.04$). The no-comm reference holds a delay-independent floor ($0$ for consensus; $\approx 0.14$ residual compactness for rendezvous).

5.3. Primitive-independence and size-invariance. The three communicating primitives — gossip-consensus, flocking, CRDT-intent — collapse on top of one another (their curves are indistinguishable at plotting resolution). Within this regime, which decentralized primitive an agent runs does not move the collapse boundary; delay does. The curves are furthermore identical at $N = 500$ and $N = 2000$: the boundary does not move with swarm size. Size-invariance is consistent with the boundary being set by the ratio of delay to the swarm’s intrinsic coordination timescale rather than by $N$; §5.4 tests that hypothesis directly by varying the intrinsic timescale itself.

5.4. The boundary scales with the intrinsic timescale. Size-invariance (§5.3) is consistent with a delay-to-timescale ratio law but does not prove one — $N$ is not the intrinsic timescale. We therefore vary the intrinsic convergence rate directly. The gossip-consensus gain $\alpha$ sets how aggressively the primitive contracts the swarm toward its neighborhood mean each step, so it is a clean knob on the intrinsic timescale ($\tau_{\text{int}} \sim 1/\alpha$); we sweep $\alpha \in \{0.125, 0.25, 0.5, 1.0\}$ against a densified delay axis at two swarm-speed caps ($v \in \{15, 30\}$), $N = 500$, 5 seeds ($520$ cells). We define the collapse onset $d_c$ as the delay at which $Q$ first falls through $0.9$ (the edge of the coordinated plateau), located by linear interpolation on the seed-mean curve.

The onset scales inversely with the gain: $d_c\,\alpha$ is constant at $\approx 2.8$ across the three resolved gains and — critically — across both speed caps (Table 2). This is the ratio law measured directly: doubling the intrinsic rate halves the tolerable delay. The fastest case, $\alpha = 1.0$, has an onset below the first non-zero delay sampled (5 steps) and is grid-limited; its listed value is an extrapolation and is flagged accordingly.

Table 2. Collapse onset $d_c$ (delay at which $Q$ crosses $0.9$, integration steps) versus gossip consensus gain $\alpha$, at two swarm-speed caps, $N = 500$, mean over 5 seeds. From the committed dcc_p4a_fine records. The product $d_c\,\alpha$ is invariant across gain and speed.

* Grid-limited: onset below the 5-step delay resolution; value extrapolated, product biased low.

Beyond onset, the gain does something surprising: it stops mattering. Each gain’s curve, once it leaves the plateau, relaxes onto a single gain-independent master curve $Q^{*}(d)$ — the spread in $Q$ across all four gains shrinks to $0.10$ by delay $28$ and to $0.00$ (to two decimals) by delay $34$. The intrinsic gain thus sets where the cliff begins, not how far it falls: past the boundary, coordination quality is governed by delay alone. The $\alpha = 1.0$, $v = 30$ corner of this grid reproduces the headline dcc_p1 gossip curve of §5.5 (Table 1) to within seed spread — the headline cliff is the master curve, and the lower gains simply postpone the fall onto it. The swarm speed sets the depth of the master-curve floor ($Q^{*}$ at delay $40$ is $0.21$ at $v = 15$ versus $0.05$ at $v = 30$: faster agents disperse harder once coordination fails) but not the onset, which is fixed by $d_c\,\alpha$. Seed scatter across the whole grid is negligible (median per-cell standard deviation $0.000$, maximum $0.021$).

5.5. Per-cell detail. Table 1 tabulates the mean coordination quality $Q$ (5 seeds) for the gossip-consensus primitive against the no-comm reference across the delay axis; the flocking and CRDT-intent curves coincide with gossip to within plotting resolution and are omitted for brevity (full per-primitive values in Appendix B). The delay cliff is visible directly: consensus falls off between delay 10 and 20; rendezvous decays more smoothly but reaches the same floor by delay 40. This gossip-rendezvous row is the $\alpha = 1$ master curve of §5.4.

Table 1. Coordination quality $Q$ versus one-way communication delay (integration steps, $\mathrm{dt}=1$), $N = 500$, mean over 5 seeds. Values from the committed dcc_p1 records; identical at $N = 2000$.

An interactive version of all figures (hover for per-point values) is available as a companion artifact.

6. Discussion, Scope, and Limitations

This is a simulation-based algorithmic result in a simplified 3-D kinematic engine: a claim about coordination primitives under delay, not physical-device validation. The primitive-independence result holds for the peer-derived-target tasks studied here and should not be over-generalized to tasks where an isolated agent can make progress (there, communication can become a liability under delay rather than a necessity). Two tasks are deliberately out of scope: a coverage-hold task is not achieved by any current primitive (gathering primitives clump away from the target cells) and awaits a dispersal-capable primitive; and a coverage/dispersal primitive (density-modulated Boids + stigmergy) is omitted from the collapse panels because it correctly fails the gather/consensus objectives — the wrong tool rather than a delay effect. A companion analysis of the cost of coordination under delay (bits, joules) is partial: energy-per-quality moves with delay, but bandwidth was held fixed, so a comm-budget sweep is future work.

7. Conclusion

Treating communication delay as a controlled axis yields a clean phase diagram: decentralized coordination on peer-derived-target tasks holds near-perfect quality until delay approaches the coordination timescale, then collapses through a boundary near $10$–$20$ steps to a floor — the delay cliff. The collapse is primitive-independent and size-invariant in this regime — a result about the coupling, not the algorithm. Sweeping the intrinsic convergence rate directly confirms the mechanism: the collapse onset scales inversely with the gain ($d_c\,\alpha \approx 2.8$), and past the onset every gain relaxes onto one gain-independent master curve — so the boundary is set by the ratio of delay to the swarm’s own coordination timescale, and the headline cliff is that master curve seen at the fastest gain. A companion paper studies how anticipation (predicting peer state forward across the delay) shifts this boundary outward.

Data and Code Availability

All §5 numbers and figures regenerate from committed experiment records via Maneuver.Map’s analysis path — aggregating task_metrics.Q_final over seeds. The phase diagram (§5.1–§5.3, §5.5) draws on the dcc_p1 batch (900 cells), aggregated by (task, algorithm, delay, N); the intrinsic-timescale scaling (§5.4) draws on the dcc_p4a_fine batch (520 cells), aggregated by (gossip.consensus_gain, gossip.max_speed, delay). The Vicsek anchor derives from the vicsek batch (45 cells). Each cell writes an experiment.json carrying a provenance block (package versions, environment lockfile hash, hardware fingerprint, full seed tree; the git fields are null under the in-process container worker, which carries no checkout). The coordination primitives live in Gossamer (gossamer.algorithms.coordination); the delay-coupled harness is in Maneuver.Map’s runner.py. The pinned wheel and base-image digests, batch identities, and seed tree are given in Appendix D; the lab’s disclosure policy is at Reproducibility and Data Availability.

References

[1] Olfati-Saber, R., Murray, R. M., “Consensus Problems in Networks of Agents with Switching Topology and Time-Delays,” IEEE Trans. Automatic Control, 2004. [2] Jadbabaie, A., Lin, J., Morse, A. S., “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules,” IEEE Trans. Automatic Control, 2003. [3] Tsitsiklis, J. N., Bertsekas, D. P., Athans, M., “Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms,” IEEE Trans. Automatic Control, 1986. [4] Tatikonda, S., Mitter, S., “Control Under Communication Constraints,” IEEE Trans. Automatic Control, 2004. [5] Nair, G. N., Fagnani, F., Zampieri, S., Evans, R. J., “Feedback Control Under Data Rate Constraints: An Overview,” Proc. IEEE, 2007. [6] Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I., Shochet, O., “Novel Type of Phase Transition in a System of Self-Driven Particles,” Phys. Rev. Lett., 1995. [7] Toner, J., Tu, Y., “Long-Range Order in a Two-Dimensional Dynamical XY Model: How Birds Fly Together,” Phys. Rev. Lett., 1995. [8] Chaté, H., “Dry Aligning Dilute Active Matter,” Annu. Rev. Condens. Matter Phys., 2020. [9] Reynolds, C. W., “Flocks, Herds, and Schools: A Distributed Behavioral Model,” SIGGRAPH, 1987. [10] Boyd, S., Ghosh, A., Prabhakar, B., Shah, D., “Randomized Gossip Algorithms,” IEEE Trans. Information Theory, 2006. [11] Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M., “Conflict-Free Replicated Data Types,” SSS, 2011.

Appendix / Supplementary Material

Appendix A: The coordination-quality metric $Q$. Both tasks expose a normalized quality $Q \in [0,1]$ against a peer-derived target — a quantity no isolated agent can compute alone, so coordination is necessary:

$L_0$ and $\operatorname{Var}_0$ are fixed length/variance scales tied to the initial spread ($L_0 = \texttt{init\_spread}$, $\operatorname{Var}_0$ the variance of the initial uniform fill). Because the normalizers scale with the domain, $Q$ is domain-size invariant — the reason the collapse curves coincide at $N \in \{500, 2000\}$ (§5.3) rather than merely being parallel.

Appendix B: Full per-primitive collapse table. The three communicating primitives (gossip, flocking, CRDT-intent) coincide to within seed spread; Table 1 (§5.4) reports gossip as their representative. The distinguishing feature is communicating vs. not: every communicating primitive tracks the gossip curve, and no_comm holds the delay-independent floor. dmb_tf_aco is a dispersal primitive and is excluded from the gather/consensus panels (it correctly fails those objectives — the wrong tool, not a delay effect), as is coverage_hold (unachieved by any current primitive).

Appendix C: Vicsek anchor. The vicsek batch runs a faithful constant-speed Vicsek update (swept engine velocity_noise = Vicsek angular noise $\eta$) across $\eta \in \{0, 0.5, \dots, 5\}$ at $N = 2000$, 5 seeds. The polar order parameter $\psi$ decays monotonically from $\psi = 1.00$ at $\eta = 0$ to $\psi = 0.63$ at $\eta = 5$ with seed spread below $0.02$ — the expected order→disorder decay, confirming the substrate reproduces a known external result before its coordination numbers are trusted.

Appendix D: Reproducibility checklist.

Canonical batches. Numbers in §5.1–§5.3 and §5.5 derive from the committed dcc_p1 batch (dcc_p1-20260707T225301-299e08d9, 900 cells). The intrinsic-timescale scaling of §5.4 derives from the dcc_p4a_fine batch (dcc_p4a_fine-20260711T004604-b3aae702, 520 cells): gossip gain $\alpha \in \{0.125, 0.25, 0.5, 1.0\}$ $\times$ speed cap $\in \{15, 30\}$ $\times$ a densified delay axis $\{0, 5, 6.5, 8, 9.5, 11, 13, 15, 18, 22, 28, 34, 40\}$ steps $\times$ 5 seeds, on the rendezvous task at $N = 500$. The $\alpha = 1$, $v = 30$ corner reproduces the corresponding dcc_p1 gossip-rendezvous cells to $\sim 10^{-10}$, so the two batches are directly comparable despite the Gossamer version difference below. The Vicsek anchor of Appendix C is vicsek-20260707T171708-2084915b (45 cells).

The grid. Primitive $\times$ task $\times$ delay $\times$ $N$ $\times$ seed. Primitives no_comm, flocking, dmb_tf_aco, gossip, iccd; tasks rendezvous, consensus, coverage_hold; delay $\in \{0, 5, 10, 20, 40, 60\}$ steps (0–60 s at $\mathrm{dt} = 1$); $N \in \{500, 2000\}$; seeds 1–5. coverage_hold is collected but excluded from the headline figures, and dmb_tf_aco from the collapse panels, for the reasons given in Appendix B.

Fixed parameters. dt=1.0, tau_sec=300, bound=1000, init_spread=500, comm_range=1200 (a connected interaction graph), energy_rate=0 and fault_prob=0 (so agent attrition cannot confound the delay axis), integrator=velocity_verlet, steps=1500.

Environment. Gossamer 0.3.1 (wheel SHA256 b28a5335…); Leviathan base image leviathan-base:py-0.2.1 (digest 1ed753f5…); Python 3.10.12 on Linux x86_64 (glibc 2.35), with numpy 2.2.6, scipy 1.15.3, pyarrow 24.0.0, pandas 2.3.3. The environment lockfile hash recorded in provenance.packages.installed_hash is dc55b4a6… for the dcc_p1 grid and b38afcbe… for the vicsek anchor. The §5.4 dcc_p4a_fine grid ran on a later stack (Gossamer 0.6.0, lockfile hash 4de1e199…, pyarrow 25.0.0); the numerical agreement of its $\alpha = 1$, $v = 30$ cells with the dcc_p1 gossip-rendezvous cells (to $\sim 10^{-10}$) confirms the coordination seam and stepping loop are unchanged across that version span, so the scaling result is on the same substrate as the phase diagram.

Provenance. Each cell’s experiment.json records package versions, the lockfile hash (SHA256 over all installed name==version pairs), a hardware fingerprint, and the full seed tree (exp_seed → gen_seed → candidate_seed → repeat_seed). The git fields are null: the worker runs the engine in-process from a prebuilt container that carries no checkout, so the lockfile hash and the image digest are the reproducible identity rather than a commit. Figures regenerate by aggregating task_metrics.Q_final over seeds by (task, algorithm, delay, N). The run produced 0 non-finite values and 0 agent faults. On requesting the underlying artifacts, see Reproducibility and Data Availability.

Appendix E: Unified symbols. $\psi$ (polar order parameter), $\eta$ (Vicsek angular noise), and $Q$ (coordination quality) follow the shared conventions in the unified symbols table.

The anticipation companion is Anticipatory Coordination via Peer-State Prediction.