![\"\"](\"https:\/\/uplatz.com\/blog\/wp-content\/uploads\/2025\/10\/A-Systematic-Analysis-of-Parallel-Execution-in-Deterministic-Systems-From-Optimistic-Concurrency-to-Block-STM-and-Optimal-Scheduling-1024x576.jpg\")
<\/p>\n
bundle-multi-3-in-1—sap-sd By Uplatz<\/a><\/h3>\nThe Sequential Bottleneck<\/b><\/h3>\n
The most straightforward method to ensure determinism is sequential execution. By processing transactions one after another, in a predefined order, the system guarantees that every node will compute the same state transitions and reach the same final state. However, this approach is fundamentally unscalable. In an era of multi-core processors, sequential execution leaves vast computational resources idle, creating a severe throughput bottleneck that is incapable of meeting the demands of high-performance applications.<\/span>2<\/span> As transaction volumes grow, the latency and throughput of a sequentially executed blockchain drop precipitously, highlighting the urgent need for parallel execution models that can harness modern hardware without sacrificing deterministic consistency.<\/span><\/p>\n <\/p>\n
A Taxonomy of Parallel Execution Models<\/b><\/h3>\n
<\/p>\n
The quest to overcome the sequential bottleneck has given rise to several distinct architectural models for parallel transaction execution in blockchains. These models differ primarily in where and how they determine transaction dependencies and schedule execution.<\/span><\/p>\n\n- The Ethereum Model (Pre-Execution):<\/b> In this model, the responsibility for execution is centralized. A single node, the block proposer, executes the transactions, computes the resulting state differences (state-diffs), and packages this information along with the transaction list into a block. This block is then propagated across the network, where other nodes (validators) need only to validate the pre-computed state changes against the transactions.<\/span>4<\/span> While this simplifies the task for validators, it concentrates the entire execution workload on the proposer, creating a centralized performance ceiling defined by the capacity of a single machine.<\/span><\/li>\n
- The Solana Model (Static Dependencies):<\/b> This model takes a static, upfront approach to dependency analysis. To be included in a block, transactions must explicitly declare which accounts (state) they will read from and write to. This <\/span>a priori<\/span><\/i> knowledge allows the runtime to construct a dependency graph and schedule non-conflicting transactions for parallel execution.<\/span>4<\/span> The primary drawback of this approach is that it shifts a significant burden onto developers, who must accurately predict and declare all state accesses. This can be complex, error-prone, and may force transactions that do not actually conflict to be executed sequentially out of an abundance of caution.<\/span>2<\/span><\/li>\n
- The Sui Model (Object-Centric):<\/b> The Sui model refines the dependency concept by focusing on data ownership. State is organized into “objects,” and transactions are classified based on whether they access owned objects or shared objects. Transactions that only touch objects owned by a single address can be processed in parallel with minimal coordination. Transactions involving shared objects require more complex consensus and ordering. This model excels at parallelizing transactions with clear, non-overlapping data access patterns but requires a more structured approach to state management.<\/span><\/li>\n
- The Aptos Model (Post-Ordering Acceleration):<\/b> This model represents a paradigm shift by decoupling transaction ordering from execution. The block proposer’s primary role is to establish a definitive, sequential order of transactions within a block. This ordered block is then agreed upon via consensus. Following consensus, each validator node independently executes the entire block in parallel, using a sophisticated engine to achieve a final state that is identical to the one that would have been produced by sequential execution.<\/span>4<\/span> This approach democratizes the execution workload across all validators and is the model that Block-STM is designed to power.<\/span><\/li>\n<\/ul>\n
The evolution from the Ethereum model to the Aptos model signifies a fundamental redistribution of computational responsibility in a distributed system. In the former, a single proposer node bears the heavy load of execution, while validators perform the lighter task of verification. This creates an inherent asymmetry and a single point of performance limitation. The Aptos model, in contrast, makes every validator responsible for the full execution workload. This architectural choice is only viable if a highly efficient parallel execution engine is available to every node. Without such an engine, each validator would simply be encumbered by the same sequential bottleneck that the proposer faced, nullifying any systemic benefit. Therefore, the feasibility and success of the Aptos model are inextricably linked to the performance of an advanced execution engine like Block-STM. It strategically trades a centralized execution bottleneck for a distributed parallel execution challenge, a challenge that Block-STM is purpose-built to solve.<\/span><\/p>\n <\/p>\n
II. Paradigms of Concurrency Control: Pessimism vs. Optimism<\/b><\/h2>\n
<\/p>\n
Concurrency control is the mechanism by which a system coordinates simultaneous accesses to shared data to ensure consistency and integrity.<\/span>6<\/span> In the context of transaction processing, this means preserving the illusion that each transaction executes in isolation, a property known as serializability. The two dominant philosophical approaches to achieving this are pessimistic and optimistic concurrency control.<\/span><\/p>\n <\/p>\n
Pessimistic Concurrency Control (PCC): The “Ask for Permission” Approach<\/b><\/h3>\n
<\/p>\n
Pessimistic Concurrency Control (PCC) operates under the assumption that conflicts between transactions are a common occurrence and must be actively prevented.<\/span><\/p>\n\n- Core Mechanism:<\/b> The primary tool of PCC is locking. Before a transaction can read or write a piece of data, it must first acquire a lock on that data item. If another transaction already holds a conflicting lock, the requesting transaction must wait until the lock is released.<\/span>8<\/span> The most well-known PCC protocol is two-phase locking (2PL), which governs the acquisition and release of these locks to ensure serializability.<\/span>6<\/span><\/li>\n
- Strengths:<\/b> PCC’s main advantage is its guarantee of correctness. By preventing conflicts from ever occurring, it ensures that the database state is never corrupted.<\/span><\/li>\n
- Weaknesses:<\/b> This guarantee comes at a significant cost. The overhead of acquiring and releasing locks can be substantial, especially in systems with high transaction volumes.<\/span>10<\/span> More importantly, PCC can severely limit concurrency, as transactions are forced to wait even if a conflict would not have ultimately materialized. This can lead to poor resource utilization and reduced throughput. Furthermore, PCC systems are vulnerable to deadlocks, a situation where two or more transactions are stuck waiting for each other to release locks, requiring a separate mechanism for detection and resolution.<\/span>9<\/span> Under high-contention workloads, the performance of PCC protocols degrades significantly as lock contention and waiting times increase.<\/span>11<\/span><\/li>\n<\/ul>\n
<\/p>\n
Optimistic Concurrency Control (OCC): The “Ask for Forgiveness” Approach<\/b><\/h3>\n
<\/p>\n
Optimistic Concurrency Control (OCC) is founded on the opposite assumption: that conflicts between transactions are rare.<\/span>10<\/span> Instead of preventing conflicts with locks, it allows transactions to execute freely and only checks for conflicts at the very end, resolving them after the fact.<\/span><\/p>\n\n- The Three Phases of OCC:<\/b> The lifecycle of a transaction under OCC is typically divided into three distinct phases <\/span>13<\/span>:<\/span><\/li>\n<\/ul>\n
\n- Read Phase:<\/b> The transaction executes its logic. It reads values from the shared database but buffers all its writes in a private workspace or transactional log.<\/span>8<\/span> These tentative writes are not visible to any other transaction. During this phase, the system records the set of data items the transaction has read (its read-set) and the set of data items it intends to write (its write-set).<\/span><\/li>\n
- Validation Phase:<\/b> This is the critical conflict-detection step. Before the transaction is allowed to commit, the system validates its execution. It checks whether any other transaction has committed changes to the data items in the current transaction’s read-set since the read phase began.<\/span>10<\/span> If a conflict is detected (i.e., the data read is now stale), the transaction’s validation fails.<\/span><\/li>\n
- Write Phase:<\/b> If validation is successful, the transaction is committed. Its buffered writes are applied to the database, making them permanent and visible to all subsequent transactions.<\/span>13<\/span> If validation fails, the transaction is aborted, its private writes are discarded, and it is typically restarted from the beginning.<\/span>15<\/span><\/li>\n<\/ol>\n
\n- Strengths:<\/b> In environments with low data contention, OCC can achieve significantly higher throughput than PCC. By avoiding the overhead of locking, it minimizes coordination and allows for a high degree of parallelism.<\/span>7<\/span> Because it is a non-locking protocol, OCC is also inherently free from deadlocks.<\/span>14<\/span><\/li>\n
- Weaknesses:<\/b> The primary drawback of OCC is its performance degradation under high contention. When conflicts are frequent, the rate of transaction aborts and re-executions skyrockets. This leads to a large amount of wasted computational work, as the effort spent on aborted transactions is thrown away.<\/span>13<\/span> In extreme cases, the system can enter a state of “contention collapse,” where throughput plummets as transactions are repeatedly aborted.<\/span>16<\/span> The cost of concurrency is thus shifted from the upfront coordination of locking to the backend penalty of rollback and re-execution.<\/span>10<\/span><\/li>\n<\/ul>\n
The decision between PCC and OCC can be viewed through an economic lens, as a trade-off based on the anticipated “cost of conflict.” PCC is akin to purchasing a comprehensive insurance policy. It requires paying a fixed, upfront premium\u2014the overhead of locking\u2014on every single transaction, regardless of whether a conflict was ever likely. This premium buys the certainty that no conflicts will occur. OCC, on the other hand, operates like a “pay-as-you-go” model with a deductible. It forgoes the upfront premium, but must pay a potentially high penalty\u2014the cost of an abort and re-execution\u2014whenever a conflict actually materializes.<\/span><\/p>\nWhen the conflict rate is low, the cumulative cost of these occasional penalties in OCC is far less than the cumulative cost of the mandatory premiums in PCC, making OCC the more efficient strategy. However, as the conflict rate rises, the frequency and total cost of OCC’s penalties can increase dramatically, eventually surpassing the cost of PCC’s steady premiums. This inflection point marks the onset of contention collapse. The central goal of an advanced optimistic system like Block-STM is to fundamentally alter this economic balance. It does so not by trying to prevent conflicts, but by dramatically reducing the <\/span>cost of the penalty<\/span><\/i> associated with an abort, thereby extending the viability of the optimistic approach into much higher-contention regimes.<\/span><\/p>\nThe following table provides a comparative summary of these two fundamental approaches to concurrency control.<\/span><\/p>\n\n\n\nFeature<\/span><\/td>\n Pessimistic Concurrency Control (PCC)<\/span><\/td>\n Optimistic Concurrency Control (OCC)<\/span><\/td>\n<\/tr>\n\nCore Assumption<\/b><\/td>\n Conflicts are likely and must be prevented.<\/span><\/td>\n Conflicts are rare and can be resolved after detection.<\/span><\/td>\n<\/tr>\n\nPrimary Mechanism<\/b><\/td>\n Locking (e.g., Two-Phase Locking).<\/span><\/td>\n Read\/Validate\/Write phases with private workspaces.<\/span><\/td>\n<\/tr>\n\nConflict Handling<\/b><\/td>\n Prevention: Transactions wait for locks to be released.<\/span><\/td>\n Detection & Resolution: Conflicting transactions are aborted and restarted.<\/span><\/td>\n<\/tr>\n\nPerformance (Low Contention)<\/b><\/td>\n Sub-optimal due to constant locking overhead.<\/span><\/td>\n High throughput due to minimal coordination.<\/span><\/td>\n<\/tr>\n\nPerformance (High Contention)<\/b><\/td>\n Degrades due to lock contention and long wait times.<\/span><\/td>\n Performance collapses due to high abort rates and wasted work.<\/span><\/td>\n<\/tr>\n\nKey Bottleneck<\/b><\/td>\n Lock manager, wait queues.<\/span><\/td>\n Validation phase, cost of re-execution.<\/span><\/td>\n<\/tr>\n\nDeadlock Risk<\/b><\/td>\n High; requires deadlock detection and resolution mechanisms.<\/span><\/td>\n None; deadlock-free by design.<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n <\/p>\n
III. Block-STM: Turning the Ordering Curse into a Performance Blessing<\/b><\/h2>\n
<\/p>\n
Block-STM is a state-of-the-art, in-memory parallel execution engine designed specifically for deterministic SMR systems like the Aptos blockchain.<\/span>17<\/span> It is built upon the principles of Software Transactional Memory (STM), a concurrency control paradigm that provides high-level abstractions to make parallel programming appear more like simple sequential execution.<\/span>19<\/span> However, Block-STM is not a general-purpose STM library; it is a highly specialized system that leverages unique properties of the blockchain use-case to achieve unprecedented performance.<\/span>1<\/span><\/p>\n <\/p>\n
The Central Innovation: Leveraging the Preset Serialization Order<\/b><\/h3>\n
<\/p>\n
The most profound innovation of Block-STM is its ability to transform a traditional constraint of blockchain systems into its greatest performance asset. Unlike general-purpose OCC or STM systems, which must dynamically discover a valid serializable order among concurrent transactions, Block-STM is given a block where the final serialization order is already determined by the proposer: $tx_1 < tx_2 <… < tx_n$.<\/span>1<\/span> In conventional thinking, this fixed order is a “curse” that constrains parallelism. Block-STM ingeniously inverts this, using the preset order as a global, unambiguous source of truth for dependency resolution, thereby turning the ordering curse into a performance blessing.<\/span>3<\/span><\/p>\nThis preset order acts as an implicit, decentralized coordination mechanism, drastically reducing the need for explicit and costly synchronization primitives between threads. In a typical parallel system, if two threads contend for a resource, they must engage in an expensive runtime negotiation (e.g., atomic compare-and-swap, lock acquisition) to resolve the conflict. In Block-STM, the outcome of any conflict between $tx_i$ and $tx_j$ (where $i < j$) is pre-ordained: the effects of $tx_i$ must prevail. This deterministic rule is embedded directly into the engine’s core logic, allowing it to replace expensive, dynamic synchronization with cheap, predictable operations. It transforms a potentially chaotic race for state access into an orderly, pre-negotiated process, which is the foundational reason for its low overhead and remarkable scalability.<\/span><\/p>\n <\/p>\n
Core Components Deep Dive<\/b><\/h3>\n
<\/p>\n
Block-STM’s architecture is a synthesis of established techniques and novel optimizations, all centered around the preset order.<\/span><\/p>\n <\/p>\n
Multi-Version Data Structure<\/b><\/h4>\n
<\/p>\n
To manage concurrent state access, Block-STM employs a multi-version data structure. This structure avoids crude write-write conflicts by allowing multiple versions of the same data location to coexist in memory.<\/span>3<\/span> When a transaction writes to a location, it creates a new version tagged with its unique identifier, which consists of its index in the block and its current “incarnation” number (since a transaction may be re-executed multiple times).<\/span>20<\/span><\/p>\nThe preset order dictates a simple yet powerful rule for reads: when a transaction $tx_j$ needs to read a memory location, the data structure provides it with the value written by the transaction $tx_i$ with the highest index such that $i < j$.<\/span>3<\/span> This ensures that every read is deterministic and consistent with the final serial order, even while transactions are executing speculatively and out of sequence.<\/span><\/p>\n <\/p>\n
Speculative Execution and Validation<\/b><\/h4>\n
<\/p>\n
Worker threads in the system speculatively execute transactions in parallel, assuming no conflicts will occur.<\/span>3<\/span> Each execution of a transaction is termed an “incarnation”.<\/span>1<\/span> During an incarnation, the engine meticulously tracks all memory accesses:<\/span><\/p>\n\n- Read-set:<\/b> A log of each memory location read, along with the specific version (transaction ID and incarnation number) that was observed.<\/span>3<\/span><\/li>\n
- Write-set:<\/b> A private buffer of all memory locations and the new values the transaction intends to write.<\/span>3<\/span><\/li>\n<\/ul>\n
After an incarnation completes, its write-set is applied to the multi-version data structure, and a validation task is scheduled. The validation process is the heart of conflict detection. It involves re-reading every location in the transaction’s read-set and comparing the currently visible version against the version originally recorded.<\/span>3<\/span> If all versions match, the validation succeeds, indicating that the transaction’s view of the world remains consistent. If a mismatch is found, it signifies that a transaction with a lower index has since been re-executed and produced a new version of the data. This constitutes a Read-Write conflict, causing the validation to fail and triggering an abort and subsequent re-execution of the current transaction.<\/span><\/p>\n <\/p>\n
The Collaborative Scheduler<\/b><\/h4>\n
<\/p>\n
Coordinating the execution and validation tasks across dozens of threads is a critical challenge. Naive approaches using standard concurrent data structures like priority queues are notoriously difficult to scale.<\/span>1<\/span> Block-STM introduces a novel, low-overhead collaborative scheduler that elegantly sidesteps this problem.<\/span>17<\/span> The scheduler prioritizes tasks associated with lower-indexed transactions, as their outcomes affect all subsequent transactions. Crucially, because the transactions are identified by a compact and bounded set of indices (from 1 to $n$), the scheduler can implement this prioritization using a few shared atomic counters instead of complex, lock-heavy data structures. This counting-based approach is a key optimization made possible only by the preset serialization order.<\/span>1<\/span><\/p>\n <\/p>\n
Dynamic Dependency Estimation<\/b><\/h4>\n
<\/p>\n
The single greatest threat to performance in an OCC system is a cascade of aborts, where the re-execution of one transaction triggers a chain reaction of validation failures in dependent transactions.<\/span>3<\/span> Block-STM’s most innovative feature for mitigating this is its dynamic dependency estimation mechanism.<\/span><\/p>\nWhen a transaction $tx_i$ fails validation and is aborted, its write-set is not merely discarded. Instead, the engine uses this information as a strong hint about where $tx_i$ is likely to write in its next incarnation. It marks every memory location in the aborted write-set with a special ESTIMATION flag in the multi-version data structure.<\/span>3<\/span> Later, if another transaction $tx_j$ attempts to read a location marked with this flag, it immediately knows that it has a potential dependency on the outcome of $tx_i$. Rather than proceeding with stale data and guaranteeing a future abort, $tx_j$ can pause its execution and wait for the dependency to be resolved.<\/span>3<\/span> This “just-in-time” dependency detection has two major advantages over pre-execution approaches that try to compute a full dependency graph upfront: (1) estimates are generated lazily and only when a conflict actually occurs, avoiding unnecessary overhead, and (2) the estimates are based on a more recent and therefore more accurate execution state.<\/span>17<\/span><\/p>\n <\/p>\n
Lazy, Block-Level Commits<\/b><\/h4>\n
<\/p>\n
Finally, Block-STM leverages the operational context of blockchains, where state updates are applied atomically at the block level. This allows the engine to forgo the expensive synchronization required for committing each transaction individually. Instead, it accumulates all state changes from successful transaction executions in the multi-version data structure. Only after all transactions in the block have been successfully executed and validated does the system perform a single, lazy commit of the entire block’s state changes. This is achieved efficiently using a “double-collect” technique managed by two atomic counters, minimizing synchronization to the very end of the process.<\/span>1<\/span><\/p>\n <\/p>\n
IV. Conflict Detection, Abort Rates, and Mitigation Strategies<\/b><\/h2>\n
<\/p>\n
The performance of any optimistic concurrency control system is ultimately determined by its ability to manage conflicts and minimize the resulting aborts. While Block-STM’s architecture is designed to be robust, understanding the nature of conflicts and the strategies to mitigate them is crucial.<\/span><\/p>\n <\/p>\n
Anatomy of a Transaction Conflict<\/b><\/h3>\n
<\/p>\n
A conflict arises when two or more transactions access the same memory location, and at least one of these accesses is a write operation.<\/span>8<\/span> There are three canonical types of data conflicts <\/span>22<\/span>:<\/span><\/p>\n\n- Write-Write (W\u2192W):<\/b> Two transactions attempt to write to the same location. Block-STM’s multi-version data structure inherently resolves these conflicts by storing both writes as distinct versions.<\/span><\/li>\n
- Write-Read (W\u2192R):<\/b> One transaction reads a location after another transaction has written to it. The preset order and multi-version read rule in Block-STM manage this by ensuring the reading transaction always sees the correct, preceding version.<\/span><\/li>\n
- Read-Write (R\u2192W):<\/b> One transaction reads a location, and a concurrent transaction later writes to it. This is the most problematic type of conflict in an optimistic system and the primary cause of aborts.<\/span><\/li>\n<\/ul>\n
<\/p>\n
Primary Cause of Aborts: Validation Failure<\/b><\/h3>\n
<\/p>\n
In Block-STM, a transaction is aborted and scheduled for re-execution when its validation fails. This occurs when the assumptions made during its speculative execution are proven false. The canonical scenario is an R\u2192W conflict that violates the preset serial order. For example, consider transaction $tx_j$. During its execution, it reads a value written by $tx_i$ (where $i < j$). Subsequently, $tx_i$ itself is aborted (due to a conflict with an even earlier transaction, $tx_k$) and is re-executed. In its new incarnation, $tx_i$ writes a <\/span>different<\/span><\/i> value to that same memory location. When $tx_j$’s validation task runs, it re-reads the location and discovers that the version it originally read is no longer the latest version produced by a transaction with an index less than $j$. This version mismatch signals a broken dependency, invalidates the entire execution of $tx_j$, and forces an abort.<\/span>3<\/span><\/p>\n <\/p>\n
The Critical Impact of Abort Cascades<\/b><\/h3>\n
<\/p>\n
The true performance risk is not a single abort, but a cascade of aborts. The re-execution of a single, low-indexed transaction can have far-reaching consequences. If $tx_1$ aborts, its new write-set might invalidate the read-sets of $tx_2$, $tx_5$, and $tx_{100}$, and any other transaction that read the values it originally wrote. When these dependent transactions are subsequently validated, they too will fail and be aborted. This chain reaction can lead to an enormous amount of wasted computation, potentially bringing the entire parallel execution process to a standstill. As noted in the Block-STM research, minimizing these cascades is “the name of the performance game” for any STM system.<\/span>3<\/span><\/p>\n <\/p>\n
Advanced Abort Reduction Techniques<\/b><\/h3>\n
<\/p>\n
Beyond Block-STM’s foundational dynamic dependency estimation, research has explored more granular and semantically aware strategies to reduce the high cost of aborts.<\/span><\/p>\n\n- Operation-Level vs. Transaction-Level Conflict Resolution:<\/b> A fundamental limitation of traditional OCC, including Block-STM, is its coarse-grained, transaction-level resolution. If a conflict is detected in just one of a transaction’s many operations, the <\/span>entire transaction<\/span><\/i> must be aborted and restarted from scratch.<\/span>23<\/span> A more advanced approach, exemplified by <\/span>ParallelEVM<\/b>, introduces operation-level concurrency control. This system uses a detailed operation log to trace dependencies <\/span>within<\/span><\/i> a single transaction. Upon a validation failure, it does not abort the whole transaction. Instead, it enters a redo phase where it identifies and re-executes <\/span>only the specific operations<\/span><\/i> that were directly affected by the conflict, while preserving the results of all other, conflict-free operations.<\/span>23<\/span> This fine-grained approach significantly reduces wasted work, with evaluations showing it can achieve a 4.28x speedup on real-world Ethereum workloads, compared to just 2.49x for a traditional OCC implementation.<\/span>23<\/span><\/li>\n
- Data-Driven Timestamp Management (TicToc):<\/b> Conventional timestamp-ordering (T\/O) protocols often cause unnecessary aborts by assigning a rigid, static timestamp to a transaction before it executes. The <\/span>
<\/p>\n
A Taxonomy of Parallel Execution Models<\/b><\/h3>\n
<\/p>\n
The quest to overcome the sequential bottleneck has given rise to several distinct architectural models for parallel transaction execution in blockchains. These models differ primarily in where and how they determine transaction dependencies and schedule execution.<\/span><\/p>\n The evolution from the Ethereum model to the Aptos model signifies a fundamental redistribution of computational responsibility in a distributed system. In the former, a single proposer node bears the heavy load of execution, while validators perform the lighter task of verification. This creates an inherent asymmetry and a single point of performance limitation. The Aptos model, in contrast, makes every validator responsible for the full execution workload. This architectural choice is only viable if a highly efficient parallel execution engine is available to every node. Without such an engine, each validator would simply be encumbered by the same sequential bottleneck that the proposer faced, nullifying any systemic benefit. Therefore, the feasibility and success of the Aptos model are inextricably linked to the performance of an advanced execution engine like Block-STM. It strategically trades a centralized execution bottleneck for a distributed parallel execution challenge, a challenge that Block-STM is purpose-built to solve.<\/span><\/p>\n <\/p>\n <\/p>\n Concurrency control is the mechanism by which a system coordinates simultaneous accesses to shared data to ensure consistency and integrity.<\/span>6<\/span> In the context of transaction processing, this means preserving the illusion that each transaction executes in isolation, a property known as serializability. The two dominant philosophical approaches to achieving this are pessimistic and optimistic concurrency control.<\/span><\/p>\n <\/p>\n <\/p>\n Pessimistic Concurrency Control (PCC) operates under the assumption that conflicts between transactions are a common occurrence and must be actively prevented.<\/span><\/p>\n <\/p>\n <\/p>\n Optimistic Concurrency Control (OCC) is founded on the opposite assumption: that conflicts between transactions are rare.<\/span>10<\/span> Instead of preventing conflicts with locks, it allows transactions to execute freely and only checks for conflicts at the very end, resolving them after the fact.<\/span><\/p>\n The decision between PCC and OCC can be viewed through an economic lens, as a trade-off based on the anticipated “cost of conflict.” PCC is akin to purchasing a comprehensive insurance policy. It requires paying a fixed, upfront premium\u2014the overhead of locking\u2014on every single transaction, regardless of whether a conflict was ever likely. This premium buys the certainty that no conflicts will occur. OCC, on the other hand, operates like a “pay-as-you-go” model with a deductible. It forgoes the upfront premium, but must pay a potentially high penalty\u2014the cost of an abort and re-execution\u2014whenever a conflict actually materializes.<\/span><\/p>\n When the conflict rate is low, the cumulative cost of these occasional penalties in OCC is far less than the cumulative cost of the mandatory premiums in PCC, making OCC the more efficient strategy. However, as the conflict rate rises, the frequency and total cost of OCC’s penalties can increase dramatically, eventually surpassing the cost of PCC’s steady premiums. This inflection point marks the onset of contention collapse. The central goal of an advanced optimistic system like Block-STM is to fundamentally alter this economic balance. It does so not by trying to prevent conflicts, but by dramatically reducing the <\/span>cost of the penalty<\/span><\/i> associated with an abort, thereby extending the viability of the optimistic approach into much higher-contention regimes.<\/span><\/p>\n The following table provides a comparative summary of these two fundamental approaches to concurrency control.<\/span><\/p>\n <\/p>\n <\/p>\n Block-STM is a state-of-the-art, in-memory parallel execution engine designed specifically for deterministic SMR systems like the Aptos blockchain.<\/span>17<\/span> It is built upon the principles of Software Transactional Memory (STM), a concurrency control paradigm that provides high-level abstractions to make parallel programming appear more like simple sequential execution.<\/span>19<\/span> However, Block-STM is not a general-purpose STM library; it is a highly specialized system that leverages unique properties of the blockchain use-case to achieve unprecedented performance.<\/span>1<\/span><\/p>\n <\/p>\n <\/p>\n The most profound innovation of Block-STM is its ability to transform a traditional constraint of blockchain systems into its greatest performance asset. Unlike general-purpose OCC or STM systems, which must dynamically discover a valid serializable order among concurrent transactions, Block-STM is given a block where the final serialization order is already determined by the proposer: $tx_1 < tx_2 <… < tx_n$.<\/span>1<\/span> In conventional thinking, this fixed order is a “curse” that constrains parallelism. Block-STM ingeniously inverts this, using the preset order as a global, unambiguous source of truth for dependency resolution, thereby turning the ordering curse into a performance blessing.<\/span>3<\/span><\/p>\n This preset order acts as an implicit, decentralized coordination mechanism, drastically reducing the need for explicit and costly synchronization primitives between threads. In a typical parallel system, if two threads contend for a resource, they must engage in an expensive runtime negotiation (e.g., atomic compare-and-swap, lock acquisition) to resolve the conflict. In Block-STM, the outcome of any conflict between $tx_i$ and $tx_j$ (where $i < j$) is pre-ordained: the effects of $tx_i$ must prevail. This deterministic rule is embedded directly into the engine’s core logic, allowing it to replace expensive, dynamic synchronization with cheap, predictable operations. It transforms a potentially chaotic race for state access into an orderly, pre-negotiated process, which is the foundational reason for its low overhead and remarkable scalability.<\/span><\/p>\n <\/p>\n <\/p>\n Block-STM’s architecture is a synthesis of established techniques and novel optimizations, all centered around the preset order.<\/span><\/p>\n <\/p>\n <\/p>\n To manage concurrent state access, Block-STM employs a multi-version data structure. This structure avoids crude write-write conflicts by allowing multiple versions of the same data location to coexist in memory.<\/span>3<\/span> When a transaction writes to a location, it creates a new version tagged with its unique identifier, which consists of its index in the block and its current “incarnation” number (since a transaction may be re-executed multiple times).<\/span>20<\/span><\/p>\n The preset order dictates a simple yet powerful rule for reads: when a transaction $tx_j$ needs to read a memory location, the data structure provides it with the value written by the transaction $tx_i$ with the highest index such that $i < j$.<\/span>3<\/span> This ensures that every read is deterministic and consistent with the final serial order, even while transactions are executing speculatively and out of sequence.<\/span><\/p>\n <\/p>\n <\/p>\n Worker threads in the system speculatively execute transactions in parallel, assuming no conflicts will occur.<\/span>3<\/span> Each execution of a transaction is termed an “incarnation”.<\/span>1<\/span> During an incarnation, the engine meticulously tracks all memory accesses:<\/span><\/p>\n After an incarnation completes, its write-set is applied to the multi-version data structure, and a validation task is scheduled. The validation process is the heart of conflict detection. It involves re-reading every location in the transaction’s read-set and comparing the currently visible version against the version originally recorded.<\/span>3<\/span> If all versions match, the validation succeeds, indicating that the transaction’s view of the world remains consistent. If a mismatch is found, it signifies that a transaction with a lower index has since been re-executed and produced a new version of the data. This constitutes a Read-Write conflict, causing the validation to fail and triggering an abort and subsequent re-execution of the current transaction.<\/span><\/p>\n <\/p>\n <\/p>\n Coordinating the execution and validation tasks across dozens of threads is a critical challenge. Naive approaches using standard concurrent data structures like priority queues are notoriously difficult to scale.<\/span>1<\/span> Block-STM introduces a novel, low-overhead collaborative scheduler that elegantly sidesteps this problem.<\/span>17<\/span> The scheduler prioritizes tasks associated with lower-indexed transactions, as their outcomes affect all subsequent transactions. Crucially, because the transactions are identified by a compact and bounded set of indices (from 1 to $n$), the scheduler can implement this prioritization using a few shared atomic counters instead of complex, lock-heavy data structures. This counting-based approach is a key optimization made possible only by the preset serialization order.<\/span>1<\/span><\/p>\n <\/p>\n <\/p>\n The single greatest threat to performance in an OCC system is a cascade of aborts, where the re-execution of one transaction triggers a chain reaction of validation failures in dependent transactions.<\/span>3<\/span> Block-STM’s most innovative feature for mitigating this is its dynamic dependency estimation mechanism.<\/span><\/p>\n When a transaction $tx_i$ fails validation and is aborted, its write-set is not merely discarded. Instead, the engine uses this information as a strong hint about where $tx_i$ is likely to write in its next incarnation. It marks every memory location in the aborted write-set with a special ESTIMATION flag in the multi-version data structure.<\/span>3<\/span> Later, if another transaction $tx_j$ attempts to read a location marked with this flag, it immediately knows that it has a potential dependency on the outcome of $tx_i$. Rather than proceeding with stale data and guaranteeing a future abort, $tx_j$ can pause its execution and wait for the dependency to be resolved.<\/span>3<\/span> This “just-in-time” dependency detection has two major advantages over pre-execution approaches that try to compute a full dependency graph upfront: (1) estimates are generated lazily and only when a conflict actually occurs, avoiding unnecessary overhead, and (2) the estimates are based on a more recent and therefore more accurate execution state.<\/span>17<\/span><\/p>\n <\/p>\n <\/p>\n Finally, Block-STM leverages the operational context of blockchains, where state updates are applied atomically at the block level. This allows the engine to forgo the expensive synchronization required for committing each transaction individually. Instead, it accumulates all state changes from successful transaction executions in the multi-version data structure. Only after all transactions in the block have been successfully executed and validated does the system perform a single, lazy commit of the entire block’s state changes. This is achieved efficiently using a “double-collect” technique managed by two atomic counters, minimizing synchronization to the very end of the process.<\/span>1<\/span><\/p>\n <\/p>\n <\/p>\n The performance of any optimistic concurrency control system is ultimately determined by its ability to manage conflicts and minimize the resulting aborts. While Block-STM’s architecture is designed to be robust, understanding the nature of conflicts and the strategies to mitigate them is crucial.<\/span><\/p>\n <\/p>\n <\/p>\n A conflict arises when two or more transactions access the same memory location, and at least one of these accesses is a write operation.<\/span>8<\/span> There are three canonical types of data conflicts <\/span>22<\/span>:<\/span><\/p>\n <\/p>\n <\/p>\n In Block-STM, a transaction is aborted and scheduled for re-execution when its validation fails. This occurs when the assumptions made during its speculative execution are proven false. The canonical scenario is an R\u2192W conflict that violates the preset serial order. For example, consider transaction $tx_j$. During its execution, it reads a value written by $tx_i$ (where $i < j$). Subsequently, $tx_i$ itself is aborted (due to a conflict with an even earlier transaction, $tx_k$) and is re-executed. In its new incarnation, $tx_i$ writes a <\/span>different<\/span><\/i> value to that same memory location. When $tx_j$’s validation task runs, it re-reads the location and discovers that the version it originally read is no longer the latest version produced by a transaction with an index less than $j$. This version mismatch signals a broken dependency, invalidates the entire execution of $tx_j$, and forces an abort.<\/span>3<\/span><\/p>\n <\/p>\n <\/p>\n The true performance risk is not a single abort, but a cascade of aborts. The re-execution of a single, low-indexed transaction can have far-reaching consequences. If $tx_1$ aborts, its new write-set might invalidate the read-sets of $tx_2$, $tx_5$, and $tx_{100}$, and any other transaction that read the values it originally wrote. When these dependent transactions are subsequently validated, they too will fail and be aborted. This chain reaction can lead to an enormous amount of wasted computation, potentially bringing the entire parallel execution process to a standstill. As noted in the Block-STM research, minimizing these cascades is “the name of the performance game” for any STM system.<\/span>3<\/span><\/p>\n <\/p>\n <\/p>\n Beyond Block-STM’s foundational dynamic dependency estimation, research has explored more granular and semantically aware strategies to reduce the high cost of aborts.<\/span><\/p>\n\n
II. Paradigms of Concurrency Control: Pessimism vs. Optimism<\/b><\/h2>\n
Pessimistic Concurrency Control (PCC): The “Ask for Permission” Approach<\/b><\/h3>\n
\n
Optimistic Concurrency Control (OCC): The “Ask for Forgiveness” Approach<\/b><\/h3>\n
\n
\n
\n
\n\n
\n Feature<\/span><\/td>\n Pessimistic Concurrency Control (PCC)<\/span><\/td>\n Optimistic Concurrency Control (OCC)<\/span><\/td>\n<\/tr>\n \n Core Assumption<\/b><\/td>\n Conflicts are likely and must be prevented.<\/span><\/td>\n Conflicts are rare and can be resolved after detection.<\/span><\/td>\n<\/tr>\n \n Primary Mechanism<\/b><\/td>\n Locking (e.g., Two-Phase Locking).<\/span><\/td>\n Read\/Validate\/Write phases with private workspaces.<\/span><\/td>\n<\/tr>\n \n Conflict Handling<\/b><\/td>\n Prevention: Transactions wait for locks to be released.<\/span><\/td>\n Detection & Resolution: Conflicting transactions are aborted and restarted.<\/span><\/td>\n<\/tr>\n \n Performance (Low Contention)<\/b><\/td>\n Sub-optimal due to constant locking overhead.<\/span><\/td>\n High throughput due to minimal coordination.<\/span><\/td>\n<\/tr>\n \n Performance (High Contention)<\/b><\/td>\n Degrades due to lock contention and long wait times.<\/span><\/td>\n Performance collapses due to high abort rates and wasted work.<\/span><\/td>\n<\/tr>\n \n Key Bottleneck<\/b><\/td>\n Lock manager, wait queues.<\/span><\/td>\n Validation phase, cost of re-execution.<\/span><\/td>\n<\/tr>\n \n Deadlock Risk<\/b><\/td>\n High; requires deadlock detection and resolution mechanisms.<\/span><\/td>\n None; deadlock-free by design.<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n III. Block-STM: Turning the Ordering Curse into a Performance Blessing<\/b><\/h2>\n
The Central Innovation: Leveraging the Preset Serialization Order<\/b><\/h3>\n
Core Components Deep Dive<\/b><\/h3>\n
Multi-Version Data Structure<\/b><\/h4>\n
Speculative Execution and Validation<\/b><\/h4>\n
\n
The Collaborative Scheduler<\/b><\/h4>\n
Dynamic Dependency Estimation<\/b><\/h4>\n
Lazy, Block-Level Commits<\/b><\/h4>\n
IV. Conflict Detection, Abort Rates, and Mitigation Strategies<\/b><\/h2>\n
Anatomy of a Transaction Conflict<\/b><\/h3>\n
\n
Primary Cause of Aborts: Validation Failure<\/b><\/h3>\n
The Critical Impact of Abort Cascades<\/b><\/h3>\n
Advanced Abort Reduction Techniques<\/b><\/h3>\n
\n