Jobs should execute at most once: simple, right?

[plaidfinch]

Nope

Unfortunately, distributed systems.

The desire

An operator submitting a job to the rack would like to rely on the following hierarchical mental model:

• At any given time, there is at most one support session on the rack.
  • Creating a new session automatically ends the previous session.
  • Sessions can also be manually ended by the operator.
  • Each session consists of a queue of jobs, each job addressed to a non-empty set of sleds in the rack.
    • Each job is only executed by the sled(s) to which it is addressed.
    • While the session is alive, each sled attempts to execute its queue in linear sequence from the start of the session.
      • Sleds execute their queues independently, without blocking on one another, so each sled potentially has a unique position in its own queue of jobs.
      • No jobs addressed to a sled are skipped by that sled unless explicitly aborted by the operator while enqueued and not yet executed. (Note that while sush supports a "skip job" functionality, this is a request for permission from Oxide to skip the job prior to its distribution to the rack. Operator abort terminates a job once it has already been submitted to the rack.)
      • Every sled executes its filtered sub-sequence of jobs in the same order as every other sled, and this order matches the order in which the jobs were authorized by Oxide Support.
      • Optionally, jobs may specify that they be run concurrently with other jobs, so while the order of jobs starting is fixed, their order of ending may be nondeterministic in this case.
      • If the session ends before all the jobs are finished on a given sled, the sled may not finish executing all the jobs in the session, but will pick up executing jobs from the start of the new session.
      • ⭐ A given job executes at most once on any given sled, no matter what.

The operator expects all these guarantees to be true even if the system is arbitrarily degraded: this is when they will be using sush, and it must follow their mental model without surprises — especially without hard-to-explain surprises! — at their greatest moment of need.

In this document, we will focus primarily around the mechanisms to guarantee:

Important

⭐ A given job executes at most once on any given sled, no matter what.

However, a great deal more mechanism and background need be explained in order to lead up to the punchline(s), much of it justified by the other requirements in this model. Thus, we begin:

Unfortunately, distributed systems

Consider that this mental model must remain sound even when:

• NTP is unavailable, so there is no trustworthy time source to use for ordering observed events or messages.
• The control plane is down, so there is no strongly consistent data store available.
• Enough sleds are out of service that trust quorum cannot unlock, meaning that there is not even an encrypted dataset locally on each sled to store the job queue durably (we reject storing it on the M.2 unencrypted, because this would expose the plain-text job history).
• Arbitrary failures may occur on individual sleds, before and during the support session, up to and including arbitrarily frequent crashes, restarts, and permanent hardware failure.
• Arbitrary disruptions to network topology may occur between individual sleds, before and during the support session, up to and including frequent and prolonged partitions between arbitrary sleds, including transient or permanent failure of one or both switches. (In our model of connectivity for sush, we think of the network as an arbitrary graph topology, even though the realizable topologies are likely a subset of this space. If it's correct for all topologies, it must be correct for whichever occur in reality.)

Causal gossip and its consequences

Sush endeavors to uphold this model in these very adversarial circumstances by hewing to a design of eventual, causal consistency. We rely on the gossip library rumors for causal gossip point-to-point between sleds. This gives us the ability to assign a partial ordering to all messages, including jobs, sent to and between sleds. Because the rack is a distributed system, it does not give us the ability to assign a total ordering to messages.

This would have several consequences for the operator model of sush, which we ameliorate through additional mechanisms:

1. In reality, there may be more than one session at a given time on the rack, since a session could be created and used on either side of a network partition. We resolve this:
   • Two sessions can only coexist as long as they are unaware of one another. As soon as they meet, at most one survives.
   • If two sessions meet through gossip and one started causally after the other, the older session is terminated (this spreads, just like all other gossip, throughout the network).
   • If two sessions meet through gossip and they started concurrently, both are mutually annihilated, and a new session must be established, which will definitionally be in both of their causal futures.
2. The causal versions of the job-start messages are insufficient to ensure that jobs execute in the same linear sequence on every sled, and it's certainly insufficient to ensure that their order of execution matches the specified ordering by Oxide Support, because signed jobs could be submitted out of order to the rack, or even submitted concurrently to different sleds in the rack. We resolve this:
   • Each job's ID is the hash of the preceding job, or, if it is the first job, the hash of the session ID.
   • Knowledge of a job is insufficient to execute it on a sled; the sled must first also know about all the jobs that preceded it in the hash chain.
   • Jobs are started strictly in the order implied by the hash chain, though if specified, they may run concurrently to one another, and may not finish in the same order.

Bootstrapping the gossip network

A third, hidden emergent precondition of causal gossip is that we need to ensure all the causal versions originate from the same "universe of gossip". Rumors uses interval tree clocks to stamp its causal versions, and comparing two versions is meaningless unless they originated from some shared "seed" in time and space. Rumors enforces this: each of its peers declares a unique 128-bit nonce to identify its own causal universe, and refuses gossip with peers who do not share this identifier. A peer which is joining the network may either declare itself the seed, or bootstrap from another peer who is already joined.

Typical treatments of interval tree clocks require a single distinguished originating peer, but sush has no such asymmetry to rely on. We resolve this using the mechanisms in rumors:

• We bootstrap sush's gossip network at every cold boot of the rack by having every peer declare itself the seed, and then attempt to gossip with randomly selected other peers.
• At first, every such gossip will fail due to mismatched nonces.
• For each conflict, either side determines how to proceed based on the lexicographic comparison of its own (min_ticks, network), where min_ticks is the tallest causally ordered chain of events in its set of versioned messages, and network is the random nonce, used as a tie-break.

Because this comparison is anti-symmetric, each peer will agree on who wins the little game. The losing peer discards its local identity and messages, and attempts to bootstrap from the winning peer, joining its network. Provided that the sets of messages eventually quiesce during this bootstrap period (in practice, there will be zero messages during this time), the network quickly converges on a single winning nonce, with all peers causally related to the seed who happened to win. The lexicographic pair chosen for comparison is important: by embedding min_ticks as the winning comparator, we ensure that any new sled joining the existing network will deterministically lose and join the existing network — comparing the network alone would destroy the existing gossip set with a coin flip's probability on each late-joining sled's addition.

The takeaway: on a reasonably healthy cold-boot of the rack, i.e. one in which it is not split-brained from the get-go, the gossip network will extremely rapidly converge to a single causal universe, where all subsequent messages can be partially ordered against one another. Once a sled has booted and connected to the established gossip network, we can rely on it remaining a part of that same causal universe, unless it comes into contact with another partition with a greater min_ticks. In the case where a sled's partition has no messages in gossip, this takeover happens still, but we don't care because there's no data to care about losing.

The only worrisome residual case is one in which the rack cold boots split-brained: in this case, the halves of the split will establish stable, but independent, causal universes (they necessarily must!) and if separate support sessions are initiated each with one half of the split, those two causal universes of gossiped messages will each become non-empty. If and when the split is resolved — if it is resolved before another cold boot of the rack — those halves will collide, and the one with the lesser min_ticks will be obliterated. All records of all of its support sessions will be wiped from memory, and replaced with the winning universe's information. To emphasize, though: this is only possible if the split pre-exists and continues through a cold boot, and is only problematic if two simultaneous support sessions are initiated on either side of the split.

Enough preamble: how do we do it?

The original question, if you can recall back that far above this wall of text, is: how can we ensure jobs are executed at most once, no matter what? This is harder than it may seem.

At its heart, we may be flummoxed at first by the absence of reliable persistent storage: we cannot rely on the option of persisting the set of causal messages (or derived state), because jobs cannot be stored on the unencrypted M.2 drives (they could in principle contain confidential information), and we cannot rely on the presence of an unlocked trust quorum, so they cannot always be stored in the crypt dataset on some arbitrary U.2 drive. But without any form of local persistence, a rebooting or crashing sled would come back, rejoin the gossip network, and immediately attempt to re-execute all the jobs intended for it, from the start of the most recent session.

At first blush, we might think gossip can save us: sush does broadcast confirmation and status messages when it starts jobs, so perhaps a restarting peer can read back through history to learn whether it ran a job or not! Alas, we cannot rely on gossip remembering for us: we do not require gossip before executing a job (so that even a single sled is permitted to run sush), and even if we did, there's no guarantee that our status messages were preserved by gossip, since the sleds which happened to receive them might have crashed before distributing them to the sleds who remain.

The only way to definitively remember what we ourselves have done is to remember it ourselves. But where, and how?

• Where: we must use the M.2 drives, because they are the only storage we can rely on being available always.
• How: we must persist only metadata, never details of jobs or gossip messages, because the M.2 is unencrypted.

As a side-note, we must persist all data to both M.2 drives, and verify that our reads match (or that one drive is entirely missing our persistent state), to avoid situations where the intermittent or permanent failure of an M.2 drive changes our perceived persisted state. This is already implemented, and we deem it acceptable, because the M.2 is not a customer-replaceable part. If an M.2 fails in the field, sush will cease operating on that sled, with a diagnosable error, and the sled should be RMA'd.

Okay, so what metadata?

Let's build this up piece by piece. We'll call the state we're storing a Boundary because it's the boundary between what has been executed, and what has not.

Store the job ID

A natural starting point is to store the job ID of the last-launched job, which globally-uniquely identifies the job!

struct Boundary {
    last_executed: JobId,
}

Is this enough? Let's think: after a reboot, we rejoin gossip and begin receiving a stream of jobs, starting at the "beginning of time" from the perspective of the gossip set. If all we have is the last-executed job ID, we must not execute any of these jobs until we reach the specified job ID, at which point we can begin executing jobs as we were before (notably, we do not blindly execute jobs that we learn about after the boundary, since causal message ordering may contradict job sequence ordering — just as ordinarily, we execute sequentially only the jobs which hash-chain onto the boundary). Because jobs in a session are linearly totally ordered with respect to each other, the job ID is enough to tell us precisely where to draw the boundary. We picked up where we left off, hurrah!

End of story? Unfortunately, the qualifier "in a session" is ... ugh, I'll say it ... load-bearing. While jobs within a session are totally ordered with respect to one another, sessions are only partially ordered with respect to one another. This means that if there's a network partition, we could reboot and end up connected to a partition which holds an entirely distinct session. So long as the partition holds, we will never learn about our persisted last-executed job, and until we do, it's not safe for us to execute anything.

Store the session ID

So maybe we should store the session ID too:

struct Boundary {
    last_session: SessionId, // new!
    last_executed: JobId,
}

What do we do when we find our stored session ID mismatches the most-current one in the partition we've joined? Well, our job ID is irrelevant for this session, so we can discard both, and continue executing everything in this session...

...but then suppose we reboot again, and this time we rejoin the partition holding the original session where our first-stored job ID originated. Now we don't know about it! And by the same rule, we'd gladly discard the session ID and the job ID from the other session, and start executing jobs from our original session. Yikes!

Important

This pattern is a critical minimal example that motivates all the rest of this machinery. Let's take it apart once more, step by step:

1. The network is partitioned into two halves, A and B.
2. Each side of the partition diverges in some manner — in this case, we end up with two different sessions on the opposite halves, but we'll demonstrate this problem again with other kinds of divergence.
3. Sled, X, in side A of the partition, executes Job 1 from side A.
4. X powers down, is reconnected solely to side B, and powers up.
5. X, in side B of the partition, executes Job 2 from side B.
6. X powers down again, is reconnected solely to side A, then powers up again.
7. X is now in a state which does not record that it had previously executed Job 1 when it was on side A.
8. X now executes Job 1 again.

I call this shape of pattern a "partition flip-flop".

It is now our mission to shield ourselves from the flip-flop.

Store every job ID and session ID

The core of this problem is that we overwrote our state from side A when we joined side B, which caused us to replay jobs from side A when we eventually rejoined it. A simple solution would be to never overwrite information, instead storing all the session/job pairings we learn about. So then:

type Boundary = BTreeMap<SessionId, JobId>;

Then, the same sequence plays out with no damage done: we can flip to a new session (over a reboot), start executing new jobs from it, record the per-session job ID boundary, and then flop back to the original session (over another reboot), and resume executing precisely where we left off.

The only (big) downside is that for safety, we can never evict entries from our mapping, or else we risk replay.

Never, you say? But there's only 32 sleds in the rack! Shouldn't that mean we can only ever track 32 sessions?

Ah, but dear reader, alas! A sled can always power-cycle and get a new session, which means over time, there is no bound to the number of entries in our map! What's more, we don't know which ones to evict, because a session that is observed to have been superseded in one partition may not yet have received the bad news in another...

Store only one job ID and session ID... but also store the session's version

But what if we knew which sessions superseded one another? After all, while sessions are not totally ordered, they are partially ordered. We already use this to great effect to maintain the partial illusion of "one session per rack"; can we use it here?

Indeed, suppose we do this:

struct Boundary {
    last_session_version: Version, // new!
    last_session: SessionId,
    last_executed: JobId,
}

Now let's run the flip-flop again: when our poor sled reboots from side A to side B, it now knows the casual version of session A's start-message, which I'll gloss as "A's version" hence. We now have a case analysis on B's version:

• If B > A, then B supersedes A and we should join B and replace our durable state with that for B
• If B < A, then A supersedes B and therefore we already witnessed the end of B in our past life, now memorialized by our boundary state — so we may participate in gossip with B, but we must never run a job there, and leave our state untouched
• If B || A, then the two sessions are dead men walking: they will mutually annihilate as soon as they encounter one another, and the only safe disposition is to gossip with B but never run a job there, and leave our state untouched
• B cannot equal A, because no messages in the causal gossip universe can have equal versions

Now the flip-flop doesn't have symmetry: if B > A, we'll never run another job in A, so our re-run risk is nil. If B < A or B || A, we never ran jobs in B, and we never rewrote our state, so we can continue onwards in A.

We also need the rule that if we're "sitting out" a session because it was causally prior or incomparable to our stored session's version, we should re-evaluate this each time a new session shows up via gossip: if it's causally posterior to our stored session, we run the same case logic and determine to join it.

This solution uses fixed space, unlike our last one, and all it sacrifices is that sleds which reboot across a partition will not run jobs until the partition is unified. I actually think that this is a desirable property, worth restating:

Important

We prevent sleds from executing jobs if they move between partitions acausally, because they can't carry their rumors with them.

That's what we're doing here, and it makes things work out very cleanly.

Aren't you forgetting something?

At the beginning of this screed, I described how everything works out so cleanly and nicely if we can manage to bootstrap the rack into a state with a single shared causal universe. But what if we can't? What if the rack cold-boots split-brained, or, equivalently, we add sleds and they cannot connect to the whole network, creating a partition that has never touched the extant gossip network? Unfortunately, sush cannot throw up its hands. We must work here, too.

Let's pull another flip-flop, this one about causal universes, not sessions. You see where this is going, right? We don't record the causal universe, so if we reboot-flip a sled into a partition in another causal universe, its causal comparisons with the sessions in that universe are totally meaningless — comparing versions from two universes is not even a valid question.

Let's add another field:

struct Boundary {
    last_network: Network, // new!
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

This way at least we know when we've got a mismatch! But we're still having a bad time, because unlike sessions, networks aren't even (meaningfully) partially ordered: they can only be compared for equality because they're random nonces.

The particularly studious reader may recall something interesting from our preamble: we have already crafted a deterministic procedure for resolving conflicts between networks — the anti-symmetric comparison we use for gossip bootstrap: compare their min_ticks, then compare their identifiers, as a tie-break. Could we use that here?

I thought so, and then it turned out that it doesn't really work. Imagine we did this:

struct Boundary {
    last_network_version: Version, // tentatively?
    last_network: Network,
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

You could imagine that every time we update the boundary on disk, we capture the causal frontier version of our gossip set, allowing us, when transplanted into another universe, to decide whether our previous universe is going to dominate this one, whensoever they collide in the future. Could we use that to select whether or not to join the new universe and start executing jobs there?

Sadly, no, not safely: in a persistent split-brain, the two partitions continue onwards indefinitely, which means that the determination of which universe dominates is not stable: it can slosh back and forth as messages land in either side's gossip set. Such universe-sloshing is transient and benign at the moment of bootstrap in a healthy rack, because everything immediately converges on a single causal universe before even one support session could be initiated, no less two. But if we allowed a sled to adopt itself into the other side of a partition based on the min_ticks count of one side dominating, two concurrent support sessions on either side of the split could drive the relative min_ticks counts back and forth, inducing precisely the flip-flop effect we're trying our darnedest to stamp out.

Store every network's boundary

When we were faced with a similar problem on the level of sessions, we tried at first to resolve it by storing a map from session to boundary (which was then just a singular job ID). There, we improved by using causality to our advantage. Here, we have no such hope because causal universes are unordered entirely from one another. But could we still do the map approach?

type Boundaries = BTreeMap<Network, Boundary>; // new!

struct Boundary {
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

Sure, but then we have to persist every network we've ever seen forever. Discarding one isn't safe, and for the same reasons as elucidated above for sessions, there's no finite bound to the number of networks that occur over time, and we have no way to locally tell when one no longer exists anywhere in the rack. Dropping anything from the map leads to a probability that we could, in this very specific flip-flop type scenario (which, please note, is a minimal exemplar of a family of situations), re-execute a job.

Maximum growth of this proposed grow-only file is something on the order of a kilobyte per sled reboot, forever, so call that 32 sleds times once per minute, on the top end, if things are going wrong very fast, everywhere. That's almost 50 gigabytes on the world's worst weather day for the rack. Even at a tenth or a hundredth that growth, it's not acceptable for the M.2.

The least worst option

Let's zoom out for a second. At this point, we have designed a set of mechanisms which almost protect us from job re-execution in almost every possible scenario. But not all! And we really want the system to fail closed, because the fail-open behavior means that just the wrong reboot behavior during a particular shape of network partition could lead to re-executing an entire session's worth of jobs on an arbitrary number of sleds. This could drive the rack into an unsupported state, without operator intervention. We do not want this.

But... precisely when can it happen? All this needs to be true:

1. There is a network partition which has existed from the moment one half of the partition has booted (either the rack booted split-brained, or a set of sleds rebooted into a partition from the rest of the rack). This "from boot" requirement is necessary to trigger the distinct irreconcilable causal universes.
2. There is a live support session on both sides of the partition.
3. At least one job addressed to a sled is submitted on the side of the partition it starts on.
4. The sled shuts down (or sush crashes), reconnects to the other side of the partition while down, then comes back up.
5. At least one job addressed to the sled is submitted to it while it's on the other side of the partition.
6. The sled shuts down again (or sush crashes again), and reconnects back to the other side of the partition while down, then comes back up.

It's possible! It's even possible, though unlikely, in the absence of malfeasance. We must handle this case, I believe. But must we handle it with grace?

Outcomes I don't accept:

• The affected sled is permanently unable to accept any new jobs, forever, and the operator cannot fix this. (if we decline to participate in the other network, we could be locked out forever if the partition resolves and that network becomes the only one.)
• The sled re-plays jobs it has already executed. (This would happen if we did the simple thing and replaced the state when moving networks.)
• We blow up the entire gossip network and start everything from scratch. (This is possible to do, but the details get fiddlier the more I write them out, and I have a better idea, below, that's much less destructive.)

Outcomes I can live with (surprisingly — and only because of the unlikelihood of the situation):

• The sled fails to execute any prior jobs which were addressed to it, including those which were submitted after the last job it executed, skipping forward to the present moment and accepting new jobs after this point. This notably violates our otherwise-sacrosanct linear-chain invariant for sessions, but I think it is the least-worst solution to this problem. I welcome dispute! Below, I explain how this could work.

But how? There are two problems here:

1. Detection: How do we know that we've been universe-flip-flopped?
2. Actuation: How do we reliably cause the sled to fail to run all prior jobs addressed to it, while accepting any jobs submitted after the moment it makes this cutover?

Detection

Recall the Boundary state we landed on:

struct Boundary {
    last_network: Network,
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

The problem solved by the last_session_version is establishing a directed edge between sessions, so we can't flip-flop between them: we only move one way along the directed edge, from earlier versions to later ones (and we park at concurrent ones until the partition heals).

We can't do quite the same maneuver for causal universes, because they don't have any inherent ordering between them, and because universe-sloshing due to min_ticks means there's no deterministic choice based on current state, either. But we can establish an arbitrary directed edge, written at the time we traverse it.

All credit to @plotnick for this final keystone in the solution: in addition to the boundary struct above, we track a Bloom filter which represents the set of all past networks we've left behind. If we receive a job request meant for us which we would actually execute (i.e. the session is live and latest):

1. We check the current gossip network against the one in our boundary file: if they match, all done.
2. If they don't match, check the Bloom filter for this network.
   • If there's a hit (and we can size it so that false positives are negligible), we do not execute the job, we instead log an error in the gossip set indicating that we are locked out due to a universe flip-flop (or more operator-legible language, ideally). Then, we proceed to the next section and "actuate" — that is, we cause ourself to permanently transition so that previous jobs addressed to us will not get executed by us, but future jobs addressed to us will. How?? Read on.
   • If there's no hit, mark our previous network identifier from the boundary file in the Bloom filter now, durably on disk, then overwrite the boundary file with information about the current network, session, and job, and execute the job, then continue on normally.

It's important that the flip-flop reset only engages when we actually would have potentially re-executed a job, so that it does not engage during normal initial bootstrap of the gossip network, when it's expected that there are no messages at all — or at most, one causal universe of messages from a single support session. If we triggered the reset on every universe flip-flop, with no need for actionable message content, we'd reset during every bootstrap. This is the maximally liberal check which still prevents the re-execution failure.

Actuation

Okay, so we detected and prevented the universe flip-flop, but now we've locked out a sled from executing jobs. If we didn't do anything about this, it's a coin-flip whether after the partition heals, it will be permanently locked out, or allowed back. We must allow it back, but safely. Here's how:

When the sled logs an error to the gossip set, at that instant, it captures the version of the frontier of the gossip set (which is equal to the version of the error message it just injected). This version marks a unique point in causality: every job submitted strictly in its future light-cone cannot possibly have originated prior to the moment in real-life linear time when the sled discovered the flip-flop. As a consequence, it is safe to execute any job which has a version strictly in the causal future of this moment. It skips executing each job which is concurrent to or in the causal past of this safe threshold, which will potentially skip it forward in time past jobs that it otherwise would have been scheduled to run. It should probably log errors for each of those, for visibility.

In brief: this mechanism causes a sled that is flip-flopped across the boundary of a universe partition to skip running any jobs which were queued for it to run while it was "out of universe", and pick up past the point it returned to.

Some more notes: this is almost, but not quite, Claude's earlier suggestion to track the causal frontier of the gossip set at network join, and filter out jobs that aren't in its causal future. This suggestion feels superficially similar but fails to achieve our goals:

1. It means that jobs queued before a reboot are skipped after a reboot.
2. It does not protect us from re-running jobs that exist in the causal future of whichever potentially out-of-date sled we happen to connect to on first resumption of gossip.

By contrast, this solution generates a unique local point in causality space by capturing the version of a locally originating message, which guarantees that this is "fresh" and nothing else in the gossip set could possibly be in its future, thereby solving (2) above. It also only engages precisely where it needs to, to prevent replay of jobs, and otherwise permits a sled to learn about jobs queued for it upon a reboot, executing them normally, thereby solving (1) above.

A final note: I believe that it might be possible to do away with the Bloom filter construction and simply detect universe mismatches and immediately trigger the skip-to-my-own-lightcone resolution. There are corner cases with keeping it, and corner cases with not keeping it. I would potentially want to err on the side of the simpler construction, but we should think through it together.

In conclusion

Thank you for coming to my TED talk!

[plaidfinch]

I asked Fable 5.1 for its review of my issue.

---

TL;DR: Design checks out and fixes a real replay hole in the current covered_by/is_live approach (verified by construction).

Two must-fix gaps:

1. insert the old network into the Bloom filter on every boundary network change, not just the no-hit branch, or a second flip-flop replays; and
2. the no-hit branch depends on session IDs being universe-unique, which holds only with the sled-bound IDs on the locker branch.

Keep outcome and store the successor job ID. The 50 GB estimate is off by orders of magnitude, so a capped exact map is worth reconsidering over Bloom-only. Don't drop the filter: mismatch-triggers-lightcone would skip the first job rack-wide after every cold boot.

Or, if you want to read some more Claudish (I think it is worth reading this, it gives more color to the above, and some other details):

Details

Accuracy

The issue is accurate on the mechanisms it describes, and it is written against the locker branch rather than main. I verified these claims against the code:

• Dominance rule: the greater min_events wins, ties broken by network id, loser re-bootstraps. Matches remote_dominates in gossip.rs and rumors' "Bootstrapping without consensus" docs.
• Session semantics: strictly-later start supersedes, concurrent starts annihilate both, stale starts are absorbed. Matches state.rs.
• Hash chain: the next job ID is derived from the predecessor's signed bytes, and the chain gates execution. Matches Session::next_job_id.
• Dual M.2 persistence "already implemented": true on the locker branch. The Locker writes every slot, adopts only on agreement or a single-process torn write, restores from a lone survivor, and otherwise discards, which makes the boundary untrusted and refuses all jobs. That is exactly the policy the issue describes. It is not on main.
• "Observe-then-send is domination": rumors documents that every message observed before a batch commits is in the causal past of that batch's sends. The actuation step depends on this and it holds. Note that send does not return the version. The sled has to recognize its own error event when it comes back through the causal stream.

Accuracy nits, none of which affect the argument:

• min_ticks is not "the tallest causally ordered chain". Rumors defines it as the minimum number of ticks that could have produced the version, a floor over all histories. Two concurrent peaks count as 2.
• "There will be zero messages" at bootstrap is false. Every sled sends a version announce into its seed universe immediately, so every seed starts at one event. The convergence argument still holds because a merged universe has more than one.
• The 50 GB growth estimate for the per-network map is off by orders of magnitude. The file is per sled, so the factor of 32 does not apply. More importantly, a lone sled reboot rejoins the existing universe, since its fresh seed loses on min_ticks, so it adds no entry. Entries grow only per universe change that then hosts an executed job: rack-wide cold boots and split-brain incidents. That is dozens to hundreds over a sled's life, not millions. This weakens the case against the map (see below).
• The session case analysis omits the base case, "B equals A because it is the same session", which is the common one and resolves to chain-positional resume.

The motivation is sound: the current design has a real replay hole

The issue calls the locker branch approach "Claude's earlier suggestion" and gives two critiques. I verified both. Critique 1 is a code reading: enqueue_job marks any job at or below the join frontier as replayed, and execute_ready_jobs never runs replayed jobs, so jobs queued before a reboot are lost after it. Critique 2 I confirmed by construction against the branch code:

1. Universe N is partitioned into P1 (session S1) and P2 (session S2, concurrent).
2. Sled X in P1 runs J1. Boundary is (N, S1, J1, F1).
3. X reboots into P2. Not covered, so lost_session is S1. X runs a live job J2 of S2. Boundary is now (N, S2, J2, F2).
4. X reboots into P1 through a lagging peer Q whose frontier is in J1's causal past. lost_session is S2, which is irrelevant in P1. J1 arrives, is_live(J1) is true because J1 dominates Q's frontier, and X executes J1 again.

covered_by only protects the recorded session, so a flip-flop plus one lagging peer replays a job from the other session. The proposed design closes this: in step 4 the stored session version for S2 is concurrent with S1, so the sled parks. And the chain-positional last_executed is immune to peer staleness in the non-flip-flop case.

Findings on the proposal

Ordered by severity.

1. The Bloom filter must be inserted into on every boundary network change, in both branches. The prose only inserts the old network in the no-hit branch. If the hit branch omits it, this replays: boundary A. Move to B (miss): Bloom gets A, run J2, boundary B. Move to A (hit): lightcone, run J3, boundary A, Bloom still only {A}. Move to B: mismatch, Bloom(B) misses, B is treated as fresh, and J2 runs again. The rule should be stated as "whenever the boundary's network field is overwritten, the old value goes into the filter first".

2. The no-hit branch relies on session IDs being universe-unique, and the doc should say so. "Never been in this network, so I have run nothing here" is only true if the same signed job cannot exist in two universes. On the locker branch it holds because SessionId::compute binds the ID to the accepting sled's baseboard and a nonce rotated at activation, and jobs are bound to their session. On main, session IDs are client-random and the client can start a session with a caller-supplied ID, so a client re-issuing the same session into the other side of a split would defeat the filter. This is a load-bearing invariant, not an incidental one. Small hardening: rotate the sush nonce at manager acceptance rather than at state-machine activation, closing the window where a universe migration between the two leaves the nonce reusable.

3. Keep outcome and frontier-independent adjudication. The proposed Boundary drops the outcome field. The recorded ending is what lets the next life report a truthful terminal status instead of guessing "interrupted", and it is orthogonal to the redesign.

4. Store the successor job ID in the boundary. The next ID is the hash of the predecessor's signed bytes, not of its ID. After a lost suffix (I ran J1, nobody else ever saw it), a sled holding only J1's ID cannot verify J2 until J1 is resubmitted. At commit time the sled has J1's bytes, so it can store next_job_id() alongside last_executed and resume without it.

5. Lightcone gates only the first execution after re-entry. Once the sled executes a job K with version greater than E and writes the boundary, chain position takes over: any chain-successor of K could not have run in a previous life because K did not exist then. Stating this bounds the "skip forward" damage to the jobs already queued at re-entry and makes the actuation easier to reason about.

6. Parking needs an operator-visible status. The issue asks for logged errors on skipped jobs during actuation. A sled parked on a concurrent or superseded session should also gossip why, or the operator sees a sled silently ignoring its queue.

My take on the design

The core move is right. Replacing a causal-coverage test with a chain-positional boundary makes "which jobs did I run" exact and independent of who you rejoin through, and that is the property the current design lacks. The Bloom filter is the right primitive for "have I ever left this universe" because it never forgets and its only failure mode, false positives and eventual saturation, degrades into the safe lightcone behavior. Fail-closed by construction.

Two design notes rather than objections:

• Parking on concurrent sessions is a consequence of storing one session, not a safety law. A sled that never rebooted would run the concurrent session's jobs too. The projection to a single (session, job) pair cannot remember two concurrent sessions, so parking is what keeps it safe. That is a fine trade, but the doc frames it as "the only safe disposition" when it is the only safe disposition given this data shape.

• Given the corrected growth rate, consider a capped exact map instead of, or in front of, the Bloom filter. A BTreeMap<Network, Boundary> of a few hundred entries is tens of kilobytes and gives exact resumption on return to a left universe, with no skip-forward at all. Evicted entries go into a Bloom filter, and only those. Lookup: in the map means exact resume, in the filter means lightcone, in neither means fresh universe. It is strictly better behavior for the flip-flop case the issue accepts degrading, and you can list where you have been. The cost is one more structure. If the "outcome I can live with" is genuinely fine, the Bloom-only design is defensible and simpler.

On the closing question of dropping the filter and triggering lightcone on every mismatch: don't. At every healthy rack cold boot each sled's boundary names the previous universe, so the first job addressed to each sled would be skipped, rack-wide. Triggering at join instead of at execution avoids that but skips jobs queued for a slow-booting sled. The filter is what lets a genuinely new universe run its queue.

One incidental finding with a disposition: SessionId::first_job_id is unused on both main and the branch and computes a different hash than next_job_id(&LastJob::None). Dead and inconsistent. Worth deleting in a separate cleanup, not in this work. Relatedly, because a job's ID derives from its predecessor and not its own content, two different signed jobs can share a chain position and an ID. The at-most-once guarantee is per chain position. That is fine for this design, but it deserves its own issue since it also shapes the duplicate-detection logic.

[plaidfinch]

I also asked:

It occurs to me that we could also use the same lightcone fallback approach (potentially?) when we flip-flip between sessions, allowing us to not get stuck in a concurrent session unable to take jobs. What would the pros/cons be for that?

TL;DR: Yes, and better than parking, but not with a single stored session version: a three-session flip-flop replays. Store the join of all executed sessions' start versions instead; then "same session → resume, strictly above the join → run the queue, otherwise → lightcone" is safe and never leaves the operator stuck on their side of a partition. Cost: chain skips on every session flip-flop, not just universe ones.

More details:

Details

Yes, and I'd take it over parking, but the boundary has to change shape first.

Why the naive version is unsafe. "Strictly later than my last session means I was never there" only holds while session moves are monotone. A hop to a concurrent session breaks that, and three sessions replay:

1. In C. Reboot into D (concurrent with C). Lightcone hop, boundary now D.
2. Reboot into A, concurrent with D but causally before C. Lightcone hop, boundary now A.
3. Meet C again. C is strictly later than A, so "fresh session, run the queue". C's jobs run twice.

The fix. Store V, the join of the start versions of every session you have executed under, instead of the last one. Three rules:

• Same session: resume by chain position.
• Start strictly above V: never been there, run the queue.
• Anything else: lightcone hop.

Being in S folds vS into V before S's first job runs, so a start above V is a session you were never in. In the example, vC is below V at step 3 and gets the lightcone. The locker branch already persists a Version in the boundary, so nothing new in storage.

Pros

• Never stuck, and the operator can act locally. Under parking, any session the operator starts on their side is concurrent with the stored one and parks too. Only healing the partition unparks. Under lightcone, anything submitted after the sled arrives runs.
• One mechanism, not two. Same actuation as the universe case.
• Two tests replace the case analysis. Equal session, or strictly above V.
• Nothing lost versus parking. Parking runs none of B's jobs. Lightcone runs the ones submitted after arrival and skips the older ones. Both lose the older ones, and both sessions die when the partition heals.

Cons

• Chain skips become more common. The issue accepts skip-forward as a rare universe-level outcome. Now it happens on every session flip-flop. Each skipped job needs a gossiped error.
• You run jobs in sessions you know are superseded. V cannot distinguish "I was in B" from "B is before a session I was in". Recovering that needs the last start version stored alongside V. Not worth it: every non-rebooted sled in that partition runs B's jobs too.
• More error events in gossip. Small.
• One more sentence in the operator model. "A sled that moves between partitions runs only jobs submitted after it arrived."

Recommendation. Take it, with V in the boundary and the three-session example recorded as the reason the single-version variant is rejected. Parking's virtue was conservatism, bought by leaving the operator no move on their own side of the partition.

[plaidfinch]

And 3 improvements, quoth Claude, which I think are worth keeping un-hidden:

---

1. Define the empty boundary: mint a marker at join. The proposal never says what "no boundary file" means, and every natural reading runs the queue from the chain start. That replays after the design's own recovery path: a sled that ran jobs, hit a disagreeing M.2 pair, and was wiped is indistinguishable from a brand-new one. Fix: with an empty boundary, mint the marker message when joining a universe (re-minting on each bootstrap migration) and run only jobs strictly above it until the first execution writes the boundary. It must be eager. Minting at first execution skips that job, and on a brand-new rack that skips every sled's first job. Cost: a replacement sled joining mid-session skips its pre-queued jobs. Gain: "no usable boundary here", whether empty or Bloom hit, is one rule.

2. Persist the marker. In memory, a crash before the first post-marker execution re-mints it, and everything submitted in between is now below the line. Under a crash loop the sled never catches a job. Storing the marker beside the network and reusing it on restart is safe: jobs above it were created after it, any the previous life started is refused by chain position, and the rest are fine to run. It also removes the proposal's awkward interim state where the record still names the previous network and every arriving job re-triggers the Bloom check. The record becomes "entered N at E, executed nothing yet", with the chain fields filled in at first execution.

3. Skips are terminal statuses, not log lines. Clients consume per-sled job statuses, not gossip logs. A skipped job otherwise sits Queued forever on that sled, hangs any client waiting on it, and leaves no history. Each skip should gossip a terminal status from the skipping baseboard with its reason: parked, lightcone, or already executed (the resubmitted-predecessor case). That settles waits, lands in every sled's history, and gives the operator the resubmit decision the design defers to them.

[plaidfinch]

Plus, we should store all the state in one file, so it doesn't get torn.

[plaidfinch]

And, there's a really interesting interaction between your existing zombie-detection code and the marker mechanism I worked out for solving the skip-forward problem. Claude explains:

---

This one is about the code, not the proposal, but it interacts with item 2.

What the code does. A Start event on our own baseboard whose version is not above the join frontier is a zombie candidate: a previous life started it and no executor of ours will ever stop it. Once replay drains, surviving candidates are gossiped as Interrupted. The join frontier is the lagging-or-not peer's frontier at the moment we joined through it.

The failure. A previous-life Start can sit above a lagging peer's frontier, because its creator (us, last life) had seen more than that peer has. It then classifies as this life's start, is never a candidate, and the rack believes the job runs forever on this sled. That is the original sush#9 symptom, surviving in the case the fix was meant to cover. The reverse error cannot happen: this-life starts are minted after join, so they are always above any join frontier.

The fix. Replace the join frontier with a marker we mint ourselves at startup, and classify by "above it or not". Our own previous-life events were created before it in real time, so they are never above it. Our own this-life events observe it before they are sent, so they are always above it. For own-baseboard events the classification is exact and peer-independent. Every other use of is_live in the code, suppressing re-gossip of replayed errors, refusing jobs for inactive sessions, is the same "before me or after me" question and gets the same answer.

The interaction with item 2. The persisted entry marker cannot serve this purpose. If life 1 mints it, starts J, and crashes, life 2 reuses the marker and J's Start is above it, so J is missed as a zombie. Two markers, then, with different lifetimes: the entry marker, persisted and universe-scoped, is the execution threshold and is reused across restarts; the birth marker, minted every startup and never persisted, is the life boundary for zombie detection. The proposal's actuation marker is the first kind. Zombies need the second. Conflating them trades a liveness bug for a reporting bug.

[plaidfinch]

A final note: I don't talk about outcomes here, but we should still preserve them per the existing code.

[plaidfinch]

And we should probably have a way to query a sled's boundary record in sush client.