Parallel Execution using static contract dependencies
|Title||Parallel Execution using static contract dependencies|
This RSKIP describes how transactions should be processed in order to be safely parallelized. This RSKIP requires RSKIP02 (Dynamic Contract Dependency) to be deployed.
RSK processes transactions from blocks one by one, in the specified order. This is because the effect of two random transactions can differ if applied in different orders. However most transactions do not use the same Accounts/Contracts and therefore they could be parallelized without interference.
There are several obstacles to parallelization. RSKIP02 allows contracts to specify dynamic dependencies. Therefore it is possible to partition the transactions into disjoint sets.
The transaction partitioning could be made deterministic if contract relations were to be defined prior execution. Two new opcodes are proposed in order to define and undefine such relations. The effect of change in a relation only applies in the next block. Therefore contracts can still communicate with any other contract providing those contracts register callback addresses before the callback addresses are actually called.
Prior execution, transactions are partitioned in dependency disjoint sets. This partition is based on a deterministic flood fill coloring algorithm. The algorithm is the following:
Set CurrentColor to zero. All transactions begin unassigned.
Start with the first unassigned transaction.
Take the source account/contract and color it with CurrentColor. Explore recursively all dependencies (dependent contracts must be also explored) and color them all with CurrentColor.
Take the destination account/contract and color it with CurrentColor explore recursively all dependencies and color them all with CurrentColor.
The main problem with this algorithm is: how to reduce the computations required for recursive coloring? One possibility is that dependencies are stored in Set data structures that allow fast join operation.
We use a Treap data structure.
Every contract stores the dependencies in a treap.
Every time we visit a contract, we visit all chids, and build treaps for them, and then we create the union of every child treaps. If we arrive at a already visited contract, we skip it but we return the reference of this contract in a resulting RefTreap structure. This is to track recursive references.
Add the treap to an ordered tree of treaps, where the key is the treap size. We also reference this resulting treap by the contract itself, to To minimize treap union time, we begin with the smaller treaps, join them, and put them back into the tree of treaps, ordered by size.
We repeat this process until a single treap is in the root.
Copyright and related rights waived via CC0.