Execute Dependency-Constrained Work at Scale

Problem: Dependency-Aware Task Runner

You are tasked with building a task execution engine that processes a set of jobs based on their dependencies. Each job has a unique ID, a list of IDs it depends on (pre-requisites), and a function to execute. A job can only start once all its dependencies have completed successfully.

Requirements

1. Dependency Resolution: A job must not start until all its dependencies have finished.
2. Concurrency Limiting: You must support a max_workers parameter to limit the number of jobs executing simultaneously.
3. Failure Propagation: If a job fails, all jobs that depend on it (directly or indirectly) must be cancelled or marked as failed, and the engine should stop scheduling them.
4. Execution: Provide a method execute_all(jobs) that returns a dictionary mapping job IDs to their execution status (SUCCESS, FAILED, or CANCELLED).

Interface

class Job:
    def __init__(self, job_id, dependencies, task_func):
        self.job_id = job_id
        self.dependencies = dependencies  # List of job_ids
        self.task_func = task_func

def execute_all(jobs: List[Job], max_workers: int) -> Dict[str, str]:
    # Returns map of {job_id: status}
    pass

Constraints

• jobs count: up to 10,000.
• max_workers: up to 100.
• The graph is guaranteed to be a Directed Acyclic Graph (DAG).

Example

Input: Jobs A (no deps), B (deps: [A]), C (deps: [A]). If A succeeds, B and C can run concurrently. If A fails, B and C are cancelled.

Edge Cases

• Cycles in dependencies (the problem guarantees a DAG, but how would you detect/handle an invalid graph?).
• A job depending on a non-existent ID.
• Empty list of jobs.