Batch-Schedule-Execute: On Optimizing Concurrent Deterministic Scheduling for Blockchains (Extended Version)
0
📊
Sign in to get full access
Overview
- Executing smart contracts is a compute and storage-intensive task that dominates the performance of modern blockchains.
- Multicore computers present an opportunity to improve smart contract execution runtime through concurrency.
- A unique challenge for blockchains is that all replicas (miners or validators) must execute all smart contracts in the same logical order to maintain the semantics of State Machine Replication (SMR).
- This paper studies the maximum level of parallelism attainable by focusing on the conflict graph between transactions packaged in the same block.
Plain English Explanation
Blockchains rely on executing smart contracts - programs that automatically enforce the terms of a contract. However, running these smart contracts is a computationally intensive task, which limits the overall performance of modern blockchain systems.
Since computers are becoming more powerful with multiple cores, the researchers in this paper believe that running smart contracts concurrently, or in parallel, could improve their execution time. However, there's a unique challenge for blockchains - all the computers (known as miners or validators) that maintain the blockchain must execute the smart contracts in the same order to keep the system consistent.
To address this, the researchers study how much parallelism, or concurrent execution, is possible by looking at the relationships, or "conflicts", between the different transactions bundled together in a single block. This reveals a potential vulnerability that block creators could exploit against existing blockchain concurrency solutions, which rely on a total ordering phase to maintain consistency.
The researchers develop a new framework called Active State Machine Replication (ASMR) that can formally analyze this problem. They introduce the idea of "graph scheduling" and the "minimal latency scheduling problem," which they prove is a complex, NP-hard problem. They show that a simplified version of this problem is equivalent to the classic Graph Vertex Coloring Problem, but the more general heterogeneous case is even more complex.
The practical implications of these theoretical results are discussed, providing insights into the challenges of improving blockchain performance through concurrency.
Technical Explanation
The researchers develop a novel Active State Machine Replication (ASMR) framework to formally study the maximum level of parallelism attainable when focusing on the conflict graph between transactions packaged in the same block.
They introduce the concept of graph scheduling and the definition of the "minimal latency scheduling problem," which they prove to be NP-hard. The researchers show that the restricted version of this problem for homogeneous transactions is equivalent to the classic Graph Vertex Coloring Problem, but the heterogeneous case is more complex.
Through this analysis, the researchers expose a performance vulnerability that block creators may exploit against existing blockchain concurrency solutions, which rely on a total ordering phase for maintaining consistency amongst all replicas.
Critical Analysis
The researchers provide a thorough theoretical analysis of the challenges in achieving parallelism for smart contract execution on blockchains. By framing the problem as a graph scheduling and minimal latency scheduling problem, they identify fundamental complexities that limit the degree of concurrency attainable.
One limitation of the work is that it is primarily focused on the theoretical aspects, without providing empirical validation of the identified performance vulnerabilities or the practical implications of the ASMR framework. Further research would be needed to assess the real-world impact and potential mitigation strategies.
Additionally, the researchers acknowledge that their analysis assumes a simplified model of blockchain transactions and their dependencies. Incorporating more realistic factors, such as heterogeneous transaction types and sharding, could yield additional insights and challenges.
Overall, this work makes a valuable contribution by rigorously examining the fundamental tradeoffs between parallelism and consistency in blockchain smart contract execution, setting the stage for future research on more efficient multi-processor scheduling for blockchain systems.
Conclusion
This paper tackles the challenge of improving the performance of smart contract execution on blockchains by exploring the potential for increased parallelism. The researchers develop a novel ASMR framework and identify the inherent complexities in achieving maximal parallelism due to the need to maintain consistency across all blockchain replicas.
The theoretical analysis reveals a performance vulnerability that block creators could exploit, as well as the NP-hard nature of the "minimal latency scheduling problem" for heterogeneous transactions. These insights provide a foundation for future research on more efficient concurrency models and scheduling algorithms for blockchain systems.
Overall, this work highlights the delicate balance between performance and consistency in blockchain architectures, and the need for innovative solutions to unlock the full potential of smart contract execution on modern multi-core hardware.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
📊
0
Batch-Schedule-Execute: On Optimizing Concurrent Deterministic Scheduling for Blockchains (Extended Version)
Yaron Hay, Roy Friedman
Executing smart contracts is a compute and storage-intensive task, which currently dominates modern blockchain's performance. Given that computers are becoming increasingly multicore, concurrency is an attractive approach to improve programs' execution runtime. A unique challenge of blockchains is that all replicas (miners or validators) must execute all smart contracts in the same logical order to maintain the semantics of State Machine Replication (SMR). In this work, we study the maximal level of parallelism attainable when focusing on the conflict graph between transactions packaged in the same block. This exposes a performance vulnerability that block creators may exploit against existing blockchain concurrency solutions, which rely on a total ordering phase for maintaining consistency amongst all replicas. To facilitate the formal aspects of our study, we develop a novel generic framework for Active State Machine Replication (ASMR) that is strictly serializable. We introduce the concept of graph scheduling and the definition of the minimal latency scheduling problem, which we prove to be NP-hard. We show that the restricted version of this problem for homogeneous transactions is equivalent to the classic Graph Vertex Coloring Problem, yet show that the heterogeneous case is more complex. We discuss the practical implications of these results.
Read more8/21/2024
📶
0
Fast Transaction Scheduling in Blockchain Sharding
Ramesh Adhikari, Costas Busch, Miroslav Popovic
Sharding is a promising technique for addressing the scalability issues of blockchain. It divides the $n$ participating nodes into $s$ disjoint groups called shards, where each shard processes transactions in parallel. We investigate scheduling algorithms for the blockchain sharding systems, where each transaction resides in a shard of the communication graph and attempts to access accounts at possibly remote shards. We examine batch scheduling problems on the shard graph $G_s$, where given a set of transactions, we aim to find efficient schedules to execute them as fast as possible. First, we present a centralized scheduler where one of the shards has global knowledge of transactions to be processed. For general graphs, where the transaction and its accessing objects are arbitrarily far from each other with a maximum distance $d$, the centralized scheduler provides $O(kd)$ approximation to the optimal schedule, where $k$ is the maximum number of shards each transaction accesses. Consequently, for a Clique graph where shards are at a unit distance from each other, we obtain $O(k)$ approximation to the optimal schedule. We also get $O(k log s)$ approximation for Hypercube, Butterfly, and $g$-dimensional Grid, where $g=O(log s)$. Next, we provide a centralized scheduler with a bucketing approach that offers improved bounds for special cases. Finally, we provide a distributed scheduler where shards do not require global transaction information. We achieve this by using a hierarchical clustering of the shards and using the centralized scheduler in each cluster. We show that the distributed scheduler has a competitive ratio of $O(mathcal{A_mathcal{CS}} log ^2 s)$, where $mathcal{A_mathcal{CS}}$ is the approximation ratio of the centralized scheduler. To our knowledge, we are the first to give provably fast transaction scheduling algorithms for blockchain sharding systems.
Read more5/27/2024
0
Maximizing Blockchain Performance: Mitigating Conflicting Transactions through Parallelism and Dependency Management
Faisal Haque Bappy, Tarannum Shaila Zaman, Md Sajidul Islam Sajid, Mir Mehedi Ahsan Pritom, Tariqul Islam
While blockchains initially gained popularity in the realm of cryptocurrencies, their widespread adoption is expanding beyond conventional applications, driven by the imperative need for enhanced data security. Despite providing a secure network, blockchains come with certain tradeoffs, including high latency, lower throughput, and an increased number of transaction failures. A pivotal issue contributing to these challenges is the improper management of conflicting transactions, commonly referred to as contention. When a number of pending transactions within a blockchain collide with each other, this results in a state of contention. This situation worsens network latency, leads to the wastage of system resources, and ultimately contributes to reduced throughput and higher transaction failures. In response to this issue, in this work, we present a novel blockchain scheme that integrates transaction parallelism and an intelligent dependency manager aiming to reduce the occurrence of conflicting transactions within blockchain networks. In terms of effectiveness and efficiency, experimental results show that our scheme not only mitigates the challenges posed by conflicting transactions, but also outperforms both existing parallel and non-parallel Hyperledger Fabric blockchain networks achieving higher transaction success rate, throughput, and latency. The integration of our scheme with Hyperledger Fabric appears to be a promising solution for improving the overall performance and stability of blockchain networks in real-world applications.
Read more7/4/2024
🌀
0
Deferred Objects to Enhance Smart Contract Programming with Optimistic Parallel Execution
George Mitenkov, Igor Kabiljo, Zekun Li, Alexander Spiegelman, Satyanarayana Vusirikala, Zhuolun Xiang, Aleksandar Zlateski, Nuno P. Lopes, Rati Gelashvili
One of the main bottlenecks of blockchains is smart contract execution. To increase throughput, modern blockchains try to execute transactions in parallel. Unfortunately, however, common blockchain use cases introduce read-write conflicts between transactions, forcing sequentiality. We propose RapidLane, an extension for parallel execution engines that allows the engine to capture computations in conflicting parts of transactions and defer their execution until a later time, sometimes optimistically predicting execution results. This technique, coupled with support for a new construct for smart contract languages, allows one to turn certain sequential workloads into parallelizable ones. We integrated RapidLane into Block-STM, a state-of-the-art parallel execution engine used by several blockchains in production, and deployed it on the Aptos blockchain. Our evaluation shows that on commonly contended workloads, such as peer-to-peer transfers with a single fee payer and NFT minting, RapidLane yields up to $12times$ more throughput.
Read more5/13/2024