Cumulative Integer

Concurrent Delta Friendly Data Types

It is a common use case in many contracts to keep track of some form of cumulative values, such as counters, total supply, and similar metrics. There global variables are serious bottlenecks for parallel execution.

The U256Cum contract contains a concurrent variable that supports concurrent addition and subtraction. A cumulative variable allows multiple transactions to add their updates to the same variable without causing conflicts or reversions. It has both minimum and maximum bounds and once initialized, a cumulative variable accepts delta updates only.

Applications

A typical application is implementing numerical variables that need to be incremented or decremented by multiple transactions. Examples include counters, tallies, total supply, or any situation where a count needs to be updated frequently and concurrently.

Mechanism

A cumulative variable has an internal buffer to store all concurrent delta updates and applies them only after all the transactions in the current parallel batch have been executed. Because these delta changes are both cumulative and commutative, the order in which they are added does not affect the final result.

Key Features

A cumulative variable has the following features:

  • Initialized once with a value of 0

  • Commutative and associative; accepts only delta changes

  • Supports upper and lower bounds to prevent over/underflow

  • Concurrent updates do not conflict

  • Applies deltas lazily after each parallel batch or on read

Conflict Model

Transactions with out-of-limit delta changes will fail, ensuring that the variable remains within its prescribed bounds. Attempting to invoke timing-dependent operations, such as read(), on the variable while it is being updated by other threads will result in a rollback of all but one transaction.

Examples

To better understand how cumulative variables work, consider the following examples:

Concurrent Counter

The contracts define a simple counter that tracks how many times the add() function is called. Each call increments the total by 1.

In the original implementation, when add() is called in parallel, is a concurrent write operation on shared state (total), which causes conflicts.

We can replace Like counter using Arcology’s U256Cumulative, with a lower bound of 0 and higher bound of uint256's maximum value. It is a thread-safe, deterministic data structure. When like() is called in parallel, it adds the delta value to its internal buffer, rather than directly updating the final state.

// SPDX-License-Identifier: GPL-3.0
pragma solidity >=0.8.0;
import "@arcologynetwork/concurrentlib/lib/commutative/U256Cum.sol";

contract Counter{
    U256Cumulative total = new U256Cumulative(0, type(uint256).max);

    function add() public {
        total.add(1);
    }     
}

In the diagram below, two users, Alice and Bob, each submit a transaction (TX 0 and TX 1 ) that calls the function add().

1

Alice (TX 0) and Bob (TX 1) both call add(), which increments a shared cumulative integer. These operations are commutative and associative, so they can be safely executed in parallel.

2

Both increments are stored temporarily in a buffer associated with the variable.

3

Arcology's conflict detector finds no underflow or overflow from the delta values. The system proceeds with committing TX 0 and TX 1 to the StateDB to produce the final value of 2.

Last updated