Implement the design for a request scheduler in which each agent owns a dependency graph of tool calls, several agents run concurrently, and one global limit caps the number of tool calls executing at once. Explain synchronization, failure, cancellation, fairness, and shutdown. ### Constraints & Assumptions - A tool call becomes runnable only after all of its dependencies succeed. - Different agents may have independent ready work. - The global concurrency limit must never be exceeded. - Tool calls may fail, time out, or ignore cancellation briefly. ### Clarifying Questions to Ask - Should a failed dependency cancel only its descendants or the entire agent request? - Is fairness required across agents or is maximum throughput sufficient? - Can tool calls be retried, and are they idempotent? ### What a Strong Answer Covers - A validated per-agent DAG with dependency counters and reverse edges. - A thread-safe ready queue plus a global semaphore or fixed worker pool. - Atomic state transitions that prevent duplicate launch. - Failure propagation, retries, timeouts, cancellation, result collection, and clean shutdown. - Fairness, backpressure, metrics, and tests that expose races. ### Follow-up Questions - How would you prevent one large agent from monopolizing every worker? - What happens if cancellation arrives while a dependency completes? - How would you make the scheduler deterministic enough to test?