Skip to main content

Sequencing

Sequencing is the post-consensus phase in which transactions agreed upon by the IOTA consensus protocol are processed and scheduled for execution.

Due to the nature of shared objects, conflicting transactions writing to the same shared objects must be executed sequentially. If not carefully managed, scheduling a large number of such conflicting transactions can lead to congestion during execution. The primary goal of sequencing is to schedule as many transactions as possible while avoiding an unmanageable load on the execution layer.

The sequencing phase is responsible for two main tasks:

  • Ordering: Establishing the causal order of transactions committed by the IOTA consensus protocol.
  • Congestion prevention: Deferring the execution of transactions that could otherwise overwhelm the execution layer.

The IOTA sequencing algorithm addresses both of these tasks simultaneously.

Sequencing Algorithm​

In IOTA, transactions are initially ordered based on their gas prices. Each transaction is then evaluated individually using the placement algorithm described below to determine its position in the execution trace. During this evaluation, every transaction is subject to a binary decision: Schedule or Defer.

  • Deferred transactions are carried over to the transaction set of the next consensus commit. If a transaction is deferred a specific number of times (currently 10), is it eventually cancelled.
  • Scheduled transactions are forwarded to the execution phase in the order determined by the placement algorithm.
Best-effort sequencing

In the IOTA sequencing algorithm, a transaction is deferred only if there is no way to schedule it without exceeding the load threshold on any individual execution worker.

Placement algorithm: Causal ordering of transactions​

The IOTA sequencing algorithm orders transactions with a strong emphasis on execution efficiency. When a transaction is evaluated, the algorithm searches for a suitable position in the execution trace where it can be placed without causing conflicts. This allows for parallel execution of transactions that operate on disjoint sets of shared objects.

To achieve this, the algorithm maintains an allocation map that tracks access to shared objects. This ensures that no shared object is written to by more than one transaction at the same time, preserving execution safety.

Once all transactions have been evaluated, the allocation map implicitly defines the causal ordering of the scheduled transactions.

The sequencing algorithm guarantees that the longest sequential execution trace remains within a predefined load threshold.

Fairness in sequencing

In IOTA, transactions included in the same consensus commit that write to an identical set of shared objects are guaranteed to be executed in descending order of their gas prices.

Example​

In the example below, we consider three transactions:

  • Tx1 touches only object a,
  • Tx3 touches only object b,
  • Tx2 touches both objects a and b.

Tx1 is willing to pay the highest gas price, while Tx3 offers the lowest. Additionally, Tx2 is estimated to have the longest execution time, while Tx3 has the shortest. In the figure below, the length of the transactions depict their execution time.

Sequencing example, final sequencing

A naive sequencing of these transactions based solely on gas price would result in a serial execution, since Tx2 would have to wait for Tx1 to complete (due to their shared access to object a), and Tx3 would need to wait for Tx2 (due to shared access to b). As a result, all transactions would be executed one after another.

Instead, IOTA's sequencing algorithm carefully places Tx3 before Tx2 in the causal order. This enables simultaneous execution of Tx1 and Tx3 (which access disjoint objects), provided that there are sufficient parallel resources. The case is illustrated in the following image.

Sequencing example, final sequencing

Gas Price Feedback for Cancelled Transactions​

When a transaction is cancelled due to shared object congestion, IOTA provides a suggested gas price in the execution status of that cancelled transaction. This suggested gas price informs the sender about the minimum gas price they should have paid for their transaction to have been successfully scheduled in the same consensus commit.

Other networks such as Sui only report which shared objects were congested, but not what gas price would have been enough for successful execution. Users on those networks have to rely on dry-run simulations to figure out a sufficient gas price. The IOTA protocol instead provides gas price feedback based on the actual scheduling decisions in the latest commits, which helps the sender estimate a sufficient gas price for a retry.

How the suggested gas price is calculated​

  • The gas price feedback algorithm simulates the allocation of the cancelled transaction at the latest possible execution start time within the commit's capacity, so that only the last scheduled transactions on each congested object overlap with it.
  • The clearing gas price for each object is the maximum gas price across those last scheduled transactions that overlap with the simulated allocation of the cancelled transaction.
  • The suggested gas price is then calculated as the maximum clearing gas price across all input objects of the cancelled transaction plus one, ensuring that it would outbid competing transactions and get scheduled.
  • The suggested gas price value is capped at the protocol's maximum gas price.

Using the suggested gas price​

The sender can then retry the cancelled transaction with a gas price equal to or greater than the suggested value.

Suggested gas price is an estimate

If the same congestion pattern repeats in a future commit, paying the suggested gas price guarantees scheduling. In practice, congestion changes between commits, so the suggested value should be considered as a good starting estimate but not as a hard guarantee to be scheduled. For better price estimate, please refer to gas price prediction during dry run.