# Distributed Average Consensus Algorithms in d-Regular Bipartite Graphs: Comparative Study
## 5 Conclusions  
In this paper, we present a comparative study of seven frequently applied distributed consensus algorithms for averaging in \(d\)-regular bipartite graphs. We assumed that their execution was bounded by a stopping criterion with various precisions, whereby diverging algorithms can potentially achieve the consensus. From the presented results, it can be seen that, generally, \(\mathrm{OW}\) was the best-performing algorithm among those examined, whereby the conclusions from non-regular non-bipartite graphs were also confirmed in this case. This algorithm did not perform the best in 2-regular bipartite graphs (i.e., in the sparsest examined graphs), where it was outperformed by GMH and \(\mathrm{CW}\) (in this case, only for the lowest precision of the applied stopping criterion). On the other hand, MH and \(\mathrm{CW}\) were classified as the worst-performing algorithms, which corresponds to conclusions from papers addressing these two algorithms in non-regular non-bipartite graphs. Furthermore, it was seen that each algorithm (except for GMH and MH) performed better for higher values of \(d\) (i.e., in graphs of greater connectivity). In addition, one can see that a higher precision of the applied stopping criterion caused each of the examined algorithms to decelerate. Contrary to conclusions in non-regular non-bipartite graphs, we can see that, surprisingly, GMH and \(\mathrm{CW}\) did not achieve the optimal performance with the lowest value of \(\epsilon\) (in the case of GMH) and with the highest \(\epsilon\) (if \(\mathrm{CW}\) was applied) in \(d\)-regular bipartite graphs of greater connectivity (this finding does not correspond to conclusions drawn in non-regular non-bipartite graphs). In this paper, all the examined algorithms were tested by investigating their convergence rate expressed as the number of iterations required for consensus achievement. The applied stopping criterion, which guaranteed the bounded execution of the algorithms, operated with three different precisions (note that the precision affects this property). Thus, in this paper, we identified that \(\mathrm{OW}\) performed the best in \(d\)-regular bipartite graphs in terms of the number of iterations for consensus achievement, i.e., the minimum number of iterations necessary for the criterion (23) to be met for the first time. A similar/same metric is applied also in [63; 65; 66]. The superior performance of \(\mathrm{OW}\) was also identified in other papers [67; 68; 69; 51; 62; 64; 70], where consensus algorithms are evaluated regarding various other properties, e.g., the asymptotic/per-step convergence factor, their associated convergence time, the error of the estimates, the averaging time, the mean square deviation, etc. The final conclusion of this paper is that \(\mathrm{OW}\) is recommended as the best-performing algorithm for \(d\)-regular bipartite graphs. Even though it was outperformed by GMH in graphs of low connectivity, we do not recommend \(\mathrm{GMH}\) for this critical graph topology since it is not possible to identify its optimal configuration without the knowledge of \(d\) and its performance is significantly degraded in densely connected regular bipartite graphs. Moreover, it was observed that \(\mathrm{MD}\) and \(\mathrm{LD}\) cannot achieve consensus in spite of the application of a stopping criterion regardless of its precision--all the other analyzed algorithms operate properly in \(d\)-regular bipartite graphs for each precision of the applied stopping criterion. Conceptualization, M.K. and J.K.; methodology, M.K. ; software, M.K. ; validation, M.K. and J.K.; formal analysis, M.K. and J.K.; investigation, M.K. ; resources, M.K. ; data curation, M.K. and J.K.; writing--original draft preparation, M.K. ; writing--review and editing, M.K. and J.K.;visualization, M.K. ; supervision, J.K.; project administration, M.K. ; funding acquisition, M.K. All authors have read and agreed to the published version of the manuscript.