🏁
Concurrent Programming Guide
  • Welcome
  • Overview
  • data structure
    • Cumulative Integer
    • Base
    • Arrays
    • Ordered Maps
  • utility
    • Multiprocessor
    • Runtime
    • Storage
  • Examples
    • Contract Examples
Powered by GitBook
On this page
  • Design Goal
  • Key Features
  • Conflict Model
  • Usage
  • Example: Concurrent Like
  • Example: Vending Machine
  • Conflict Analysis
  • Conflict Example
  • Parallelized Version
  • Conflict Free Execution
  1. data structure

Cumulative Integer

Concurrent Delta Friendly Data Types

In optimistic parallel processing, a fundamental assumption is that multiple transactions will not touch the same state. If they do, a conflict occurs, and the transactions will be reverted to protect state consistency. However, 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. This creates a serious bottleneck that requires special handling.

Design Goal

Cumulative variables are specifically designed to address concurrent counting. A cumulative variable allows multiple transactions to add their updates to the same variable without causing conflicts or reversions. Once initialized, a cumulative variable only accepts delta updates.

A cumulative variable has an internal buffer to store all delta updates and applies them only after the current generation of transactions has been executed. With this property, multiple transactions can add delta changes to the buffer first, instead of applying them immediately. 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 block 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.

Note: Arcology's parallel execution model is centered around preserving commutativity, any TX that violate the rule will be reverted.

Usage

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.

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

Example: Concurrent Like

The contracts below define a simple counter that tracks how many times the like() function is called. Each call increments the likes count by 1. In the original implementation, when called in parallel, the line likes += 1; is a read-modify-write operation on shared state (likes), which causes conflicts if multiple transactions try to call like() in parallel.

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

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

contract Like {
    uint public likes;

    function like() public {
        likes += 1;
    }
    
   function get() public view returns(uint256){
        return likes;
    }        
}
// SPDX-License-Identifier: GPL-3.0
pragma solidity >=0.8.0 <0.9.0;
import "@arcologynetwork/concurrentlib/lib/commutative/U256Cum.sol";

contract Like {
    U256Cumulative likes = new U256Cumulative(0, type(uint256).max);

    function like() public {
        likes.add(1);
    }
    
    function get() public view returns(uint256){
        return likes.get();
    }        
}

Calling the Parallelized Version

In the diagram below, three users, Alice, Bob, Charlie, each submit a transaction (TX 0, TX 1 and TX2) that calls the function like() and get().

1

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

2

Charlie (TX 2) calls get(), which reads the current value of the like counter. But it reads the aggregate value of like. If TX 2 executes:

  • Before TX 0 and TX 1 → it sees 0

  • After one → it sees 1

  • After both → it sees 2

Thus, TX 2 (get()) does not commute with the writes. This violates Arcology’s commutativity-based conflict model, that requires the final result must be the same regardless of execution order.

3

Arcology's conflict detector identifies this read-write conflict after execution. To preserve correctness and determinism, the system reverts TX 2. TX 0 and TX 1 proceed and produce a final like count of 2.

Note: the scheduler learns from this conflict pattern. In future blocks, it will automatically place transactions that call non-commutative functions into separate generations to prevent the same conflict from reoccurring.

Example: Vending Machine

pragma solidity >=0.8.0 <0.9.0;

contract VendingMachine {
    // Declare state variables of the contract
    address public owner;
    mapping (address => uint) public cupcakeBalances;

    // When 'VendingMachine' contract is deployed:
    // 1. set the deploying address as the owner of the contract
    // 2. set the deployed smart contract's cupcake balance to 100
    constructor() {
        owner = msg.sender;
        cupcakeBalances[address(this)] = 100;
    }

    // Allow the owner to increase the smart contract's cupcake balance
    function refill(uint amount) public {
        require(msg.sender == owner, "Only the owner can refill.");
        cupcakeBalances[address(this)] += amount;
    }

    // Allow anyone to purchase cupcakes
    function purchase(uint amount) public payable {
        require(msg.value >= amount * 1 ether, "You must pay at least 1 ETH per cupcake");
        require(cupcakeBalances[address(this)] >= amount, "Not enough cupcakes in stock to complete this purchase");
        cupcakeBalances[address(this)] -= amount;
        cupcakeBalances[msg.sender] += amount;
    }
}

The refill() function allows the contract owner to increase the cupcake inventory. It checks that the caller is the owner and then adds the specified amount to the contract’s cupcake balance.

The purchase() function allows anyone to buy cupcakes by sending ETH. It verifies that the buyer has sent enough ETH (1 ETH per cupcake) and that the contract has enough cupcakes in stock. If both conditions are met, it deducts the requested amount from the contract’s balance and adds the corresponding amount to the buyer’s balance.

Conflict Analysis

Below is a table highlighting potential conflicts when the same or different functions are called simultaneously. We can conclude that since these functions modify the same variable concurrently, transactions calling to refill() and/or purchase() cannot be processed in parallel.

Function Pair
Variable(s) Modified
Conflict Type

refill() / refill()

cupcakeBalances[address(this)]

Two concurrent refills modify the inventory simultaneously

refill() / purchase()

cupcakeBalances[address(this)]

Refill and purchase modify the sender's balance and the inventory.

purchase() / purchase()

cupcakeBalances[address(this)] cupcakeBalances[msg.sender]

Two concurrent purchases modify the sender's balance and the inventory.

Conflict Example

Let's say there are two transactions calling refill(10) and purchase(5). The refill transaction will add 10 cupcakes to the contracts inventory by executing cupcakeBalances[address(this)] += 10, while the purchase transaction is try to move 5 cakes from contract's inventory to user's account.

1

System tries to run the transactions in full parallel.

2

Transactions read and write the same memory slot; the conflict detector will detect a write-write conflict after execution. One transaction is rolled back.

3

Only the surviving one proceeds.

4

Parallelized Version

Upon examining the cupcakeBalances mapping, we can immediately see that these variables are never directly modified. Instead, they apply a difference—a delta value—to the original balance, either by adding or subtracting an amount. There is no read involved, meaning the final state isn't needed immediately. This makes it a perfect use case for cumulative variables. In the parallelized version:

  • We replaced the original uint used in cupcakeBalances mapping with a cumulative u256 provided by Arcology's concurrent library.

pragma solidity >=0.8.0 <0.9.0;

import "@arcologynetwork/concurrentlib/lib/commutative/U256Cum.sol";

contract VendingMachine {
    address public owner;
    mapping (address => U256Cum) public cupcakeBalances; // Use U256Cum instead

    constructor() {
        owner = msg.sender;
        U256Cum balance = new U256Cum(0, type(uint256).max); // Initialize the variable
        balance.add(100); // set the initial cupcake balance to 100
        cupcakeBalances[address(this)] = balance;
    }

    // Allow the owner to increase the smart contract's cupcake balance
    function refill(uint amount) public {
        require(msg.sender == owner, "Only the owner can refill.");
        cupcakeBalances[address(this)].add(amount);
    }

    // Allow anyone to purchase cupcakes
    function purchase(uint amount) public payable {
        require(msg.value >= amount * 1 ether, "You must pay at least 1 ETH per cupcake");
        cupcakeBalances[address(this)].sub(amount);
        cupcakeBalances[msg.sender].add(amount);
    }
}

Conflict Free Execution

Let's rerun two transactions calling refill(10) and purchase(5). The refill transaction will add 10 cupcakes to the contracts inventory by executing cupcakeBalances[address(this)].add(10), while the purchase transaction is try to move 5 cakes from contract's inventory to user's account.

1

System tries to run the transactions in full parallel.

2

Transactions read and write the same concurrent variable that is commutative and associate. There is no conflict. Both transactions will through.

3

Alice successfully fill the inventory and Bob gets his cakes.

PreviousOverviewNextBase

Last updated 1 month ago

The contains a concurrent variable that supports concurrent addition and subtraction. It has both minimum and maximum bounds and allows concurrent delta changes. It is conceptionally similar to an atomic integer but with some major constraints.

To better understand how cumulative variables work, consider the following example from the . The VendingMachine contract allows the owner to manage and sell cupcakes. It tracks the contract’s cupcake inventory and individual buyer balances. The owner can refill the inventory, and buyers can purchase cupcakes by sending 1 ETH per cupcake.

Scheduler will learn the conflict patten and avoiding putting transactions calling these conflict functions in the same in the future.

We removed the line cupcakeBalances[address(this)] >= amount. It is unnecessary because U256Cum enforces bounds internally at commit time after each . If a sub(amount) causes the value to fall below its lower limit, the transaction will be automatically reverted after execution.

U256Cum contract
Ethereum developers docs
generation
generation