Who goes first, and the promise only one driver could read

Part five of a series. The earlier parts cover what DrivEngine is, the two layers, junctions, and the three tiers of a driver.

Two cars approach an unsignalled junction. Their paths cross. One of them has to give way.

This is the hardest problem in the project. Not the geometry, which is settled at bake time. Not the routing, which is a search. This. Two independent agents, each holding half of the picture, having to reach the same conclusion about a piece of road, without talking to each other.

I have rewritten this part more times than any other, and this article is about the attempts that failed, because the reason they failed is worth more than the thing that eventually worked.

The obvious rule, and why it is not enough

Start with the simple version. Each driver looks at the conflicts ahead on its own path. For each one, it estimates when it will reach the crossing and when the other car will. Whoever gets there clearly later gives way. A time margin keeps the comparison from flipping when the two estimates are close.

This works beautifully on an empty road with two cars, which is exactly how much traffic you have when you write it.

Then you put forty cars in a small town and watch two failure modes appear.

Both cars go. Each computes an arrival estimate, each concludes it is the earlier one, and they meet in the middle. This happens whenever the two estimates are built from slightly different information.

Nobody goes. A waits for B, B waits for C, C waits for A. Nothing in the rule notices that the wait forms a ring, so the ring stands there until the simulation ends. In a small grid town this can lock a whole district.

Both failures come from the same root: a decision that only makes sense if both parties reach it consistently is being made twice, separately, from two different seats.

Promises, and why they have to be remembered

The first thing you need is stability. A driver that recomputes the race from scratch every tick will flip its answer as the two estimates cross, so it slows, sees that it now arrives first, accelerates, sees that it arrives second, slows again. The car stutters at the mouth of the junction and both drivers keep changing their minds.

So a yield is remembered. When a driver decides to give way to a particular car at a particular crossing, it holds that decision. I call it a promise, and the word is deliberate: it is a commitment to another driver that shapes what that other driver does.

Which immediately raises the question this whole article is about.

A promise has two seats. One driver makes it. The other driver relies on it. If the two seats can disagree about whether the promise exists, you have something worse than no promise at all, because now one driver is confidently driving into a gap the other one is not leaving.

There is an invariant for exactly this, and it is written as a plain sentence in the test code: a car only expects a yield the other driver still gives. Every time a design has broken that sentence, the crashes came back.

When nobody moves

Rings still happen, even with stable promises, so there has to be a breaker. After a deadlock timeout, one promise in the ring is released, chosen deterministically so that every driver involved agrees about which one it was.

There is a second kind of ring that has no promise to release: cars that are simply physically in each other's way, each one blocked by the geometry rather than by a decision. For those, the breaker releases one junction guard instead, and the release is latched until the chosen car has actually entered the junction, so it does not evaporate one tick later.

Recovery is not optional. Prevention gets you most of the way, and the remaining cases are the ones you cannot enumerate. A deadlock that resolves after a few seconds is a traffic jam. A deadlock that never resolves is a bug report.

The starvation bug, and the two halves of its fix

The first long waits came from a cause far away from the visible symptom.

The symptom was starvation. Cars at one approach of a junction waited enormous amounts of time, half a minute at a stretch, while other approaches flowed. The invariant that says a wait at a junction is bounded was breaking constantly.

The obvious reading is that the race is unfair, and that the fix is some kind of ageing or turn taking. That reading is wrong, and several designs built on it made things worse: pairwise oldest-first priority produced cars crossing into each other on the same tick, and various turn taking and phase schemes cost between a third and two thirds of the town's throughput. One of them, a persistent short phase for one movement at a time, produced nearly a thousand deadlock ring breaks.

The actual cause was a small lie in the arrival estimate.

A stopped car has no speed, so an arrival estimate based on its speed is infinite, and a race against an infinite arrival is no race at all. So a stopped car is credited with a small nominal speed, enough that the comparison means something. Fine for a car that is stopped and free to go.

But a car stopped at the back of a queue is not free to go. It cannot move until the car in front moves. And the nominal speed told every other driver in the junction that it would arrive in about two seconds. Combined with the latch that keeps promises stable, one car sitting in a queue could hold an entire approach still for as long as the queue lasted, because the promise never got reconsidered while the car it named was still short of the crossing.

The measurement that found it was unglamorous and decisive: at the worst junction, the four worst movements were waiting on dozens of distinct cars, and those cars were sitting on an approach road at an average speed of around half a metre per second. Not arriving. Parked in traffic.

The fix is two rules, and the important part is that they only work as a pair.

First, a car that is held in place by something it cannot control gets a near zero nominal speed rather than the normal one. A car that is free to go still gets the normal credit, or a junction full of stopped cars would never release any of them.

Second, a held promise ends when the car it names is stuck and is further away, in time at its real speed, than the deadlock timeout.

Now the pair. The second rule has to be asked from both seats. The driver holding the promise has to drop it, and the driver relying on it has to know it was dropped, on the same tick, from the same question. When only half of that landed, the invariant about promises being shared went from a handful of violations to more than eighty. One seat had let go and the other was still counting on it.

The full fix paid for itself across the board: trips up by between a tenth and a third depending on the seed, throughput up by similar amounts, total standing time down by about half, the longest single wait cut from well over a minute to something survivable, junction standstills down by between half and almost all of them.

It also made something else worse, and that should be said out loud: cars that used to crawl up to junctions now arrived at speed, which meant more braking and more late plans. Fixing one thing revealed the next one. That next one is part seven.

The commitment problem

Now the failure I actually want to talk about.

Once a car is far enough into a junction, giving way is no longer possible. It cannot stop in time, and stopping across a crossing is worse than continuing. That car is committed, and the correct behaviour for anyone else approaching that crossing is to let it finish.

The measurement said this was the dominant remaining case. At the first tick where two drivers in a collision named each other, roughly two thirds of the episodes were one car committed while the other had concluded it could go first.

So the fix writes itself. A committed car should publish its claim, and other drivers should read it and wait.

I built that three times.

Shape one. The claim holds while the committed car will arrive within the deadlock timeout.

Shape two. A stricter version: the claim holds unless the other driver would clear the crossing before the committed car gets there.

Both made everything worse. The collision counts went up, not down. Worse, the invariant about promises being shared went from single digits to around fifty in both shapes, and deadlock rings appeared where there had been none. Shape two is strictly less aggressive than shape one and it was worse on every collision count, which tells you the model is wrong rather than the tuning.

Shape three. Something much more modest: when a driver is already going to wait, and the car it waits for is committed at the same crossing, relabel the wait and let the waiting car slow more gently instead of holding its current speed. It changes who slows, never who waits, so it cannot rot the promise graph the way the first two did.

It was harmless, and it was useless. Every number inside the noise. And digging into why produced the sentence that this entire article exists to deliver.

Why all three failed

The analysis tool walked every crossing episode and reported what each driver read about the other. The relabel fired five times in over two hundred episodes. The pair read as both committed in nearly every one.

So at the tick when the second driver decided to commit, the first driver was not publishing a claim the second one could read, even though a tally taken three seconds later says both were committed.

The reason is structural, and obvious once you have seen it:

A driver's claim exists only while the crossing is still inside that driver's lookahead. A driver's holds are rebuilt every tick from what it can see ahead of it. A car that is on the crossing, or past it, no longer has that crossing in front of it. So it publishes nothing, at exactly the moment when the fact matters most to everybody else.

The claim is a note in one driver's head, and it is not there when the other driver needs it.

That kills the entire family. Not shape one, not shape two, not shape three. Any rule where one driver publishes something and another reads it, when the thing being published is derived from the publisher's own forward view. No bound on the claim helps, because the problem is not how long the claim lasts, it is that the claim has already stopped existing.

Moving the claim

The arrival race works because both drivers ask the same question from shared data. A one-way published claim does not have that property. It also disappears when the publishing car stops looking at the crossing.

The claim describes a shared piece of road, so it needs to live on that road rather than inside either driver. In this case, the junction has to own it.

Part six moves the claim onto the junction. It fixes this failure, but it also makes traffic wait longer. That cost had to be measured rather than explained away.