# Distributed Average Consensus Algorithms in d-Regular Bipartite Graphs: Comparative Study
## 3 Theoretical Background
### Examined Distributed Consensus Algorithms  
In this subsection, we introduce seven distributed consensus algorithms (also referred to as weights) chosen for evaluation in \(d\)-regular bipartite graphs. The selection of these algorithms is justified by the fact that they have probably been the most frequently quoted algorithms in their category over the past decades. The first examined algorithm is MD, which is frequently applied and has easily implementable weights with the Perron matrix [81]. Thus, all its non-diagonal entries are equal to either zero or the mixing parameter \(\epsilon\) (i.e., the inverted value of the maximum degree of a graph \(\Delta\) in this case). Mathematically, their weight matrix **W** can be, thus, expressed as follows:  
\[[W]_{ij}= \begin{cases}\frac{1}{\Delta},&\text{if }e_{ij}\in\textbf{E}\\ 1-\frac{d_{i}}{\Delta},&\text{if }i=j\\ 0,&\text{otherwise}\end{cases}  \tag{12}\]  
As identified in our previous manuscript [52], both the largest \(\lambda_{1}(\textbf{W})\) and the smallest eigenvalue \(\lambda_{n}(\textbf{W})\) of the weight matrix **W** are always located on the unit circle in \(d\)-regular bipartite graphs if (12) is applied. Furthermore, it is mathematically proven in our previous paper that all the other eigenvalues of the weight matrix **W**, except for the two previously mentioned ones, are situated inside the unit circle. These facts cause the algorithm to diverge (as the third convergence condition is broken) in such a way that the values of the inner states oscillate between two values (more specifically, between values approaching the averaged initial inner states of the agents forming both the disjointed subsets). Further details about the divergence of MD in regular bipartite graphs can be found in the mentioned manuscript. In Figure 6, we depict the evolution of the inner state of one of the agents forming MAS in both a regular bipartite/non-regular non-bipartite graph if MD is applied. As seen, the inner state settles down in a non-regular non-bipartite graph; however, it oscillates in the other case. Another analyzed algorithm is LD, or, in other words, GMH with the optimal mixing parameter (i.e., \(\epsilon=0\)). As identified in [51], the weight matrix \(\mathbf{W}\) of this algorithm is identical to the weight matrix \(\mathbf{W}\) of MD in \(d\)-regular bipartite graphs, whereby this algorithm also diverges in this critical graph topology. See (13) for its weight matrix \(\mathbf{W}\)[62]. \[[\mathbf{W}]_{ij}= \begin{cases}\frac{1}{max\{d_{i},d_{j}\}},&\text{if }e_{ij} \in\mathbf{E}\\ 1-\sum_{j}\left[\mathbf{W}\right]_{ij},&\text{if }i=j\\ 0,&\text{otherwise}\end{cases}  \tag{13}\]  
In this paper, we also chose MH developed by [PERSON] and [PERSON] et al., which is known as one of the most common Markov Chain Monte Carlo methods to sample a probability distribution in complicated scenarios [70; 82]. As further seen, this scheme has found a wide range of applications as a data aggregation mechanism over the last decades. Note that the weight matrix \(\mathbf{W}\) of this algorithm is identical to the weight matrix \(\mathbf{W}\) of GMH with the mixing parameter \(\epsilon=1\)[51]. Mathematically, its weight matrix \(\mathbf{W}\) is defined as follows:  
\[[\mathbf{W}]_{ij}= \begin{cases}\frac{1}{max\{d_{i},d_{j}\}+1},&\text{if }e_{ij} \in\mathbf{E}\\ 1-\sum_{j}\left[\mathbf{W}\right]_{ij},&\text{if }i=j\\ 0,&\text{otherwise}\end{cases}  \tag{14}\]  
Another examined algorithm is BC, which is an approach with the Perron matrix based on Laplacian eigenvalues. Theoretically, these weights are considered to be the fastest algorithm among those with the Perron Matrix, and their weight matrix \(\mathbf{W}\) is defined as [83]:  
\[[\mathbf{W}]_{ij}= \begin{cases}\frac{2}{\lambda_{1}(\mathbf{L})+\lambda_{n-1} (\mathbf{L})},&\text{if }e_{ij}\in\mathbf{E}\\ 1-d_{i}\frac{2}{\lambda_{1}(\mathbf{L})+\lambda_{n-1}(\mathbf{L})},&\text{if }i=j\\ 0,&\text{otherwise}\end{cases}  \tag{15}\]  
We also included OW in our analyses and experiments.