Rafael Romão's Coding Labs

Lab L12 · Java + Go

Implementing a dependency task executor

Build an executor for tasks that depend on other tasks. Each task lists the tasks that must succeed before it may run. First validate the whole graph — unknown dependency, duplicate edge or cycle means reject before running anything. Then execute in waves: every task whose prerequisites are done runs in parallel (at most concurrency at once), and a task whose prerequisite failed or was skipped is marked skipped instead of run.

The task

A deploy pipeline: build must finish before test and lint; package needs both; deploy needs package; docs depends on nothing. If lint fails, package and deploy must not run, but test and docs should still finish so you see every result. Detecting a cycle up front matters because a cycle discovered halfway through means some tasks already had side effects. The reference reuses the L03 aggregator to run each wave.

wave 1wave 2wave 3wave 4builddocstestlint ✗packageskippeddeployskippeda prerequisite failed → never calledvalidate first: unknown dependency, duplicate edge or cycle → reject before any task runs
Columns are waves. A failure in wave 2 turns everything downstream of it into “skipped” without touching the independent tasks.

What you implement

public final class DependencyExecutor {
    public record Task<V>(List<String> dependsOn, Callable<V> run) {}
    public record Outcome<V>(V value, Throwable failure, boolean skipped) {}

    public static <V> Map<String, Outcome<V>> execute(
            Map<String, Task<V>> tasks,     // id -> task
            int concurrency,                // max tasks running at once within a wave
            int maxTasks,                   // max size of 'tasks'
            BooleanSupplier cancelled) throws InterruptedException;
}

Rules

  • Validation happens before any callback runs: invalid limits, a dependency on an unknown id, the same dependency listed twice, or a cycle → IllegalArgumentException.
  • Cycle check: Kahn's algorithm — repeatedly remove tasks with no remaining prerequisites; if some tasks are never removed, there is a cycle.
  • Wave 1 is every task with no prerequisites. Wave k+1 is every task whose last prerequisite was in wave k. Within a wave at most concurrency tasks run at once.
  • Success → Outcome(value, null, false). Throws → Outcome(null, e, false).
  • If any prerequisite failed or was skipped → Outcome(null, null, true) and the callback is never called. Skips propagate transitively; independent branches keep running.
  • The result has one entry per task. Dependencies only order execution; they do not pass results between tasks.

Worked example

  1. build; test ← build; lint ← build; package ← test, lint; deploy ← package; docs.
  2. Wave 1: build, docs. Wave 2: test, lint. lint throws.
  3. package → skipped; deploy → skipped (its prerequisite was skipped). build, docs, test → values.
  4. Add build ← deploy → cycle → IllegalArgumentException, and no callback ran.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: DependencyExecutor.java · tests: DependencyExecutorTest.java. Go starter: executor.go · tests: executor_test.go.

cd java
./gradlew test --tests 'labs.dag.*'

cd go
go test -race -count=1 ./dag
Reveal the reference solutions

Java: DependencyExecutor.java
Go: executor.go

When to use

Use this lab when a finite set of tasks has explicit prerequisite relationships. Each task has a unique string identity, a list of prerequisite identities, and a callback. Validate a positive concurrency limit and a positive maximum task count. Reject missing dependencies, duplicate dependency edges, null callbacks, and cycles before invoking any callback. The caller must not modify the task graph while it is being copied.

The result maps every identity to its value, failure, or skipped status. A task whose prerequisite failed or was skipped does not run. Independent tasks continue. Dependencies express execution ordering, not automatic result injection: callbacks obtain their inputs through an explicitly owned mechanism. The executor is in memory and neither persists task state nor retries effects.

Steps

  1. Build indegrees and successors. Count prerequisites per node and record each node's dependants. A duplicate edge is rejected instead of accidentally counting the same prerequisite twice. Copy dependency lists so the execution view is stable.
  2. Validate globally before effects. Run a topological traversal on a separate indegree copy. If the visited count differs from the graph size, a cycle exists. Do this before executing an independent root: a late cycle discovery after other side effects would make invalid-input behavior nondeterministic.
  3. Execute ready waves. Gather all zero-indegree nodes for a wave. Skip nodes with failed prerequisites and pass runnable callbacks to the bounded all-settled aggregator. Wait for that wave to finish, record its outcomes, and then release the next wave. This reference favors clear ownership over maximum utilization: one slow task can delay a dependent of an already-finished sibling until the wave completes.
  4. Propagate dependency failures. A skipped node still releases successor bookkeeping, allowing the scheduler to classify its descendants rather than leaving them forever pending. The result distinguishes skipped work from a callback that actually ran and failed.
  5. Preserve cancellation ownership. The underlying aggregator checks cancellation before starting callbacks and waits for owned execution. Running tasks need cooperative transport cancellation; a blocked callback can delay the whole execution. Cancellation is not a transaction rollback of already-completed effects.
  6. Test forbidden histories. Include a failing parent with a child whose body fails the test if called. Verify success, failure, and skipped outcomes separately. Include a cycle and an otherwise runnable root, then verify graph validation rejects the entire input before any callback executes. Add a diamond graph and controlled execution barrier to characterize a more aggressive ready-queue extension.

Checklist

Recall and variation

Rebuild indegree validation before reading Go or Java. Variation: add a cycle beside an independent root. Acceptance: validation rejects the entire input before even the independent callback runs. Then add a diamond and verify a child waits for both successful parents.

  • Cycles and missing prerequisites fail before any effects
  • Failed prerequisites prevent their descendants from executing
  • Independent tasks continue according to the stated policy
  • Concurrent task and total input limits are separate
  • A result means completed, failed, or skipped rather than silently pending

Signals

Working: every valid node receives one terminal outcome and no child starts before all its prerequisites complete successfully.

Going wrong: cycle detection happens after side effects, duplicate edges strand a node, or a scheduler claims to saturate workers while intentionally waiting at wave barriers. Graph bookkeeping is O(V+E), while aggregation and wave construction add overhead; graph depth and task duration shape utilization.

Related