Simulate a deterministic single-worker job scheduler with priority aging, dependency gating, exponential-backoff retries, and cascading cancellation of failed jobs' dependents.
Simulate a job scheduler on a single worker in discrete time. A global clock starts at 0. One job runs at a time. The simulation is fully deterministic: nothing is random, and failures are scripted in advance.
Each job has: a string id, an integer base priority (HIGHER = more urgent), an integer duration in ticks, a positive maxAttempts, and a list of dependency ids. A dependency must already exist when the job is submitted.
A job is one of: PENDING, RUNNING, SUCCEEDED, FAILED (permanent), CANCELLED. A job is RUNNABLE only once all its dependencies have SUCCEEDED.
SCHEDULING : when the worker is free at a tick, among all jobs that are PENDING, have all dependencies SUCCEEDED, and are not currently in retry-backoff, pick the one with:
1. highest EFFECTIVE priority, where effective = basePriority + floor(waitingTicks / AGING_STEP). waitingTicks is the number of ticks since the job first became runnable (its dependencies first all satisfied). Aging continues to accrue while a job waits, including during retry backoff.
2. tie -> earliest submission order.
3. tie -> smallest id (lexicographic).
EXECUTION : a started job occupies the worker for its duration. It completes `duration` ticks after it starts. Within a single tick, a completion is processed before any new job is started, so the worker can finish one job and start another in the same tick.
RETRY + BACKOFF : when an attempt completes and that attempt is scripted to fail: if the job still has attempts remaining, it returns to PENDING and becomes schedulable again only after a backoff of BACKOFF_BASE * 2^(attemptsUsed - 1) ticks measured from the failure tick. If no attempts remain, the job becomes FAILED (permanent).
DEPENDENCY CASCADE : when a job becomes FAILED permanently, every job that transitively depends on it is immediately CANCELLED and can never run. CANCEL events are emitted in breadth-first order: first every direct dependent of the failed job in submission order, then their dependents in submission order, and so on level by level.
Commands:
- INIT <AGING_STEP> <BACKOFF_BASE> : first line.
- SUBMIT <id> <priority> <duration> <maxAttempts> <depCount> [dep1 ... depk] : print "OK <id>", or "BADDEP <id>" if any listed dependency has not been submitted yet (the job is not added).
- FAIL <id> <attempt> : script that the given 1-based attempt number of <id> will fail when it completes. No output.
- TICK <n> : advance the clock n ticks, running the scheduler each tick and emitting event lines (below) in the order they occur.
- STATUS <id> : print "<id> <STATE> <attemptsUsed>", or "<id> UNKNOWN 0" if never submitted.
- RUNNING : print the id currently running, or "IDLE".
Event lines emitted during TICK (absolute tick index of the event):
- "START <id> <tick>" when a job starts an attempt
- "DONE <id> <tick>" when a job succeeds
- "FAILATTEMPT <id> <tick> <attemptsUsed>" when an attempt fails but retries remain or it's the final attempt
- "FAILED <id> <tick>" when a job becomes permanently failed
- "CANCEL <id> <tick>" when a job is cascade-cancelled