State Conflict Detection & Resolution

Restoring State Consistency

In Arcology, 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.

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.

Conflict

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, potentially leading to unintended or unpredictable outcomes. The conflict detection mechanism identifies and addresses such conflicts to ensure data consistency and integrity.

Rules

The conflict Judgement 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.

Steps

The detector relies on the read/write counter instead to efficiently determine whether multiple transactions have modified the same variable, indicating a potential conflict. This approach minimizes the need for direct value comparison while still achieving accurate conflict detection and resolution. The steps are listed below:

• Grouping Variables: Group variables using the slot ID.

• Read-Write Interactions: Look for variables with both read and write operations. The "Number of Read Operations" and "Number of Write Operations" fields will indicate these interactions.

• Write Counter: Use the "Number of Write Operations" field to track the number of write operations on a variable. The write counter essentially tells you how many transactions have written to the variable.

• Transaction IDs: Analyze the "Transaction IDs" field to identify which transactions accessed the same variables. If multiple transactions have accessed the same variable, and the write counter is greater than one, it indicates a potential conflict.

• Conflict Resolution: When conflicts are identified, consider the order of transactions and their write counters to determine the order in which transactions are applied to the state. This helps resolve conflicts and maintain data consistency.

Conflict Resolution

It's essential to have mechanisms in place to determine how conflicts are handled. Arcology's concurrency framework ensures that the final outcome of concurrent transactions maintains data integrity and consistency.

Conflicts are detected during validation before committing. If conflicts are found, one or more transactions might need to be rolled back and re-executed to maintain the state consistency. Only the transitions generated by conflict-free transactions have the chances to finally commit the changes.