Conflict Detector

A fine-grained concurrency model based on EVM-compatible storage slot tracking.

In Arcology's parallel execution environment, a conflict refers to a situation where multiple transactions attempt to access and modify the same shared resources concurrently. The conflict detection mechanism identifies and addresses such conflicts to ensure data consistency and integrity. The final goal is to ensure that operations on shared resources are performed in a way that maintains data integrity and consistency.

In the Ethereum Virtual Machine (EVM), there are two types of variables:

• Memory: Memory variables within a smart contract are specific to each individual transaction, remaining isolated, private, and not shared across different transactions.

• Storage: Storage variables are shared among transactions and are stored on the blockchain as part of the contract's state. Conflicts can arise when multiple transactions attempt to modify the same storage variable simultaneously.

Arcology's concurrency control specially deal with the storage variable. Arcology's concurrency control mechanism specially deals with the storage only.

Granularity

In the EVM storage, a slot is the smallest data unit. Each storage slot can hold 256 bits or 32 bytes of data. Smart contracts use these slots to store and manage their state variables, which are the persistent data that the contract maintains. Contracts can read from and write to individual storage slots.

Arcology's concurrency control operates at the slot level, tracking data access right down to individual storage slots. A slot-level concurrency control design offers several advantages:

• Simplicity: Storage slots provide a clear and consistent unit of data storage within a smart contract. Concurrency control mechanisms operating at this granularity are straightforward to implement and reason about.

• Minimized Overhead: As storage slots are a fundamental storage unit in Ethereum, a slot-level concurrency control design fits well with the underlying architecture of the EVM and blockchain. The granularity of storage slots allows for efficient conflict detection and resolution, minimizing the overhead associated with managing concurrent transactions.

• EVM Compatibility: Ethereum's EVM is built around the concept of storage slots, making it align with the platform's design. Developers and users can expect a consistent and predictable behavior when it comes to managing shared resources within smart contracts.

---

Detection Mechanism

The conflict detection module analyzes the contents of the RW sets from different transactions that are executing concurrently. It examines whether there are any conflicting accesses to the same data locations. This detection process helps identify if two or more transactions are attempting to modify the same data concurrently, which could result in a conflict.

Two transactions are

Access Types

A "state access" refers to a specific action that a transaction performs on the data items stored in the StateDB. Operations are used to interact with the data, retrieve information or make changes. Each operation corresponds to a certain type of interaction with the data, and the Arcology processes these operations to manage the underlying database efficiently and maintain data integrity.

The concurrency control system monitors three types of state accesses during transaction processing:

• Read: The read operation retrieves data from the database without making any changes to it. Read operations provide information to the user or application and are essential for querying the StateDB.

• Write: In Arcology's concurrent execution design, a write operation refers to an action where a transaction modifies the value of a data. The write operations involve updating data to reflect new information or changes made by the transaction.

• Delta Write: A delta write refers to a type of modification that is the difference between the new value and the original value.

Why Delta Writes

There are some key differences between the "write" and "delta write" operation:

• Data Update: A write operation replaces the original data with the new data, while a "delta write" records the change that needs to be applied to the original data.

• Immediate vs. Deferred Update: A write operation immediately updates the data, while a delta write defers the update until a read operation is performed, or the transaction is committed.

• Read Overhead: Delta writes can introduce computational overhead during read operations because the delta changes need to be applied before providing the data to the user. Writes don't have this additional overhead during reads.

Arcology supports delta-write on commutative variables only. In Arcology, a commutative variable refers to a type of thread-safe data that supports commutative operations. Commutative operations are those that can be applied in any order without changing the final outcome. Please refer to concurrent API document for more details.

Rules

The conflict detector relies on a set of predefined rules to analyze these RW sets and determines whether conflicts have occurred. It determines conflict status based on the following possible scenarios.

The conflict detection is based on the following access rules:

                +------------+-------+-------+-------------+
                | Operation  | Read  | Write | Delta Write |
                +------------+-------+-------+-------------+
                | Read       |   ✓   |   X   |      X      |
                +------------+-------+-------+-------------+
                | Write      |   X   |   X   |      X      |
                +------------+-------+-------+-------------+
                | Delta Write|   X   |   X   |      ✓      |
                +------------+-------+-------+-------------+

• Read-Read: Read operations do not modify data and can occur concurrently without affecting each other. Therefore, no conflict occurs between two read operations from different transactions.

• Read-Write: A conflict occurs if a read operation from one transaction overlaps with a write operation from another transaction.

• Read-DeltaWrite: It needs to apply the pending changes first, which effectively converts it into a write operation before evaluating conflicts with read or write operations. It conflicts with both read and write operations from other transactions, just like a regular write operation would.

• Write-Write: A conflict occurs if two transactions attempt to write to the same data item concurrently. Only one of the transactions should be allowed to commit its write, while the other might need to wait or be aborted.

• Write-DeltaWrite: A conflict occurs if a write operation from one transaction. Since the order in which the write and delta write are applied might impact the final value of the data item.

• DeltaWrite-DeltaWrite: Delta write operations from different transactions generally do not result in conflicts. They can be applied independently without directly modifying the original data until they are read or committed.

For a list of variable types supporting DeltaWrite operation please refer to the API document.

Conflict Resolution

Conflicts are detected during the validation phase, which occurs after the execution of a generation but before committing. If conflicts are found, one or more transactions may need to be rolled back and re-executed to maintain state consistency. Only the state transitions produced by conflict-free transactions have a chance to be committed.

Scheduler Feedback

The detector also captures conflicting information related to past transaction interactions. This conflict history is used by the transaction scheduling module to make informed decisions about concurrent execution. By learning from past conflicts, the system can optimize scheduling to reduce contention, improve throughput, and minimize rollbacks.

At the end of each block cycle, the scheduler will update its internal conflict database based on conflict information detected by the feedback from the Arbitrator. If two different smart contracts are found conflicting with another, the scheduler will avoid putting them in a same generation in a future cycle.

---

Example

Now, let's assume the following contract were deployed on the Arcology Network, and two users, Alice and Bob, each sent a transaction to call the like() function. The variable likes had an initial value of 0.

// SPDX-License-Identifier: GPL-3.0
pragma solidity >=0.8.0 <0.9.0;

contract Like {
    uint public likes;

    function like() public {
        likes += 1;
    }    
}

The Scheduler will send the two transactions to two Execution Unit (EU) instances to be processed independently.

Each EU will execute the transaction in isolation and maintain its own Read/Write (RW) Set, capturing access to the likes variable during the execution. After both transactions are executed, their RW Sets are sent to the Conflict Detector.

Since both Alice and Bob's transactions read and write to the same variable (likes), a write-write conflict is detected by the Conflict Detector. To maintain deterministic state consistency, only one transaction is allowed to commit.

In this case, Bob’s transaction will be reverted, as it conflicts with Alice’s and cannot be safely merged. This ensures the final state remains deterministic and reproducible across all nodes — with likes increased by 1, not 2.