## 3 Scalable Dynamic Multi-Agent Byzantine Consensus
### Process
#### 3.2.1 Process in Pre-Prepare Stage
The detailed algorithm is presented as Algorithm 2. ```
0:\(n\) consensus nodes, client \(c\), the size of the area \(k\), identification of all nodes
0: minimum spanning tree for agents
1:begin
2: client \(c\) sends a message to the \(k\) neighbor nodes;
3: set the client as the root;
4:for (\(i=1\); \(i\leq\) k, \(i++\)) // \(k\) area
5:if node \(i\) receives the message
6: set node \(i\) as agent;
7: set \(flag=1\) and the layer as the current layer;
8: agent sends \(k\) messages to \(k\);
9:while agent cannot find \(k-1\) nodes
10: The \(k-1\) nodes will be the leaf nodes;
11:else call line 4;
12:until there are no consensus nodes;
13:endwhile
14:if a new node enters the system
15: put the node into the nearest area as a leaf node;
16:endif
17:endif
18:endfor
19:end
```

**Algorithm 2**Spanning tree generation algorithm. #### 3.2.2 Process in the Reply Stage

The final step of the algorithm is to return the execution results of all the nodes to the client. The client determines whether the block is written on the chain according to the number of messages that are sent and the number of messages that are recovered. Therefore, the recovery mechanism and counting mechanism of the information request are very important. PBFT allows the system to have \([n-1]/3\) non-faulty nodes, and its fault-tolerance rate is \(1/3\). In the implementation process, the recycling of the nodes is divided into two steps. First, the internal voting results of an area are returned to the agent. Second, the agent will return the votes inside the area to the client. The agent must record the amount of internal information to return. We assume that if a node agrees to accept the message, the message is sent to the agent. If the node is

Figure 4: Spanning tree that is generated for multicasting. a non-loyal node or there is a software error or communication timeout, the node does not agree to accept. In the commit phase, there two types of commit messages, namely, committed-local(_m,v,n,i_) and committed(_m,v,n,i,a_), where \(m\) is the client's request message, \(v\) is the current view number, \(n\) is the sequence number, and \(a\) is the agent in an area. The process of committed-local (_m,v,n,i_) is conducted in an area. Then, the agent will calculate statistics of the voting situation and return the results to the client through the process of committed (_m,v,n,i,a_). According to the total number of multicast requests and the total number of received consent messages, the blockchain system can confirm whether the request is received or not. The reply process of the SDMA-PBFT algorithm is illustrated in Figure 5.

### Traffic Analysis for SDMA-PBFT

Assume that the total number of consensus nodes in a blockchain system is \(n\) and the number in an area is \(k\). In the worst case, each layer has a complete child node and the blockchain consensus nodes constitute a fully branched tree with k nodes. In an asynchronous environment, the number of messages sent can be calculated as follows:

layer 1



\[\text{Total (area)}=\text{area (layer}_{3})+\text{area (layer}_{2})+\text{area (layer}_{1})=k^{3}+k^{2}+k \tag{9}\]

\[\text{Total (Number)}=\text{Total (area)}\times k=k^{4}+k^{3}+k^{2} \tag{10}\]

Through the above reasoning, we conclude the following:

\[\text{Total (area}_{i})=\text{area (layer}_{i})+\text{Total (area}_{i-1}) \tag{11}\]

\[\text{Total (Number}_{i})=\text{Total (area}_{i})\times k \tag{12}\]

First, we assume that \(k\) is 4 and that the size of the message in an area is \(k^{2}\). When \(k=4\) and the system has three layers with a full \(k\)-branched tree, the number of nodes in the area in the system is 84 and the total number of nodes in the system is 336. The size of the sent message in the system is 84 \(\times\) 4\({}^{2}\) = 1344. If the system is not divided into layers, the total size of the message is approximately 336\({}^{2}\) = 112,896, which is approximately 84 times larger than in SDMA-PBFT. If the total number of nodes in the system is fixed, other results will be observed as \(k\) is increased.