Patents

Family Two: Durable work, tombstones and lossless recovery

No accepted work is lost, and no completed result is delivered twice, across a durable broker and GPU runtimes.

Durable-log brokerGPU inference runtimesPatent pending
Every piece of work · in exactly one state
Dstorage
Mmemory
Qqueued
Gon GPU
Ocomplete
Together, all accepted work; white caps are tombstones
End-to-end recovery

From a failed machine to nothing lost and nothing done twice

1A machine fails
A
B
C

Consumer C stops; its items are of unknown standing.

2Reconcile state
A
B
C

Tombstones read, survivor reports gathered, every item classified.

3Leave survivor work alone
A
B
C

Resident and in-flight work stays where it is; tombstoned work is suppressed.

4Redispatch only eligible work
A
B
C

The redispatch set goes back through durable storage to the survivors.

  • 5states; every piece of work is in exactly one
  • 1durable tombstone marks a completion
  • 4outcomes for every item at reconciliation
  • 6 Mqueued items in the loss this design closed

Methods and Systems for No-Loss Work Reconciliation Between a Durable-Log Broker and Accelerator Inference Runtimes Using Consumer-Reported Hardware Residency. U.S. Provisional Patent Application No. 64/147,527 (patent pending). Embodied in the broker of the Inference Fabric.

Five states, every piece of work in exactly one

Every piece of work is in exactly one of five states at any time: durable storage, consumer memory, queued for GPU, running on GPU, or durably complete. At any instant all accepted work is the disjoint union of those five sets, so nothing is ever unaccounted for.

All accepted work at one instant
storagememoryqueuedon GPUcomplete
every piece of work accepted so far
The two bars are the same length, with no gaps and no overlaps. Region widths are illustrative.

A tombstone, and a fixed durability order

Completion is marked by a durable tombstone, and the durability order is fixed: the output is persisted, then the tombstone, and only then is the input retired.

One piece of work · in this order, always
1 · persist the output2 · persist the tombstone3 · retire the input
crash between 1 and 2: the output exists, no tombstone, the input is still held; the work is unresolved and recovery decides it crash between 2 and 3: the tombstone exists, so the work is complete and is never redispatched
Because retirement comes last, a retired input always means the output and its tombstone already exist.

Recovery as a classification

Recovery is a classification. After a failure the system identifies the work that is accepted but not complete, the work that surviving consumers report as resident in their own memory, and the work whose owner was a failed consumer.

Tombstonedcomplete; suppressed
Accepted, not complete
resident on a surviving consumer suppressed: left where it is owner failed the redispatch set

Surviving consumers report the sequence ids resident in their own memory. The blue region is work whose owner failed minus anything a survivor still holds; only that is sent again. Region sizes are illustrative.

Only work that is unresolved, not tombstoned, not resident on a survivor, and owned by a failed consumer is redispatched. Everything else is suppressed, and each item comes out of reconciliation with exactly one of four outcomes.

Consumer A · survived
Consumer B · survived
Consumer C · failed
Terminal: tombstoned
Survivor-resident: held by a survivor
In flight: owned by a survivor
Redispatch
Durable storage after reconciliation
The redispatch set is added back to durable storage; it never overlaps a tombstone or a survivor's memory. Item counts are illustrative.

At-least-once execution, at-most-once completion

The guarantees fall out of the model: no accepted work is lost, and no completed result is delivered twice.

GPU executions · at least once here twice: once before the failure, once after redispatch
Observable completions · at most once the tombstone stops a second publish

A piece of work may execute more than once on GPUs, and the outside world observes its completion at most once.

That is the design that closed a six-million-item loss and balanced the token ledger to zero, told in Millions of queued items that were not there.