What is Parallel Execution?

icon ONE
icon FOR
Photo - What is Parallel Execution?
From November 2023 to January 2024, the SEI price increased by 5.7 times. One reason for this surge could be the revolutionary approach to transaction processing used by Sei — parallel execution.
Parallel execution refers to the simultaneous processing of multiple transactions or operations, instead of handling them one by one. This approach is akin to paying for goods at a grocery store where, instead of one grocery line, there are multiple grocery lines available. This allows for servicing more customers at once, thereby reducing the wait time for each.
The analogy of parallel transaction execution: one grocery line vs. three lines. Source: medium.com

The analogy of parallel transaction execution: one grocery line vs. three lines. Source: medium.com

Traditionally, blockchain processes transactions sequentially. However, this approach leads to delays and limits the scalability of the network. Just as shoppers wait to pay for their groceries at a single line, network participants wait for their transaction to be processed from the mempool.

Parallel execution is used to simultaneously process unrelated transactions, i.e., events that do not affect each other. For example, if two different users trade tokens on different trading platforms, their transactions can be processed at the same time. However, if they trade on the same platform, their transactions need to be executed sequentially.

The challenge in implementing parallel execution lies in identifying independent transactions. This requires understanding how each operation impacts the state of the blockchain. With a large number of interconnected applications, identifying such transactions becomes more difficult.

Models of Parallel Execution

Most blockchains with parallel execution are based on the following models:

  1. State Access Model: An approach where transactions accessing a certain part of the blockchain's state are predetermined. This allows for distinguishing between independent and dependent operations.
  2. Optimistic Model: An approach assuming all transactions in the blockchain are independent. Adjustments for dependencies are made after they are identified. 

Examples of blockchains that use the state access model include Solana, Sei v1, and Sui, while examples of the optimistic model include Aptos, Monad, and Sei v2.

Despite the main principle of parallel execution being the simultaneous processing of transactions, there are several ways to implement this approach. We won't dive into the specifics of each but will instead highlight the most effective ones through examples of projects that utilize them.

Solana

Solana is the first blockchain to employ a parallel transaction processing method. Its approach involves identifying dependencies between data and operations' access to various parts of the blockchain.

Imagine a data storage system where each transaction requests access to a specific file:

  • If the requests do not overlap, transactions are processed independently of one another.
  • If transactions request access to the same file, they require coordination.

Each transaction specifies the part of the blockchain it intends to access. This requirement is part of the Sealevel transaction execution model, which, together with the Proof of History (PoH) consensus algorithm, enables parallel processing in the Solana blockchain.

Sei

Sei is a Layer 1 blockchain built on the Cosmos SDK (Software Development Kit) and the CosmWasm smart contract platform. It employs a delegated architecture, distributing blockchain functions across three layers: 

  • The application layer executes application logic and processes transactions.
  • Consensus layer allows all network participants to reach an agreement on the state of the blockchain.
  • The network layer is responsible for distributing transactions within the blockchain.

Sei enhances the capabilities of the standard Cosmos SDK through Cosmos' customizability, enabling parallel transaction execution. Features of Sei include the Twin-Turbo consensus and a parallelization mechanism.

Twin-Turbo Consensus

The Twin-Turbo consensus is characterized by two elements: intelligent distribution and optimistic block processing. These functions work together to simplify transaction execution and block confirmation.

Intelligent Block Propagation. Consider a scenario where Anna and Alex each have their home libraries. When Anna sends Alex a book to read, he often already has it in his library. This approach is labor-intensive and redundant.

Similarly, validators send blocks containing transaction information. Since consensus participants continually exchange operational data, most of them already possess the necessary transaction information. This means validators waste time waiting for transactions that are already in their mempool.
Proposing blocks without intelligent propagation. Source: twitter.com

Proposing blocks without intelligent propagation. Source: twitter.com

Instead of sending the entire content, Anna now only sends Alex the title of the book she's reading. He checks his library for the book and, if missing, requests a copy from Anna.

Likewise, validators send a proposal containing only the transaction hash. When other network participants receive such a proposal, they use transactions from their mempool to reconstruct the block in their blockchain state (similar to checking a library for books). 
Intelligent block propagation. Source: twitter.com

Intelligent block propagation. Source: twitter.com

If validators do not have information on all transactions in their local mempool, they wait for the block content to be published.

Optimistic Block Processing.
After a block has been proposed and distributed among validators, they send each other prevote and precommit messages. This approach aids in agreeing on the exact block they wish to add to the blockchain.

Following a precommit, validators verify each transaction within the block. However, with a large amount of data, this stage is time-consuming and resource-intensive. 
Standard block processing vs. optimistic block processing. Source: github.com

Standard block processing vs. optimistic block processing. Source: github.com

Instead, validators continue to process other operations in the blockchain, applying them to a "candidate state." If the proposed block is agreed upon, the candidate state is also accepted. Otherwise, it is discarded.

Parallelization Mechanism v1

Sei leverages the Cosmos SDK, essentially an "operating system" for blockchains within the Cosmos ecosystem. When nodes receive a transaction block, they initiate a validation process comprising three phases: BeginBlock, DeliverTx, and EndBlock. Sei has adapted the last two phases to facilitate parallel execution.

DeliverTx. Conventionally, transactions are processed sequentially during the DeliverTx phase. Sei revolutionizes this approach by enabling parallel execution.

To circumvent uncertainty (scenarios where the outcomes of certain processes are undesirable for simultaneous execution), Sei segregates transactions into those that can be executed in parallel and those that require sequential execution. This segregation is based on the type and data of the operations they perform.

EndBlock. As Sei caters to the financial sector, transactions within the blockchain can be categorized into buys and sells, and their execution platforms into markets.

In the EndBlock phase, Sei amalgamates buy and sell orders for assets. Rather than processing these orders sequentially, Sei filters out independent transactions and concurrently verifies them at the block's end.

Orders are deemed independent if they do not impact the same market within a single block.
Block processing with and without parallelization. Source: github.com

Block processing with and without parallelization. Source: github.com

Parallelization Mechanism v2

On November 29, 2023, the project team heralded the launch of Sei v2, the first parallel EVM merging the best features of Solana and Ethereum. This new iteration introduced:

  1. EVM compatibility.
  2. Optimistic parallelization.
  3. SeiDB.

The second update specifically enhances Sei's capability for parallel transaction processing. Hence, this discussion will primarily focus on optimistic parallelization.

In Sei's initial version, developers were tasked with manually identifying transaction dependencies, a process that detracted from network efficiency. Sei v2 adopts an optimistic stance, presuming all transactions are independent and can be processed concurrently.
How optimistic parallelization works in Sei v2. Source: twitter.com

How optimistic parallelization works in Sei v2. Source: twitter.com

When conflicting transactions emerge, affecting identical storage segments, Sei undertakes the following:

  • Conflict identification. The system discerns which storage segments a given transaction attempts to access.
  • Transaction processing. Following the identification of conflicting operations, these are executed sequentially.

This cycle repeats until all conflicts have been addressed, allowing Sei to proceed with processing subsequent transactions devoid of any clashes.

Other Blockchains with Parallel Execution

Sui. Transactions within Sui modify object attributes, which could be either assets or smart contracts. If a transaction is deemed independent (meaning no other transaction interacts with the target object), it circumvents the consensus mechanism.

Aptos. Utilizes an optimistic execution principle. Unlike Sei v2, Aptos automatically identifies transaction dependencies in case of conflicts, without requiring transactions to specify which part of the blockchain state they affect.

Monad. A high-performance, L1 blockchain compatible with Ethereum. Similar to Aptos, Monad embraces an optimistic execution approach, assuming transactions are unrelated and addressing dependencies as they arise.

avatar
Vlad Vovk
Author
Writes about DeFi and cryptocurrencies from a technological perspective.