Grace window and skip-queue bounds

Answers the two open questions left in liveness-probe-skip-schedule.md.

1. The grace window is fixed, not earned

If the grace window grew with a guardian's past reachability, a thief could first make a guardian look very reliable, then cut them off and get a longer stall. To stop that:

• The grace window is one fixed length, set when the roster is set. It does not change with history.
• Every grace window counts against the per-pass budget (rule 2). A long window cannot go past that cap, whatever its length.
• History may only make the window shorter, never longer. A guardian who has missed probes before gets the shortest window. Being reliable earns nothing a thief could use.

So the worst stall in one pass stays at one turn limit plus one grace window.

2. The skip queue is bounded by the roster

The queue only holds guardians who are on the roster, and each one can be in it once per pass. So it can never be longer than the roster size minus one. No extra cap is needed for length.

What does need a rule is order when a queued guardian comes back:

• A returning guardian takes the next open turn after the current one ends. They do not interrupt the current turn.
• If several come back at once, they go in roster order, so a thief cannot pick who goes first.
• A queued guardian who still has not answered when the pass ends is carried into the next pass at the front, with a fresh grace window. They keep their turn (rule 1), but they cannot be waited on twice in the same pass.

Worst case, put together

Per pass, a thief who makes k honest guardians unreachable costs at most:

one turn limit (budget, rule 2) + one grace window (fixed)

and not k times anything. An honest guardian who is offline for a while loses no turn; their turn just moves later.

Still open

• Who sets the fixed grace window, and can it be changed without a fresh roster vote?

Who sets the grace window

Open question from grace-window-and-queue-bounds.md: who fixes the grace window, and can it change without a new roster vote?

Answer

• The grace window and the per-pass budget (one turn limit) are part of the roster record. They are signed together with the roster, so changing either one needs the same vote as changing the roster.
• A change takes effect only at the start of the next pass. A pass that is already running keeps the values it started with, so nobody can shrink the window in the middle of a pass to skip a guardian who is offline.
• While the key is frozen, the window can only get longer. Making it shorter is refused until the key is unfrozen. A thief who has coerced some guardians could otherwise vote for a tiny window and turn every honest guardian who is briefly offline into a skip.
• Each guardian keeps a local floor. A probe schedule shorter than the floor counts as an attack signal, so the guardian refuses to sign it, even if the roster vote passed.

Why this closes the loop

Rule 1 depends on the window to protect guardians who are briefly offline. Rule 2 depends on the budget to stop a thief from freezing the key for limit times roster size. If either value could change without a vote, or during a freeze, the thief could undo both rules. Tying the values to the roster, and letting them change only between passes and only upward during a freeze, keeps the bounds the two rules depend on.

Still open

How large should the local floor be? It needs to cover normal network outages, but it can't be so long that it brings back the freeze problem.

Liveness-probe skip schedule

How rules 1 and 2 fit together when a pass reaches a guardian who does not answer.

Per guardian (rule 1)

1. When the turn opens, send a signed liveness probe that includes a nonce and the pass id.
2. Re-probe at fixed intervals across a grace window G. Do not skip on the first miss.
3. If a signed answer arrives within G, the guardian keeps the turn with the normal limit L.
4. If every probe in G goes unanswered, mark the guardian *skipped*. The guardian keeps their seat. A signed answer later puts them back in their place in the rotation.

Per pass (rule 2)

• Keep a budget B = L for the pass. Each grace window spent on a guardian who ends up skipped is subtracted from B.
• When B reaches 0, no further guardians are probed and waited on in this pass. Each one left is queued, and the next pass probes them first.
• The longest a thief can stall one pass is about L + G: one full budget plus the window already running. The worst case is no longer L × roster size.

Why an honest guardian who is briefly offline is safe

• One missed probe never costs a turn, because of the grace window.
• Being queued does not skip the guardian. They are probed first in the next pass.
• When they answer, they get their turn back. Being offline for a while delays their turn but does not remove it.

Open questions

• Should G scale with how often a guardian has been reachable before? A thief could use that to push G longer.
• Queued guardians could build up over many passes if the thief keeps cutting them off. Is a cap on the queue length needed?