The Same Transaction Dependencies, Three Ways to Run in Parallel
Suppose two transactions run together. One finishes quickly; the other takes longer. A third transaction needs only the result of the faster one to begin. Must it wait for the slower one too?
The conditions for preserving the same ledger result as sequential execution do not settle this question. Having the necessary results ready and assigning the next piece of work to a worker are separate decisions.
Nigo represents dependencies between transactions as a graph called a DAG. It implements three ways to execute that graph: WAVE, READY_QUEUE, and WORK_FIRST_CONTINUATION. Before focusing on the names, let us look at the waiting each approach tries to reduce in the same set of transactions.
Add one more transfer to the faster branch
A holds 100 units of an asset and wants to send 20 to B, 10 to C, and 5 to D. Let us split this into five transactions that consume and create StateCells: records holding an asset's owner and quantity. Assume the asset permits direct transfers by its owner, and all five are valid Direct Cell transactions signed by A. There is no additional issuance or burning, the fee amount is zero, and the block has enough execution capacity for all five.
- ① Split: Consume A's 100 and create two records owned by A: 60 on the left and 40 on the right.
- ② Send to B: Consume the left-hand 60 and create B's 20 and A's 40.
- ③ Send to C: Consume the right-hand 40 and create C's 10 and A's 30.
- ④ Send to D: Consume A's 40 left by ② and create D's 5 and A's 35.
- ⑤ Merge the remainder: Consume the 35 from ④ and the 30 from ③ to create A's 65.
The final state is A=65, B=20, C=10, D=5, for a total of 100. The records sent to B, C, and D are not inputs to the merge; each remains in the ledger. The right-hand 40 from ① and the left-hand 40 left by ② have equal quantities but are different records. Assume the two branches share no other records they modify, including those involved in fee handling.
An arrow means that the later transaction needs a result from the earlier one. Its number is the quantity of A's asset passed between them. B's 20, C's 10, and D's 5 remain as described above.
Fix the candidate order as ① → ② → ③ → ④ → ⑤. Once ① finishes, ② and ③ can be computed together. Transaction ④ needs only the result of ②, while ⑤ must wait for both ③ and ④. The important distinction is that ④ comes after ③ in the candidate order but does not need ③'s computation result. There is therefore an opportunity to compute ④ while ③ is still running. The final order in which transaction results are applied remains the original candidate order.
A DAG represents the waiting that must be respected
Each point in the diagram is a transaction, and each arrow represents a required ordering. A graph whose arrows have a direction, with no path that follows those arrows back to its starting point, is a directed acyclic graph, or DAG.
Nigo's execution graph connects the effects of earlier transactions on later ones in the fixed candidate order. Because arrows only lead from smaller candidate numbers to larger ones, they cannot form a cycle in which transactions wait for one another to finish. This is a plan for computing transactions within one node; it does not turn the block consensus structure into another kind of DAG.
Asset transfers are not the only reason to add a dependency. The original order also matters when a later transaction reads a record an earlier one writes, when a later transaction changes a record an earlier one reads, or when both change the same record. Merely reading the same policy does not, by itself, create a dependency.
This analysis covers more than inputs and outputs. It also includes asset policies, fee handling, and lookups of records that do not exist. Conversely, connecting two attempts to consume the same input does not make both attempts valid. The DAG does not replace transaction validation.
The graph tells us which predecessor results must be ready. A scheduler decides when to start a ready transaction and which worker should run it. That is why the same DAG can be scheduled in several ways.
WAVE: finish one group before starting the next
First, group transactions into stages that can run together.
This example produces four groups: ① → ②·③ → ④ → ⑤.
WAVE completes the computation of every transaction in the current group and passes the checked results to the next group.
This gives each group a clear boundary between the state it reads and the state it passes on. Nigo keeps this existing execution structure as its baseline scheduler, so other scheduling strategies can be compared against it for the same results.
The tradeoff is waiting for the slowest transaction in a group. Even if ② has finished, ④ in the next group does not start while ③ is still running. Regardless of whether ④ needs ③'s result, completion of the whole group is the condition for moving to the next stage.
To make the difference visible, assume that at most two transactions can be computed at once. Transaction ③ takes four time units; each of the others takes one. These durations are chosen to explain scheduling, not calculated from the asset quantities. We also omit the extra time needed for scheduling, state transfer, and validation.
With WAVE, ① runs from 0–1, ② from 1–2, and ③ from 1–5. Transaction ④ starts at 5, when the group finishes, rather than at 2, when ② finishes. It runs from 5–6, followed by ⑤ from 6–7, for a total of seven time units.
READY_QUEUE: enqueue work as its required results become ready
Transaction ④ needs the result of ②. READY_QUEUE aims to give it a chance to run as soon as that condition is met. Ready transactions enter a bounded queue and are assigned to available workers.
Nigo does not start a successor merely because it receives notice that a predecessor's computation has finished. It validates the result and actual state accesses, applies the changes to the temporary state the successor will use, and then reduces the number of outstanding predecessors. Only transactions whose predecessor results are all ready enter the execution queue. Applying these changes passes temporary state to the next computation; it does not commit them to the DB.
In this example, ④ can be assigned at time 2, when ②'s result becomes ready. A worker is available, so ④ runs from 2–3 while ③ continues until 5. Transaction ⑤ needs both results, so it runs from 5–6 after ③ finishes. The total is six time units.
The fact that ⑤ has two predecessors matters. Starting it just because ④ finishes would leave it without the 30 for A that ③ creates. The merge becomes ready only after both results have been delivered. The queue does not relax this requirement.
The motivation for considering READY_QUEUE was to reduce unnecessary waiting for a whole group. But finding ready transactions, enqueuing and dequeuing them, and preparing the state they will read also have costs. Being ready means a transaction is eligible to run; its actual start can still be delayed if all workers are busy.
WORK_FIRST_CONTINUATION: let the worker continue with the next transaction
Using a queue introduces a step of registering and assigning the next piece of work after a transaction finishes. This time, consider whether the worker that just finished can continue directly with a successor.
WORK_FIRST_CONTINUATION lets the current worker take one of the successors that has just become ready. Among those successors, Nigo gives priority to the one earliest in candidate order and leaves the others in the shared queue. Instead of submitting a new execution task for each transaction, a fixed number of tasks keep processing subsequent transactions.
In this example, the worker that finishes ① can continue with ②, while another worker takes ③ from the queue. The worker that finishes ② continues with the now-ready ④. Finishing ④ does not make ⑤ available yet: it still needs ③. When the worker running ③ later satisfies that final dependency, it can continue with ⑤.
The aim is to reduce the cost of being assigned the next piece of work, while preserving every required wait. A worker does not permanently own a branch. When it has no continuation available, it looks for other work in the shared queue.
The diagram below shows computation intervals for the three strategies under the same duration assumptions. Each row identifies a transaction, not a worker. Overlapping bars indicate computations that can run together.
Time units are illustrative, not measurements. The diagram is not a trace of actual thread assignments.
It is natural that WORK_FIRST is no shorter than READY_QUEUE in this diagram. The scheduling costs it aims to reduce were left out of the assumed durations in the first place. To establish a real benefit, we need measurements that include those costs.
How do Direct Cell and Native Program fit into the same structure?
Using this design requires knowing, in sufficient detail before execution, which state a transaction may read and change. A Direct Cell transaction specifies the inputs it will consume and the outputs it will create. Core, Nigo's transaction execution layer, adds fee records and asset policy lookups to this information when analyzing the scope of state access.
Native Program transactions also specify the state they need and the changes they propose. As described in the Native Program validation model, the program validates the supplied state and proposed changes, and Core checks its result against the actual transition. This also requires a restricted execution environment that prevents the program from arbitrarily reading or changing ledger state outside the scope supplied to it. For parallel execution, the analysis must also check the applicable program and policy, and include accesses on the failure path where only fee changes remain.
Calling the same Native Program therefore does not mean every transaction must wait for every other one. Transactions that change different records and only read a common policy may be able to run together. Conversely, transactions with different asset inputs still have a dependency to consider if they change the same allowance or fee record.
Core provides each transaction's access scope; the block execution layer builds the DAG and schedules the computations. Neither Direct Cell handling code nor the Native Program itself creates threads or selects a scheduler. The business logic is separate from the arrangement of execution across multiple transactions.
Participating in this common structure does not mean using all three scheduling strategies. In the current parallel path, segments containing only Direct Cell transactions can use any of the three configured strategies. Segments containing Native Program transactions use WAVE. General EVM transactions and operations that change system-wide execution assumptions form sequential boundaries, with parallel segments on either side.
Nigo uses WAVE as the baseline and implemented the other two strategies as alternatives for Direct Cell segments. WAVE is currently the default scheduler; the two alternatives are experimental strategies. Parallel execution itself is also off in the default configuration. Enabling it and choosing a scheduler are separate decisions. This does not mean that automatic selection of the best strategy for each workload has been completed.
One graph, different costs
WAVE passes state across group boundaries. READY_QUEUE opens an execution opportunity when an individual transaction's dependencies are satisfied. WORK_FIRST_CONTINUATION tries to reduce assignment costs by having the current worker take that opportunity directly. All three must respect the same DAG dependencies, final result application order, and validation conditions.
In the example, starting ④ earlier shortened the computation by one time unit. But if the transactions themselves are very cheap, managing dependencies and preparing state may cost more than this saves. If validation, storage, or other work around block execution takes longer, an improvement within the computation stage may produce only a small reduction in total processing time.
That leaves the next question: Did these choices to reduce waiting and scheduling costs help in actual measurements? The performance investigation separates execution time from total processing time in Nigo's measurement records and examines which strategies benefit when previously validated results can be reused.