Environment: Node 20 (verified on Node v22; APIs are Node 20-compatible), zero dependencies.
All 14 tests pass and the counterexample demo works. The solution is written to ~/http2-flow/SOLUTION.md (with runnable code in lib/flow-control.js, harness.js, test.js, demo-counterexample.js). Full markdown:
Environment: Node 20 (verified on Node v22; APIs are Node 20-compatible), zero dependencies. Deliverable: a minimal RFC 7540 flow-control accountant + forward-progress DATA scheduler, plus a deterministic replay harness that emits a counterexample naming the exact frame index.
lib/flow-control.js # FlowController + Scheduler + FlowControlError
harness.js # deterministic trace replay + invariant oracle
test.js # 14 node:test cases
demo-counterexample.js # live counterexample output
index.js # public entry point
SOLUTION.md
Run:
cd ~/http2-flow
node --test test.js # 14 passing
node demo-counterexample.js
A strictly-priority writer that always serves the highest-weight stream with pending data picks stream 1 (weight 100). If stream 1's per-stream window is 0, available() returns 0 and the naive loop breaks out entirely. Streams 2 and 3 still have window and pending bytes, but are never reached. Throughput drops to zero despite available capacity:
stream 1 (w=100, window=0) -> selected -> no window -> STOP
stream 2 (w=1, window=1000, pending) -> never served
stream 3 (w=1, window=1000, pending) -> never served
Correct property: eligibility-aware scheduling. Selection must consider only streams sendable right now (window > 0, pending > 0, connection window > 0); a blocked stream is skipped, not a reason to stop. Weight orders the eligible set, it does not gate it. Equal weights must degrade to flat round-robin.
The harness oracle caught a real bug in the first draft:
WINDOW_UPDATE used target.window, but the connection window lives in connectionWindow. For streamId === 0, target = this, so this.window was undefined; undefined + increment = NaN, the overflow check silently passed, and the increment was written to a phantom field while the real connection window never grew. Fixed by branching on isConnection and using connectionWindow.Other enforced invariants:
| Concern | Correct behaviour |
|---|---|
SETTINGS_INITIAL_WINDOW_SIZE |
Applied retroactively as a delta to all open streams; may legally drive a window negative; never a flow-control error. |
WINDOW_UPDATE overflow |
window + increment > 2^31-1 → FLOW_CONTROL_ERROR (GOAWAY). Increment 0 tolerated as no-op (strict mode available). |
| Frame coalescing | Each DATA frame length ≤ min(remaining connection window, remaining stream window, max frame size). |
| Consumption | Debit never drives either window below zero; guard before mutate. |
lib/flow-control.js)The critical fix — a connection/stream branch instead of treating this as a stream:
onWindowUpdate(streamId, increment) {
if (!Number.isInteger(increment) || increment < 0 || increment > MAX_WINDOW) {
throw new FlowControlError(`invalid WINDOW_UPDATE increment ${increment}`);
}
if (increment === 0) {
if (this.rejectZeroIncrement) throw new FlowControlError('WINDOW_UPDATE with increment 0');
return false; // tolerant no-op
}
let target;
let isConnection = false;
if (streamId === 0) {
isConnection = true;
target = this;
} else {
target = this.streams.get(streamId);
if (!target) throw new FlowControlError(`WINDOW_UPDATE for unknown stream ${streamId}`);
}
const current = isConnection ? this.connectionWindow : target.window; // <-- the fix
if (current + increment > MAX_WINDOW) {
throw new FlowControlError(
`window overflow on ${isConnection ? 'connection' : `stream ${streamId}`}: ` +
`${current} + ${increment} > ${MAX_WINDOW}`
);
}
if (isConnection) this.connectionWindow += increment;
else target.window += increment;
return true;
}
Retroactive SETTINGS delta (negative windows allowed):
onSettingsInitialWindowSize(newSize) {
if (!Number.isInteger(newSize) || newSize < 0 || newSize > MAX_WINDOW) {
throw new FlowControlError(`invalid SETTINGS_INITIAL_WINDOW_SIZE ${newSize}`);
}
const delta = newSize - this.initialWindowSize;
this.initialWindowSize = newSize;
for (const s of this.streams.values()) s.window += delta; // may go negative; legal
return delta;
}
Guarded debit + clamped availability:
available(streamId) {
const s = this.streams.get(streamId);
if (!s || s.closed) return 0;
return Math.max(0, Math.min(this.connectionWindow, s.window));
}
consume(streamId, bytes) {
const s = this.streams.get(streamId);
if (!s) throw new FlowControlError(`consume for unknown stream ${streamId}`);
if (bytes > this.connectionWindow) throw new FlowControlError('connection flow-control window exceeded');
if (bytes > s.window) throw new FlowControlError(`stream ${streamId} flow-control window exceeded`);
this.connectionWindow -= bytes;
s.window -= bytes;
s.bytesEmitted += bytes;
return bytes;
}
The key line is if (available <= 0) break; inside the per-stream inner loop: it breaks that stream's turn, not the whole pump. The outer fairness round keeps visiting remaining streams. The outer while (progress) repeats only when a frame was emitted — the forward-progress guarantee and a termination proof (windows only shrink during a pump).
pump(opts = {}) {
const maxFrames = opts.maxFrames ?? Infinity;
const frames = [];
let progress = true;
while (progress && frames.length < maxFrames) {
progress = false;
for (const s of this.fc.streams.values()) { // one fairness round
if (s.closed) continue;
let budget = s.weight * this.quantum; // weight controls share per round
while (budget > 0 && s.pending > 0) {
const available = this.fc.available(s.id);
if (available <= 0) break; // skip blocked stream, don't stall
const length = Math.min(budget, s.pending, available, this.maxFrameSize);
if (length <= 0) break;
this.fc.consume(s.id, length); // guarded debit
s.pending -= length;
s.framesEmitted += 1;
budget -= length;
frames.push({ streamId: s.id, length, connWindow: this.fc.connectionWindow, streamWindow: s.window });
progress = true;
if (frames.length >= maxFrames) return frames;
}
}
}
return frames;
}
Properties: forward progress; no starvation; flat-RR fallback (1,2,3,1,2,3…); coalescing; deterministic (insertion-ordered Map, no randomness).
harness.js drives a scripted trace and asserts invariants after every event and every frame, using an independent oracle (granted - emitted) rather than trusting the controller.
Events: open, close, settings, window_update, data, pump.
Invariants:
0 < length ≤ maxFrameSize.=== granted - emitted.=== granted - emitted (settings deltas included).2^31-1.On violation it throws a CounterexampleError with kind, event index, and the exact frame index:
[counterexample] connection-window-exceeded at event event[1]: emitted 1000 > connection granted 100
event index : 1
frame index : 0
offending : {"emitted":1000}
expected : {"granted":100}
window snap : {"connection":-900,...,"emitted":1000}
Usage:
const { Harness } = require('./harness');
const h = new Harness({ initialWindowSize: 1000, connectionWindow: 1 << 20 });
h.run([
{ type: 'open', streamId: 1, weight: 100 }, // high weight, will be blocked
{ type: 'open', streamId: 3, weight: 1 },
{ type: 'open', streamId: 5, weight: 1 },
{ type: 'data', streamId: 1, bytes: 5000 },
{ type: 'data', streamId: 3, bytes: 5000 },
{ type: 'data', streamId: 5, bytes: 5000 },
{ type: 'pump' },
]);
console.log(h.bytesByStream()); // { '1': 1000, '3': 1000, '5': 1000 }
test.js implements NaiveStrictPriorityScheduler — the exact bug being guarded against — and asserts it makes zero progress on the same scripted state while the real scheduler emits on all streams, so tests cannot regress to a strict-priority deadlock.
$ cd ~/http2-flow
$ node --test test.js
# tests 14
# pass 14
# fail 0
# duration_ms 69.2
| # | Test | Proves |
|---|---|---|
| 1 | SETTINGS retroactive, negative windows | delta applied to open streams; -4900 accepted; no send while negative |
| 2 | SETTINGS growth re-opens blocked stream | window grows from 0, pending flushes |
| 3 | WINDOW_UPDATE increment 0 | tolerant no-op (stream and connection) |
| 4 | WINDOW_UPDATE overflow | stream and connection overflow → FLOW_CONTROL_ERROR/GOAWAY; exact ceiling accepted |
| 5 | Frame coalescing | every frame ≤ 4096; totals match windows |
| 6 | Forward progress | blocked w=100 stream does not starve w=1 streams; naive emits 0 |
| 7 | Flat round-robin | equal streams emit 1,2,3,1,2,3,1,2,3 |
| 8 | Weighted 2:1 | 8 frames vs 4 in a 12-frame window |
| 9 | Connection bottleneck | shared window caps aggregate output exactly |
| 10 | Counterexample machinery | corrupted accountant yields CounterexampleError with valid frame index |
| 11 | Determinism | same trace ⇒ byte-identical frames |
| 12 | Fuzz (300 random traces) | no invariant violation; pump never stops with sendable data |
| 13 | SETTINGS bounds | 2^31 and -1 rejected |
| 14 | Wake after WINDOW_UPDATE | blocked stream resumes and drains fully |
Counterexample command output:
$ node demo-counterexample.js
correct scheduler bytes by stream: { '1': 1000, '3': 1000, '5': 1000 }
correct scheduler frames by stream: { '1': 1, '3': 1, '5': 1 }
--- counterexample trace ---
[counterexample] connection-window-exceeded at event event[1]: emitted 1000 > connection granted 100
event index : 1
frame index : 0
offending : {"emitted":1000}
expected : {"granted":100}
window snap : {"connection":-900,"initialWindowSize":65535,"streams":{"1":{"window":64535,"pending":0,"emitted":1000}}}
WINDOW_UPDATE increment 0. RFC 7540 §6.9 calls it PROTOCOL_ERROR. The task wording ("handle increments including 0") is satisfied by a tolerant no-op by default (onWindowUpdate returns false); pass { rejectZeroIncrement: true } for strict behaviour.SETTINGS_INITIAL_WINDOW_SIZE; the scheduler skips the stream until it recovers.SETTINGS_INITIAL_WINDOW_SIZE, only by WINDOW_UPDATE(0, …) and consumption.WINDOW_UPDATE is processed mid-pump, so windows are monotonically non-increasing; each emitted frame strictly decreases the finite remaining window, so the loop terminates.const { FlowController, Scheduler } = require('./lib/flow-control');
const fc = new FlowController({ initialWindowSize: 65535, maxFrameSize: 16384 });
const sched = new Scheduler(fc);
fc.openStream(1, 100);
fc.openStream(3, 1);
fc.openStream(5, 1);
sched.enqueue(1, 100_000);
sched.enqueue(3, 100_000);
sched.enqueue(5, 100_000);
const frames = sched.pump(); // coalesced DATA frames, may be capped by maxFrames
fc.onWindowUpdate(3, 65535); // dynamic top-up
fc.onSettingsInitialWindowSize(32768); // retroactive, may make windows negative
# Evidence - Problem class: js-http2-per-stream-flow-control-starvation-guard - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-12T16:25:59.136Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a minimal HTTP/2 (RFC 7540) flow-control accountant and write scheduler in Node 20 with no dependencies: track the connection-level window and each stream's per-stream window, apply SETTINGS_INITIAL_WINDOW_SIZE changes retroactively to already-open streams, handle WINDOW_UPDATE increments including 0 and overflow past 2^31-1 (which must surface as FLOW_CONTROL_ERROR / GOAWAY), and coalesce DATA frames so no frame exceeds the peer's advertised max frame size or the stream's remaining window. The scheduler must guarantee forward progress: a high-weight stream whose window is exhausted must not block lower-weight streams that still have window, and a flat round-robin fallback must keep throughput non-zero when all weights are equal, so a naive strictly-priority queue that deadlocks on stream 1 with 0 window and 2 unread streams must fail your tests. Ship a deterministic harness that replays a scripted event trace of SETTINGS/WINDOW_UPDATE/DATA/blocked-frames and asserts per-stream bytes emitted, that cumulative emitted bytes never exceed any window at any instant, and that the run terminates with a counterexample trace naming the exact frame index where an invariant broke.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-http2-per-stream-flow-control-starvation-guard", "provider": "openrouter", "solved_at": "2026-09-12T16:25:59.136Z", "version": "20"}All 14 tests pass and the counterexample demo works. The solution is written to ~/http2-flow/SOLUTION.md (with runnable code in lib/flow-control.js, harness.js, test.js, demo-counterexample.js). Full markdown:
Environment: Node 20 (verified on Node v22; APIs are Node 20-compatible), zero dependencies. Deliverable: a minimal RFC 7540 flow-control accountant + forward-progress DATA scheduler, plus a deterministic replay harness that emits a counterexample naming the exact frame index.
lib/flow-control.js # FlowController + Scheduler + FlowControlError
harness.js # deterministic trace replay + invariant oracle
test.js # 14 node:test cases
demo-counterexample.js # live counterexample output
index.js # public entry point
SOLUTION.md
Run:
cd ~/http2-flow
node --test test.js # 14 passing
node demo-counterexample.js
A strictly-priority writer that always serves the highest-weight stream with pending data picks stream 1 (weight 100). If stream 1's per-stream window is 0, available() returns 0 and the naive loop breaks out entirely. Streams 2 and 3 still have window and pending bytes, but are never reached. Throughput drops to zero despite available capacity:
stream 1 (w=100, window=0) -> selected -> no window -> STOP
stream 2 (w=1, window=1000, pending) -> never served
stream 3 (w=1, window=1000, pending) -> never served
Correct property: eligibility-aware scheduling. Selection must consider only streams sendable right now (window > 0, pending > 0, connection window > 0); a blocked stream is skipped, not a reason to stop. Weight orders the eligible set, it does not gate it. Equal weights must degrade to flat round-robin.
The harness oracle caught a real bug in the first draft:
WINDOW_UPDATE used target.window, but the connection window lives in connectionWindow. For streamId === 0, target = this, so this.window was undefined; undefined + increment = NaN, the overflow check silently passed, and the increment was written to a phantom field while the real connection window never grew. Fixed by branching on isConnection and using connectionWindow.Other enforced invariants:
| Concern | Correct behaviour |
|---|---|
SETTINGS_INITIAL_WINDOW_SIZE |
Applied retroactively as a delta to all open streams; may legally drive a window negative; never a flow-control error. |
WINDOW_UPDATE overflow |
window + increment > 2^31-1 → FLOW_CONTROL_ERROR (GOAWAY). Increment 0 tolerated as no-op (strict mode available). |
| Frame coalescing | Each DATA frame length ≤ min(remaining connection window, remaining stream window, max frame size). |
| Consumption | Debit never drives either window below zero; guard before mutate. |
lib/flow-control.js)The critical fix — a connection/stream branch instead of treating this as a stream:
onWindowUpdate(streamId, increment) {
if (!Number.isInteger(increment) || increment < 0 || increment > MAX_WINDOW) {
throw new FlowControlError(`invalid WINDOW_UPDATE increment ${increment}`);
}
if (increment === 0) {
if (this.rejectZeroIncrement) throw new FlowControlError('WINDOW_UPDATE with increment 0');
return false; // tolerant no-op
}
let target;
let isConnection = false;
if (streamId === 0) {
isConnection = true;
target = this;
} else {
target = this.streams.get(streamId);
if (!target) throw new FlowControlError(`WINDOW_UPDATE for unknown stream ${streamId}`);
}
const current = isConnection ? this.connectionWindow : target.window; // <-- the fix
if (current + increment > MAX_WINDOW) {
throw new FlowControlError(
`window overflow on ${isConnection ? 'connection' : `stream ${streamId}`}: ` +
`${current} + ${increment} > ${MAX_WINDOW}`
);
}
if (isConnection) this.connectionWindow += increment;
else target.window += increment;
return true;
}
Retroactive SETTINGS delta (negative windows allowed):
onSettingsInitialWindowSize(newSize) {
if (!Number.isInteger(newSize) || newSize < 0 || newSize > MAX_WINDOW) {
throw new FlowControlError(`invalid SETTINGS_INITIAL_WINDOW_SIZE ${newSize}`);
}
const delta = newSize - this.initialWindowSize;
this.initialWindowSize = newSize;
for (const s of this.streams.values()) s.window += delta; // may go negative; legal
return delta;
}
Guarded debit + clamped availability:
available(streamId) {
const s = this.streams.get(streamId);
if (!s || s.closed) return 0;
return Math.max(0, Math.min(this.connectionWindow, s.window));
}
consume(streamId, bytes) {
const s = this.streams.get(streamId);
if (!s) throw new FlowControlError(`consume for unknown stream ${streamId}`);
if (bytes > this.connectionWindow) throw new FlowControlError('connection flow-control window exceeded');
if (bytes > s.window) throw new FlowControlError(`stream ${streamId} flow-control window exceeded`);
this.connectionWindow -= bytes;
s.window -= bytes;
s.bytesEmitted += bytes;
return bytes;
}
The key line is if (available <= 0) break; inside the per-stream inner loop: it breaks that stream's turn, not the whole pump. The outer fairness round keeps visiting remaining streams. The outer while (progress) repeats only when a frame was emitted — the forward-progress guarantee and a termination proof (windows only shrink during a pump).
pump(opts = {}) {
const maxFrames = opts.maxFrames ?? Infinity;
const frames = [];
let progress = true;
while (progress && frames.length < maxFrames) {
progress = false;
for (const s of this.fc.streams.values()) { // one fairness round
if (s.closed) continue;
let budget = s.weight * this.quantum; // weight controls share per round
while (budget > 0 && s.pending > 0) {
const available = this.fc.available(s.id);
if (available <= 0) break; // skip blocked stream, don't stall
const length = Math.min(budget, s.pending, available, this.maxFrameSize);
if (length <= 0) break;
this.fc.consume(s.id, length); // guarded debit
s.pending -= length;
s.framesEmitted += 1;
budget -= length;
frames.push({ streamId: s.id, length, connWindow: this.fc.connectionWindow, streamWindow: s.window });
progress = true;
if (frames.length >= maxFrames) return frames;
}
}
}
return frames;
}
Properties: forward progress; no starvation; flat-RR fallback (1,2,3,1,2,3…); coalescing; deterministic (insertion-ordered Map, no randomness).
harness.js drives a scripted trace and asserts invariants after every event and every frame, using an independent oracle (granted - emitted) rather than trusting the controller.
Events: open, close, settings, window_update, data, pump.
Invariants:
0 < length ≤ maxFrameSize.=== granted - emitted.=== granted - emitted (settings deltas included).2^31-1.On violation it throws a CounterexampleError with kind, event index, and the exact frame index:
[counterexample] connection-window-exceeded at event event[1]: emitted 1000 > connection granted 100
event index : 1
frame index : 0
offending : {"emitted":1000}
expected : {"granted":100}
window snap : {"connection":-900,...,"emitted":1000}
Usage:
const { Harness } = require('./harness');
const h = new Harness({ initialWindowSize: 1000, connectionWindow: 1 << 20 });
h.run([
{ type: 'open', streamId: 1, weight: 100 }, // high weight, will be blocked
{ type: 'open', streamId: 3, weight: 1 },
{ type: 'open', streamId: 5, weight: 1 },
{ type: 'data', streamId: 1, bytes: 5000 },
{ type: 'data', streamId: 3, bytes: 5000 },
{ type: 'data', streamId: 5, bytes: 5000 },
{ type: 'pump' },
]);
console.log(h.bytesByStream()); // { '1': 1000, '3': 1000, '5': 1000 }
test.js implements NaiveStrictPriorityScheduler — the exact bug being guarded against — and asserts it makes zero progress on the same scripted state while the real scheduler emits on all streams, so tests cannot regress to a strict-priority deadlock.
$ cd ~/http2-flow
$ node --test test.js
# tests 14
# pass 14
# fail 0
# duration_ms 69.2
| # | Test | Proves |
|---|---|---|
| 1 | SETTINGS retroactive, negative windows | delta applied to open streams; -4900 accepted; no send while negative |
| 2 | SETTINGS growth re-opens blocked stream | window grows from 0, pending flushes |
| 3 | WINDOW_UPDATE increment 0 | tolerant no-op (stream and connection) |
| 4 | WINDOW_UPDATE overflow | stream and connection overflow → FLOW_CONTROL_ERROR/GOAWAY; exact ceiling accepted |
| 5 | Frame coalescing | every frame ≤ 4096; totals match windows |
| 6 | Forward progress | blocked w=100 stream does not starve w=1 streams; naive emits 0 |
| 7 | Flat round-robin | equal streams emit 1,2,3,1,2,3,1,2,3 |
| 8 | Weighted 2:1 | 8 frames vs 4 in a 12-frame window |
| 9 | Connection bottleneck | shared window caps aggregate output exactly |
| 10 | Counterexample machinery | corrupted accountant yields CounterexampleError with valid frame index |
| 11 | Determinism | same trace ⇒ byte-identical frames |
| 12 | Fuzz (300 random traces) | no invariant violation; pump never stops with sendable data |
| 13 | SETTINGS bounds | 2^31 and -1 rejected |
| 14 | Wake after WINDOW_UPDATE | blocked stream resumes and drains fully |
Counterexample command output:
$ node demo-counterexample.js
correct scheduler bytes by stream: { '1': 1000, '3': 1000, '5': 1000 }
correct scheduler frames by stream: { '1': 1, '3': 1, '5': 1 }
--- counterexample trace ---
[counterexample] connection-window-exceeded at event event[1]: emitted 1000 > connection granted 100
event index : 1
frame index : 0
offending : {"emitted":1000}
expected : {"granted":100}
window snap : {"connection":-900,"initialWindowSize":65535,"streams":{"1":{"window":64535,"pending":0,"emitted":1000}}}
WINDOW_UPDATE increment 0. RFC 7540 §6.9 calls it PROTOCOL_ERROR. The task wording ("handle increments including 0") is satisfied by a tolerant no-op by default (onWindowUpdate returns false); pass { rejectZeroIncrement: true } for strict behaviour.SETTINGS_INITIAL_WINDOW_SIZE; the scheduler skips the stream until it recovers.SETTINGS_INITIAL_WINDOW_SIZE, only by WINDOW_UPDATE(0, …) and consumption.WINDOW_UPDATE is processed mid-pump, so windows are monotonically non-increasing; each emitted frame strictly decreases the finite remaining window, so the loop terminates.const { FlowController, Scheduler } = require('./lib/flow-control');
const fc = new FlowController({ initialWindowSize: 65535, maxFrameSize: 16384 });
const sched = new Scheduler(fc);
fc.openStream(1, 100);
fc.openStream(3, 1);
fc.openStream(5, 1);
sched.enqueue(1, 100_000);
sched.enqueue(3, 100_000);
sched.enqueue(5, 100_000);
const frames = sched.pump(); // coalesced DATA frames, may be capped by maxFrames
fc.onWindowUpdate(3, 65535); // dynamic top-up
fc.onSettingsInitialWindowSize(32768); // retroactive, may make windows negative
# Evidence - Problem class: js-http2-per-stream-flow-control-starvation-guard - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-12T16:25:59.136Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a minimal HTTP/2 (RFC 7540) flow-control accountant and write scheduler in Node 20 with no dependencies: track the connection-level window and each stream's per-stream window, apply SETTINGS_INITIAL_WINDOW_SIZE changes retroactively to already-open streams, handle WINDOW_UPDATE increments including 0 and overflow past 2^31-1 (which must surface as FLOW_CONTROL_ERROR / GOAWAY), and coalesce DATA frames so no frame exceeds the peer's advertised max frame size or the stream's remaining window. The scheduler must guarantee forward progress: a high-weight stream whose window is exhausted must not block lower-weight streams that still have window, and a flat round-robin fallback must keep throughput non-zero when all weights are equal, so a naive strictly-priority queue that deadlocks on stream 1 with 0 window and 2 unread streams must fail your tests. Ship a deterministic harness that replays a scripted event trace of SETTINGS/WINDOW_UPDATE/DATA/blocked-frames and asserts per-stream bytes emitted, that cumulative emitted bytes never exceed any window at any instant, and that the run terminates with a counterexample trace naming the exact frame index where an invariant broke.", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-http2-per-stream-flow-control-starvation-guard", "provider": "openrouter", "solved_at": "2026-09-12T16:25:59.136Z", "version": "20"}