Binance Research
Crypto exchange Binance has released an entire study dedicated to parallel execution in the blockchain. The solution itself appeared quite a long time ago, but analysts have already theoretically summarized many years of developments. The technology is known primarily thanks to the Solana project, but the solution is used in various forms by Vara, TON, Sui, Sei, Aptos, Linera, Fuel and Monad.
Sequential execution problem
The constraint on blockchain throughput is the problem of sequential execution.. In a sequential execution solution, each transaction must be verified by the entire network, which results in significant energy consumption and increased load on miners or validators.
Parallel execution is designed to separate tasks and process a larger number of transactions at a time, which should have a beneficial effect on throughput and provide better network scaling.
Specialists from Binance note that the evolution of computing machines is moving towards multitasking and multithreading. Proof can be found in the fact that processor frequencies have not advanced much over the past 20 years – instead, the number of cores has increased. This is a more efficient solution, since the vast majority of tasks will be handled by several weaker cores faster than one powerful one.
Programming follows this trend – modern solutions are written in such a way as to maximize the positive effect of multithreading. Therefore, solutions are in fashion, where many problems are solved in parallel.
How parallel execution works in blockchain
To put it as simply as possible, parallel execution allows you to process many transactions simultaneously. In conditions of large computing power and multitasking, a parallel solution seems to be the most effective.
But there are a number of problems that make consistent blockchain solutions more reliable and secure. Home – dependent transactions. What if two transactions are processed in parallel, in which, for example, the same address sends cryptocurrencies to two different addresses. If these transactions are carried out completely in parallel, then the owner of the wallet will be able to spend his coins twice. And this is not welcome.
Therefore, dependent transactions can only be executed sequentially. Transaction dependency is a key concept that means that:
-
The output of one task is written to the input of another – e.g.. Alice transfers ETH to Bob (output), and Vasya (input) transfers ETH to Carol.
-
The output of multiple tasks is written to the same memory location – for example, both Alice and Carol transfer ETH to Vasya (output).
From this it is obvious that only tasks independent of each other can be parallelized. This, in turn, means that the speed of a parallel blockchain will always be limited by the longest chain of dependent tasks. And yet, there are quite a lot of independent tasks, so there is plenty of room for parallel solutions in the blockchain.
Various parallel execution methods
-
Sharding. Binance experts classify sharding as parallel execution. This is true at the macro level (shards actually process their transactions in parallel to each other), but at the micro level, each shard within itself processes transactions sequentially.
-
Task parallelism. This is when multiple transactions are processed simultaneously. For example, if a node has 16 cores, it can simultaneously process 16 transactions.
-
Data parallelism – one instruction for multiple data (Single instruction multiple data, or SIMD). SIMD is a low-level solution that allows you to work more efficiently with data. It is useful for hashing and verification.
Disadvantages of Parallel Execution
Compared to simple sequential solutions, parallel designs do not always look advantageous. Quite the contrary, they are much less safe, predictable and simple.
The authors of the study summarized the vulnerabilities of parallel execution and identified a number of critical ones:
-
race situation (uncertainty of the result that arises when independent transactions are incorrectly defined);
-
re-entry problems;
-
deadlocks, where two or more tasks wait indefinitely for each other to complete. Each of them cannot be executed until the other is executed;
-
non-composability, when the program code itself may be correct, but produce critical errors when used under different conditions.
Also conditionally critical (that is, critical in certain situations) two more problems are seen:
-
priority inversion, or a condition in which a low-priority task can indirectly block a higher-priority task due to scheduler malfunction;
-
resource starvation, where some tasks consume more resources than they should, depriving other tasks of the resources they need.
Conclusion
Chasing bandwidth can be quite expensive. Parallel execution is a complex design that introduces many problems, but provides significant performance gains.