Implement Dependency-Aware Job Scheduling - The Scheduler

                      TASK
                    

Implementation

Some jobs can only start after others finish. Dependency-aware scheduling builds an execution plan that respects these constraints while maximising parallelism: jobs in the same round have no shared dependencies and can run simultaneously.

Implement a node that plans and executes dependency-constrained workflows:

// a has no deps; b and c depend on a; d depends on b and c
{ "type": "submit_workflow", "msg_id": 1,
  "jobs": [{"id":"a","deps":[]},{"id":"b","deps":["a"]},
            {"id":"c","deps":["a"]},{"id":"d","deps":["b","c"]}] }
-> { "type": "workflow_submitted", "in_reply_to": 1,
    "execution_plan": {"round_1":["a"],"round_2":["b","c"],"round_3":["d"]} }

// Circular dependency detected
-> { "type": "workflow_rejected",
    "error": "Circular dependency detected: a->b->c->a" }

// Critical path: a(100ms)->b(200ms)=300ms vs a(100ms)->c(50ms)=150ms
{ "type": "submit_workflow", "msg_id": 3,
  "jobs": [{"id":"a","duration_ms":100,"deps":[]},
            {"id":"b","duration_ms":200,"deps":["a"]},
            {"id":"c","duration_ms":50,"deps":["a"]}] }
-> { "type": "workflow_submitted", "in_reply_to": 3,
    "critical_path": ["a","b"], "critical_path_length_ms": 300 }

When a job fails, every job that (directly or transitively) depends on it must be cancelled.

Sample Test Cases

Topological sort schedulingTimeout: 5000ms

Input

{
  "src": "client",
  "dest": "scheduler",
  "body": {
    "type": "submit_workflow",
    "msg_id": 1,
    "jobs": [
      {
        "id": "a",
        "deps": []
      },
      {
        "id": "b",
        "deps": [
          "a"
        ]
      },
      {
        "id": "c",
        "deps": [
          "a"
        ]
      },
      {
        "id": "d",
        "deps": [
          "b",
          "c"
        ]
      }
    ]
  }
}

Expected Output

{"src": "scheduler", "dest": "client", "body": {"type": "workflow_submitted", "in_reply_to": 1, "execution_plan": {"round_1": ["a"], "round_2": ["b", "c"], "round_3": ["d"]}}}

Circular dependency detectionTimeout: 5000ms

Input

{
  "src": "client",
  "dest": "scheduler",
  "body": {
    "type": "submit_workflow",
    "msg_id": 1,
    "jobs": [
      {
        "id": "a",
        "deps": [
          "b"
        ]
      },
      {
        "id": "b",
        "deps": [
          "c"
        ]
      },
      {
        "id": "c",
        "deps": [
          "a"
        ]
      }
    ]
  }
}

Expected Output

{"src": "scheduler", "dest": "client", "body": {"type": "workflow_rejected", "in_reply_to": 1, "error": "Circular dependency detected: a->b->c->a"}}

Hints

Hint 1▾

Build execution plan: each round contains jobs whose all deps completed in prior rounds

Hint 2▾

Detect circular deps with DFS — a back-edge during traversal means a cycle

Hint 3▾

Critical path: the chain of duration_ms values with the maximum total from source to sink

Hint 4▾

On job failure, cancel all jobs that directly or transitively depend on it

Hint 5▾

Round 1 = jobs with no deps; Round 2 = jobs whose only deps are in Round 1; and so on

Resources

Critical Path Method

Finding the longest path through a dependency graph

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

topological sortcritical pathcircular dependencyfailure propagationparallel rounds

main.py

python