# A Coordination Technique for Improving Scalability of Byzantine Fault-Tolerant Consensus
## 3 A Coordination Technique for Scalable BFT Consensus
### Step 3. Processing Equal/Unequal Transactions
#### 3.3.2 Step 3.2 Handling Unequal Transactions  
This step is executed by the coordinator when some of the transactions are not equal. This step is composed of three sub-steps: (1) classifying transactions; (2) executing a consensus algorithm; and (3) sorting all transactions.  
_(1) Classifying Transactions:_ In this step, the coordinator classifies all transactions into _common_ transactions and uncommon transactions throughout all transactions from each node. For uncommon transactions, we rename them as _trouble_ transactions. Algorithm 4 shows the classification step. The output of the classification is stored in \(List_{comm}\) and \(List_{tr}\). The classification step is very intuitive. With the boolean flag _isCommon_, it iterates all transactions of each node and checks if a transaction exists in their transaction lists (see Lines 3-18).  
```
1:Inputs:\(Txs=\{Txs_{0},Txs_{1},...Txs_{n}\}\)
2:Initialize:\(List_{comm}\leftarrow\{\}\), \(List_{tr}\leftarrow\{\}\), \(List_{agg}\leftarrow\{\}\)
3:for\(i\)=0, \(i\leq N(Node)\), \(i\)++do
4:for\(j\)=0, \(j\leq N(Tx_{i})\),\(j\)++do
5:\(isCommon\leftarrow\)\(true\)
6:for\(k\)=0, \(k\leq N(Node)\) & \(i\
eq k\), \(k\)++do
7:if\(Tx_{j}\) does not exist in \(Txs_{k}\)then
8:\(isCommon\leftarrow false\)
9:break
10:endif
11:endfor
12:if\(isCommon==true\)then
13:\(List_{comm}\gets Tx_{j}\)
14:else
15:\(List_{tr}\gets Tx_{j}\)
16:endif
17:endfor
18:endfor
19:\(List_{agg}\leftarrow\)request\(Node_{prime}\) to execute a Consensus Algorithm(\(List_{tr}\))
```  
**Algorithm 4** [_Coordinator_] Classifying Transactions  
_(2) Executing a Consensus Algorithm:_ For trouble transactions, \(List_{tr}\) from the previous sub-step, the coordinator requests the prime node to execute a consensus algorithm and obtains a list of agreed transactions \(List_{agg}\) from the prime node, denoted on Line 19 Algorithm 4. It should be noted that any BFT-based consensus algorithms can be applied in this step. All transactions in \(List_{tr}\) cannot be contained in \(List_{agg}\), because some of the transactions might not be completed in the consensus algorithm. At that time, transactions not agreed upon are removed according to the BFT-based consensus algorithm.  
_(3) Sorting All Transactions:_ Based on common transactions \(List_{comm}\) and agreed transactions \(List_{agg}\), the coordinator merges and sorts them in time order in this step. Then, the coordinator requests the prime node to confirm merged transactions similar to the process of equal transactions (see Algorithm 5, Line 5). The \(sig^{\prime\prime}_{prime}\) is produced by the prime node using \(Signature(SortedList_{csn})_{sk_{prime}}\). If transactions are confirmed, the coordinator requests all nodes to generate a new block with the \(SortedList_{csn}\), and all nodes' \(time_{p}\) is updated by the current time \(time_{c}\).  
```
1:Inputs:\(List_{comm},List_{agg}\)
2:Initialize:\(List_{csn}\leftarrow\{\}\), \(SortedList_{csn}\leftarrow\{\}\)
3:\(List_{csn}\leftarrow(List_{comm}\cup List_{agg})\)
4:\(SortedList_{csn}\leftarrow\) sort (\(List_{csn}\))
5:\(isConfirmed\), \(sig^{\prime\prime}_{prime}\), \(pk_{prime}\leftarrow\) request\(Node_{prime}\) to confirm \(SortedList_{csn}\)
6:if\(isConfirmed==true\)then
7: request All Nodes to generate a new block with \(SortedList_{csn}\) and \(sig^{\prime\prime}_{prime}\)
8:\(time_{p}\gets time_{c}\)
9:else
10: Terminate
11:endif
```  
**Algorithm 5** [_Coordinator_] Sorting the Merged Transactions