# NeuChain+: A Sharding Permissioned Blockchain System with Ordering-Free Consensus
## 5 Cross-Shard Transaction Processing Protocol
### Merging Reserve Table  
The reserve table is a crucial data structure for deterministic concurrency control, implemented using a hash table. After executing a transaction, the reserve table is updatedin the form of \(<\)_account_, _tid_\(>\). When multiple transactions access the same _account_, the reserve table will be updated according to the deterministic rule. This deterministic rule is expressed in detail below. As illustrated in Algorithm 2, whenever the new epoch \(n\) enters the execution phase, the read-write reserve table is first initialized (Lines 1-2) and the cross-shard read-write lists \(RL\) and \(WL\) implemented using dynamic arrays are initialized (Lines 3-4), used to cache the account involved in the cross-shard transactions. Subsequently, multiple parallel worker threads reserve the transactions executed in Section 4. The worker analyzes the transaction read-write sets to reserve, and the transaction with the minimum _tid_ in the reserve table is reserved according to deterministic rules (Lines 6-7, 10-11). Note that the accounts involved in cross-shard transactions need to be stored in the cross-shard read-write lists for _cross-reserve_ (Lines 8-9, 12-13). ```
1:The read-write set \(\{T.RS,T.WS\}\)
2:A complete reserve table containing accounts involved in cross-shard transactions
3:Initialize read reserve table \(RT\);
4:Initialize write reserve table \(WT\);
5:Initialize cross read list \(RL\);
6:Initialize cross write list \(WL\);
7:functionReserve(\(T\)) \(\triangleright\) After \(T\) completes execution
8:for\(w\in T.WS\)do
9:\(WT[w.key]=\min(WT[w.key],T.tid)\);
10:if\(T\) is cross-shard transaction then
11:\(WL.insert(w.key)\);
12:for\(r\in T.RS\)do
13:\(RT[r.key]=\min(RT[r.key],T.tid)\);
14:if\(T\) is cross-shard transaction then
15:\(RL.insert(r.key)\);
16:functionMergingSender() \(\triangleright\) After completing all intra-shard reservations
17:for\(key\in RL\)do
18:\(batch.RT.insert(<key,RT[key]>)\);
19:for\(key\in WL\)do
20:\(batch.WT.insert(<key,WT[key]>)\);
21: Broadcast \(batch\) to all other shard;
22:functionMergingReceiver()
23:if receive the same \(batch\) of a shard over \(f+1\)then
24:for\(r\in batch.RT\)do
25:\(RT[r.key]=r.value\);
26:for\(w\in batch.WT\)do
27:\(WT[w.key]=w.value\);
```  
**Algorithm 2** Merging reserve table based on deterministic execution. Although the execution results of cross-shard transactions are deterministic from a global perspective, from the perspective of a block server, it cannot be determined whether the cross-shard transactions can be reserved in other shards. We enable the block server to hold a complete reserve table containing accounts involved in cross-shard transactions by merging reserve tables. This allows block servers among different shards to deterministically commit or abort cross-shard transactions through concurrency control (detailed in Section 5.2). We describe the merging reserve table in detail below. After completion of the execution of transactions in the current _epoch_, package the rows in the reserve table corresponding to the accounts in a batch and broadcast it to all other shards (Lines 14-19). After receiving \(f+1\) of the same batches from other shards, the accounts involved in cross-shard transactions from remote shards are cached in the local reserve table (Lines 20-25). Since the accounts among shards do not overlap, the keyscorresponding to the accounts involved in transactions from other shards in the reserve table of this shard must be empty, so there is no need to judge whether to reserve them based on deterministic rules. It is not difficult to find that there is cross-shard communication during merging reserve tables, but this is different from the coordination of 2 PC. 2 PC needs to make decisions through coordination between shards, and decision making means the need for expensive intrashard consensus. Whether cross-shard transactions in NeuChain+ can be committed is deterministic without decision making. Therefore, it only needs a simple exchange of results.