Base
Foundation of All Concurrency Data Structures
Last updated
Foundation of All Concurrency Data Structures
Last updated
When it comes to parallel processing, Solidity’s built-in data structures don’t provide the execution commutativity and state consistency guarantees that Arcology requires.
Arcology's concurrent containers are lockless data structures specifically designed to handle concurrent data manipulation, and they are different from native data structures in a number of ways:
Execution commutativity and state consistency are always guaranteed.
Any violation of the commutativity guarantee triggers conflicts and reversions.
The containers are managed by the Arcology's concurrent framework, not the EVM.
They can only be accessed through the concurrent APIs.
Their behaviors under concurrent environments are strictly defined.
Under the hood, Arcology’s concurrent containers are implemented as an ordered map, where each element is stored as a key-value pair that can be accessed by both key and index.
Arcology’s concurrent containers allow multiple transactions to add or remove elements in parallel without immediate coordination. During execution, each transaction operates in isolation and records its intended changes—new elements are marked as pending appends, and deletions are marked as pending removals.
As shown in the "Before Commit" diagram, these updates are not immediately reflected in the shared array. Instead, they remain in a temporary state until all transactions in the generation complete. At that point, the system performs conflict detection and resolves any overlapping operations.
In the "After Commit" phase, pending appends are deterministically ordered and merged into the array, while valid removals are finalized. At this point, both the pending appended and removal sets are empty. This design ensures that parallel modifications are commutative, conflict-resilient, and merged without rollback, enabling scalable and deterministic state transitions.
The Base container is the foundation of all concurrent containers, designed to accommodate the varying requirements of different container types. As a result, it has some unique properties that differ from conventional data structures.
In Arcology’s concurrent execution model, committedLength() is thread-safe because it reflects the number of finalized elements from previous generations. This value is consistent across all execution units (EUs), making it safe to use for deterministic, index-based reads. Any operation based on this length observes a globally agreed-upon boundary, preserving commutativity and ensuring that no conflicts or rollbacks occur during parallel execution.
In contrast, speculative length functions like fullLength() and nonNilCount() depend on the aggregated state produced by all transactions running in complete isolation—something each transaction has no visibility into until the generation concludes. While reading the speculative length itself may not cause a conflict (assuming all transactions are conflict-free), using that length for index-based access is unsafe. Even if every job successfully commits, the relative ordering of newly inserted elements is not determined until after the generation is resolved. As a result, index-based access into speculative space assumes a structure that does not yet exist, violating commutativity.
Unless you are certain that you are the only one accessing the container during the current generation, index-based reads using speculative lengths are unsafe and should be avoided. Doing so risks introducing subtle, non-deterministic behavior that can lead to conflicts, rollbacks during parallel execution.
In Arcology, all concurrent containers are inherited from an ordered map implementation in the , where each element is stored as a key-value pair. This structure enables parallel-safe updates, fine-grained conflict detection, and sparse indexing.
