Show HN: Starboard, Rules of the Road for Satellites

There are now roughly 15,000 working satellites in orbit, about two thirds of them in a single constellation, and plans for well over a hundred thousand more. When two satellites from different operators are predicted to pass too close, the operators still mostly sort it out by email and phone: who has the better data, who has fuel, who will move. That works when it is a handful of events a week between people who answer. It does not work when one side is slow, unreachable, out of contact, or a dead object that will never answer at all.

What is missing is not better tracking. It is an agreed answer to a simple question that both sides can compute on their own: who gives way?

Ships solved this with the rules of the road (COLREGS). When two power-driven vessels cross, the one that sees the other on its starboard side gives way, and the other holds course. Both captains look at the same situation and reach the same conclusion. Nobody has to call anybody, and the vessel that holds course has a job too: be predictable.

Starboard is that convention for spacecraft, written precisely enough that two computers built by different companies, compiled with different toolchains, reach the same verdict without exchanging a single byte.

Each satellite receives the standard close-approach warning, a CCSDS Conjunction Data Message (CDM) from a tracking provider, and runs Starboard on it. If the encounter is risky (probability of collision at least 1 in 10,000, or a predicted miss under 1 km), it walks the same chain of five rules. The first rule that decides, decides:

The craft that gives way plans the smallest burn that restores a safe miss (a Clohessy-Wiltshire plan), and after the encounter two return burns put it back in its slot. In the crossing at the top of this page the predicted miss is 150 m with Pc 1.043 × 10⁻³; ACME-1 burns 1.012 m/s, passes 1,280 m clear, and is home again after 2.689 m/s in total.

Both craft evaluate the rules on the same ordered pair, sorted by international designator, so agreement is not something that is hoped for. It holds by construction. That is Theorem 1 of the spec, and it is machine-checked with CBMC.

"Roughly the same answer" is not good enough. Near a threshold, a one-bit difference in a probability can make each satellite conclude the other will move. So the property Starboard actually has to deliver is that two different computers produce identical bits for every quantity that affects the verdict. Ordinary floating-point code does not do that: compilers fuse multiply-adds, x87 keeps excess precision, every libm has its own sin and exp, and strtod implementations differ in the last place.

The controls matter as much as the passes: a build with x87 excess precision or FMA contraction produces different bits, and the boot self-test catches it and refuses to fly. A computer that would get the maths wrong does not get a vote.

Running the transcripts on FPU-less ARM turned up one single-ulp difference in a sine. Tracing it led to the last operation of the cosine kernel, a 1.0 + m with a tiny negative m, where libgcc's software double addition (__aeabi_dadd, GCC 13) returned the wrong neighbour. A 200,000-case fuzz of double addition found 897 mismatches, all of them effective subtractions with an exponent gap of exactly 33, all rounded down. Reading the source suggests why: in the alignment path for large gaps the true round bit is folded into a sticky bit before a one-bit renormalisation needs it.

For Starboard the consequence is concrete: two satellites using that routine would agree with each other and silently disagree with everyone else. The self-test now probes rounding at exponent gaps 31 to 34 and refuses such a platform, and the C library ships a correctly rounded replacement, checked against hardware on 49.4 million additions and subtractions. Write-up: CROSS-ARCH.md.

The design question is not only "do they agree" but "what happens when they don't, or when someone lies":

Starlings in a murmuration never hold a meeting. Each bird watches its neighbours and a turn ripples through the flock. When a Starboard craft commits to a maneuver it broadcasts a 204-byte maneuver notice over its inter-satellite links; neighbours relay it hop by hop and keep a shared ledger, and each checks the mover's new path against its own. In the demo, a notice crosses a 72-satellite shell in 9 hops and every ledger ends with the same digest.

The interesting case is a tight formation. Near the end of the film, eight craft fly 2 km apart and one must dodge a fragment. Its first plan would drift through three neighbours' slots, so they raise flock alerts, and because all eight hold the same CDM and ledger they screen the same candidate plans and reach the same choice: a later burn by the mover alone, 5.33 m/s, nobody within 1,024 m. Moving the whole formation in unison was evaluated too, and lost on both conflicts and fuel. The flock warns; it never decides.

Starboard is ready for a hardware-in-the-loop campaign and a demonstration mission in shadow mode, where it decides and reports but a human approves every burn. It is not flight-proven. Specifically:

The full, unflattering list is OPEN-PROBLEMS.md.

$ git clone https://github.com/Tokeloshe/starboard-protocol && cd starboard-protocol $ cmake -B build && cmake --build build && ./build/starboard_crossing_demo Pc bits ACME 0x3F5117B3E9975E2E | ORBX 0x3F5117B3E9975E2E IDENTICAL [ok] ACME-1 verdict: I GIVE WAY (Rule 4 - starboard) ORBX-9 verdict: I STAND ON (Rule 4 - starboard) T+000:00 TCA - closest approach 1280.0 m >= R_SAFE 1024 m [ok]

$ make -C ports/c && ports/c/murmuration hop 9 ##########################################*############################# 72/72 know flock ledgers: ALL 71 IDENTICAL (digest 1E3AC8C816631BCF on every satellite)

The C99 flight library is 43 KB of code and 25 KB of RAM, with no heap and no recursion, MISRA C:2012-checked, and fuzzed with about 129 million hostile inputs. It reads CCSDS CDMs, speaks CCSDS telemetry, and integrates with NASA cFS, F′ or bare metal. A header-only C++17 reference implementation produces the same bits.

The specification is CC BY 4.0, free to implement forever, because a convention only works if everyone can adopt it. The reference code is AGPL-3.0-or-later, with a commercial license for proprietary flight software.