Ultra Ethernet ordered delivery: one recovery design checked in a model against the standard's rule

• A checking engine
• Agrees the gate keeps the rule
• The standard's ordering rule
• Refuted by a counterexample

Ultra Ethernet is a networking standard for artificial intelligence (AI) and high-performance computing systems. One of its delivery modes is meant to deliver data in order. The lab modelled one recovery design for that mode and checked, with four separate tools, that in its model the design always keeps the standard's ordering rule. A simpler design fails the same check.

What it shows

Ultra Ethernet is published by the Ultra Ethernet Consortium (UEC). Its transport supports in-order message delivery, and the claim names the mode the lab studied: Reliable Ordered Delivery. The lab's model reads the standard's rule for that mode as a requirement that data reach the receiver in sequence order. A network card that implements the mode needs some way to hold back or drop data that arrives out of order after a loss, and to resume in order once the gap is repaired.

The model and the check

The lab wrote a model of one such mechanism, which it calls a recovery gate, and a model of the standard's ordering sentence. It then asked whether every run of the gate keeps the rule. Four separate checking tools said yes. The claim's word for this is that the gate entails the mandate: in the model, every run of the gate also meets the rule. The lab also modelled a naive design that remembers only one step back. The tools found a run where that design breaks the rule, so the check is not empty: it can fail.

What the limits add

The lab's limits, in our claim file, matter as much as the claim. They call the result a modeling entailment: it holds inside the lab's model, and it is not a legal opinion. In that model, the rule as literally written does not require this gate; many other receivers meet it without the gate. The gate is needed only if the rule is read to also forbid gaps. And in the small model the lab ran, no receiver makes progress at all, because the model has no resending of lost data.

Why it matters, and to whom

This is for makers of network cards, switches and chips that implement Ultra Ethernet, and for the test houses that check them. A designer who picks a recovery mechanism wants machine-checked evidence that it keeps the ordering rule before it goes into silicon, where a bug is costly to fix. The result gives that evidence for one design, in a small model, with a counterexample that shows why the naive alternative is unsafe.

Compliance is not essentiality

It is also a caution about language. The evidence file shows the lab's internal title for this result, which uses the word "essentiality". That word has a specific meaning in standards licensing. Under the usual definition, the one used by the European Telecommunications Standards Institute (ETSI), a right is essential only if no compliant product can avoid it on technical grounds. The lab's own model shows compliant receivers without the gate. So this is evidence that one design complies, not evidence that the design is essential. No legal opinion has been obtained, and the lab's limits say so.

How it was checked

The evidence file records that the check requires every engine's verdict over a fixed, fingerprinted copy of the standard's text to hold. It names one engine, the Apalache model checker, as a tool that a re-run needs.

Agreement among four engines guards against a bug in any one engine. It does not guard against a mistake in the model they are given, and the served files do not show that the engines were given different models. The model is also small: the limits describe it as a model with two sequence numbers. That is enough to expose the naive design, but it says little about behaviour at the scale of a real network.

Testing the check

The lab tested its own check by breaking it on purpose, twice, and the evidence file describes both. In one test, the standard's own sentence was weakened from an absolute "must" to a permissive "may". In the other, the Apalache engine was made unavailable, so that a check still reporting success would be claiming a four-engine result from three. Both times the check failed, as it should. The same file records that a clean re-run needs Apalache installed, and that the re-run is graded as blocked by the environment when it is missing.

What it does not claim

• It does not claim essentiality, and it is not a legal or licensing opinion. It does not claim that the rule requires this design; the lab's limits say the opposite for the rule as literally stated. It does not claim anything about a real network card, or about delivery modes other than ordered delivery.

• It does not claim that the idea is new. In-order delivery by sliding-window protocols is textbook material, and machine-checked proofs of such protocols exist. Badban, Fokkink and van de Pol verified that a two-way sliding-window protocol is equivalent to a pair of first-in, first-out queues. What the lab adds is a check of one more design against the ordering rule of a new standard, with a counterexample for the naive design.

How to reproduce it

The evidence file names the command that re-runs the check. It needs the lab's code at the commit named in the evidence file, Python, and the Apalache model checker.

To test the limits yourself, write a second receiver that meets the ordering rule without the gate, for example a buffer that holds everything until each gap is filled, and run it through the same engines. The lab's own model already found many such receivers. To make the result stronger, add resending of lost data to the model, so that receivers can make progress, and check that the gate still keeps the rule.

Formal statement

$$\begin{array}{c}\mathrm{Gate}\Rightarrow \mathrm{InOrder}\\ \mathrm{InOrder}\nRightarrow \mathrm{Gate}\end{array}$$

In the lab's model, the gate implies the ordering rule; the claim's word for this is entail. The reverse does not hold for the rule as literally written, which is why this is evidence that one design complies, not a proof that every implementation must use it.

Prior art

• Ultra Ethernet Consortium, "Ultra Ethernet Specification": the published specification, which describes in-order message delivery in its transport
• Badban, Fokkink and van de Pol, "Mechanical verification of a two-way sliding window protocol": a machine-checked proof that a sliding-window protocol behaves like first-in, first-out queues
• European Telecommunications Standards Institute, "Intellectual Property Rights Policy": the usual definition of a right that is essential to a standard
• Hoefler and colleagues, "Ultra Ethernet's Design Principles and Architectural Innovations": background on the standard's design

Evidence

• The evidence file for this result
• Our claim file, with its limits
• All our published files, each with a fingerprint you can check

Related results across the group

• One protocol rule, compiled into five targets for hardware, kernel, firmware and logs
• The chip netlist whose area and delay are published matches its design: a formal equivalence proof
• Searching for combined Wi‑Fi sign-in attacks without hints: a budgeted search and a complete one
• The same result on VerifyCore Labs, our parent lab

All results from OrbitalProof · The OrbitalProof home page