Directed Acyclic Graph (DAG)

In workflow orchestration, each node in the DAG represents a discrete, executable unit of work or an activity. Nodes encapsulate the logic to be performed.

• Examples include: running a script, querying a database, calling an API, or training a machine learning model.
• Nodes can have properties like execution timeouts, retry policies, and resource requirements.
• The granularity of a node is defined by the workflow designer.

The edges define the dependencies and data flow between tasks. They enforce execution order and can optionally pass data or context from upstream to downstream tasks.

• A downstream task cannot execute until all of its upstream dependencies are satisfied (e.g., completed successfully).
• This dependency graph allows the orchestrator to automatically schedule tasks as soon as their prerequisites are met.
• Edges enable the modeling of complex, fan-in/fan-out dependency patterns.

A topological sort is a linear ordering of a DAG's nodes where for every directed edge from node A to node B, A appears before B in the ordering. This ordering is the blueprint for sequential execution.

• Workflow engines perform a topological sort to determine a valid execution sequence.
• Multiple valid orderings may exist for the same DAG, but all respect the dependency constraints.
• This is the algorithmic foundation that makes DAGs executable.

Because a DAG only specifies partial order, tasks that are not directly or indirectly dependent on each other can be executed in parallel. This is a key advantage for performance optimization.

• The orchestrator identifies independent branches of the graph and can schedule their nodes concurrently.
• This maximizes resource utilization and reduces end-to-end workflow runtime.
• The degree of parallelism is constrained only by the dependency structure, not by the definition language.

An execution plan is a runtime blueprint generated by the workflow engine from a static workflow definition (like a DAG). It specifies the precise, concrete steps for a single run:

• Order of Operations: The exact sequence of tasks to execute.
• Resource Bindings: Specific compute targets or queues for each task.
• Conditional Paths: Resolved logic branches based on initial input data. While the DAG defines possible paths, the execution plan is the deterministic roadmap for a specific instance. It is often optimized for performance before execution begins.

A Workflow Definition Language is a domain-specific language (DSL) or data format used to declaratively specify the structure of an executable workflow. It encodes the DAG's tasks, dependencies, and control flow. Common examples include:

• Apache Airflow: DAGs defined in Python.
• AWS Step Functions: JSON-based Amazon States Language (ASL).
• CWL (Common Workflow Language): YAML/JSON-based standard for portable workflows. These languages allow developers to version, share, and reproduce complex workflows as code.

A process instance is a single, specific execution of a workflow definition. Each time a DAG is triggered, a new instance is created. Key characteristics:

• Isolated State: Maintains its own variables, execution history, and logs.
• Independent Lifecycle: Can be started, paused, resumed, or canceled without affecting other instances.
• Audit Trail: Records all events and state changes for that specific run. In a DAG-based system, each instance tracks which nodes (tasks) have been completed for that particular execution.

An activity is a discrete, executable unit of work within a workflow, represented as a node in a DAG. It is the atomic operation the engine invokes. Activities can be:

• Service Calls: Invoking an external API or microservice.
• Function Execution: Running a piece of business logic or a data transformation.
• Human Tasks: Requiring manual input or approval. The workflow engine manages the scheduling, input/output passing, and retry logic for each activity, while the activity itself contains the business logic.