ETL Dependency Orchestration

A pipeline is a set of tasks where some can't start until others finish: you can't transform before you extract, and you can't build the report until both the load and the transform are done. An orchestrator's first job is working out a legal order to run them in.

That's a topological sort.

Task: write topological_order(tasks) returning a list of task names in an order where every task appears after all of its dependencies.

• tasks maps each task name to the list of task names it depends on. A task with no dependencies maps to an empty list.
• Many orders are usually valid, so to make the answer unique: at every step, among the tasks whose dependencies are all already scheduled, pick the alphabetically first one.
• If no task is available but tasks remain, the dependencies form a cycle and no legal order exists. Return an empty list.
• Every name mentioned as a dependency is also a key in tasks.

The algorithm (Kahn's) is a loop over three steps: find the tasks with nothing outstanding, pick the alphabetically first, then remove it from everyone else's outstanding list. Repeat until nothing is left — or until nothing is available, which is how you detect the cycle.

That cycle check is the valuable part. A real orchestrator must refuse to start rather than deadlock halfway through a run, and "no task is ready but tasks remain" is the complete and exact condition for it.