Cross-Service Deadlines and Cancellation Budgets: Propagation, Allocation, and Stable Convergence

A 3-second timeout at the ingress gateway, 3 seconds for service A, and another 3 seconds for service B do not produce a 3-second user experience. Queueing, DNS, connection establishment, retries, and response delivery each restart the clock at another layer, so the operation may ultimately run for more than ten seconds. After the user closes the connection, database queries and third-party requests may still be running. MCP Timeouts, Retries, and Idempotency addresses the effects of an individual tool, while the Multi-Agent Wait Graph addresses persistent task graphs. This article deals only with one end-to-end budget for a synchronous service call tree.

Issue a Budget at Ingress That Cannot Be Increased

Publish service.budget.v1. The edge obtains maxDuration from an authenticated endpoint policy, clamps the client declaration to the permitted range, subtracts time already spent at ingress and the response reserve, and generates an operation ID, budget version, trusted ingress timestamp, absolute deadline for auditing, initial remainingBudgetMs, cancel generation, and priority source. An external caller cannot extend the deadline or raise the priority with a custom header.

Within a process, use a monotonic clock to calculate the remaining time. Across machines, do not directly compare two unreliable wall clocks. Each hop sends "the local remaining duration minus a transport safety margin." The recipient takes the minimum of that value, its own endpoint cap, and the remaining budget in the operation registry, then establishes a local deadline. gRPC deadline propagation converts a deadline into a timeout to deduct elapsed time and mitigate clock skew; other protocols must implement equivalent rules. Any budget with an unknown version, a negative value, a value above the cap, or an origin at an untrusted network boundary must be rejected or handled using the smaller local default.

W3C Trace Context only correlates telemetry; it is not authorization to spend budget. A trace may be sampled, restarted, or forwarded across trust domains, so span timing cannot be used to infer permission to continue executing. Distributed Tracing records the time spent in each phase, while the canonical deadline still comes from the call context and the trusted control plane.

Divide the Budget into Phases Before Allowing Fan-Out and Retries

The versioned contract for each endpoint locks in a minimum response budget, maximum queueing share, downstream reserve, and serialization and flush headroom. Before calling a downstream dependency, calculate:

childBudget = min(parentRemaining - responseReserve,
                  dependencyCap,
                  operationRemaining)

If the result is below the dependency's minimumUsefulBudget, fail fast before sending. Do not send a request that is certain to time out. Parallel fan-out shares the parent budget; completing one child does not "refund" the time it consumed. A sequential chain deducts the actual elapsed time at every hop. A service mesh may enforce connection and per-try timeouts, but its Service Mesh and Istio configuration cannot specify a deadline longer than the application's deadline.

Retries and hedges consume the same retry ledger, which records the maximum number of attempts, elapsed time, concurrent attempts, and latest permitted start time. Exactly one of the SDK, sidecar, and business layer may own retries; otherwise, three retries at each of three layers amplify into 27 attempts. Only operations that can be replayed safely may be retried, and writes must reuse a stable operation/idempotency identity. Stop starting new attempts after reaching the response-reserve boundary, even if unused attempts remain. Circuit breaking in Microservices Patterns handles dependency health, while a deadline determines how much longer the current call may wait. Neither can replace the other.

A Cancellation Signal Does Not Mean the Work Has Actually Stopped

An operation state can be represented as ACCEPTED -> RUNNING -> CANCELLING -> CANCELLED_STABLE | COMPLETED | NEEDS_RECONCILIATION. Before sending, every downstream operation first registers its identity, generation, budget, effect capability, and PREPARED state with the authoritative child registry. It then uses a CAS matching the current cancel generation to enter DISPATCHING; if registration fails, it must not be sent. When the client disconnects, the deadline expires, or the upstream cancels, the control plane atomically closes the child-registration watermark, advances the cancel generation, prevents new children and retries, and propagates cancellation across the registered set. Interfaces such as Go context must still be passed explicitly through the call chain; they cannot be dropped into a goroutine that never checks the signal.

Database drivers, RPCs, and stream processing must check for cancellation at blocking points and release their connections. Each child writes a terminal receipt when it completes, confirms that it has stopped, or is isolated. If a child has crossed the acceptance point for an external side effect but its outcome is unknown, register the effect ID, payload digest, and provider handle, then enter NEEDS_RECONCILIATION. The operation may be marked CANCELLED_STABLE only after the registration watermark has closed, every child in the authoritative set has a terminal or isolation receipt, connections and permits have been released, and an old generation can no longer commit. HTTP 499, 504, or gRPC DEADLINE_EXCEEDED alone cannot prove quiescence.

Treat Budget Exhaustion as an Injectable Failure

Use a virtual clock and controllable transport to inject these conditions: ingress queueing consumes half the budget, DNS stalls, three children include one fast child, one slow child, and one that ignores cancellation, the sidecar retries automatically, sending succeeds but registration fails, the deadline races the dispatch CAS, the cancellation message is lost, a stale retry starts, and a downstream write succeeds but its response is lost. Assert that the number of sends for unregistered children is 0, no child deadline falls after the parent's reserve boundary, the budget never grows across hops or retries, a stale cancel generation cannot create a call, and unknown effects are not treated as zero.

Release gates require zero budget expansion across 1 million randomized call trees, 100% coverage for child preregistration and terminal receipts, zero new downstream acceptances after the deadline, a P99 below 100 milliseconds from cancellation propagation until new I/O stops, zero orphaned connections and permits, and an end-to-end deadline miss rate below 0.1%. Known cancellations and effects awaiting reconciliation must be reported separately. Start in shadow mode, then expand from read-only operations to idempotent writes. If anomalies occur, roll back to the previous rules by budget version, but retain the hard ingress cap, child registry, and reconciliation. Never return to having no deadline.

Further Reading

• Distributed Tracing
• Service Mesh and Istio
• MCP Timeouts, Retries, and Idempotency
• Microservices Patterns