# Distributed Average Consensus Algorithms in d-Regular Bipartite Graphs: Comparative Study
## 2 Related Work
### Distributed Consensus Algorithms in Non-Regular Non-Bipartite Graphs  
In this section, we turn the readers' attention to papers dealing with the chosen algorithms for evaluation, in non-regular non-bipartite graphs in this case. This was decided upon in order to compare the conclusion presented in this paper with conclusions valid in non-regular non-bipartite graphs. Thus, our intention was to identify whether there are any differences between the conclusions drawn in non-regular non-bipartite and regular bipartite graphs. The authors of [62] compared four distributed consensus algorithms (namely, MD, LD, BC, and OW) by applying the asymptotic convergence factor: a commonplace measure to quantify how fast an iterative algorithm converges to the global result, and its associated convergence time. From the presented results, it can be seen that OW performed the best since its values for these two metrics are the lowest (note that a lower value of these metrics indicates that an algorithm was performed better). As further identified in this study, BC was the second-best-performing, LD was the third, and MD achieved the worst performance. The paper [63] is concerned with a comparison of MD, MH, BC, and OW in symmetric, complete-cored symmetric, and K-cored symmetric star topologies by applying several various metrics. The authors of this paper assume that the execution of the algorithm was affected by quantization noise. From the presented results, it is apparent that the OW was faster than the concurrent approaches, but not necessarilywith the lowest error (also, BC's error was high). In general, the worst performance was observed to be achieved by MH in terms of the number of iterations for consensus. The second-best-performing algorithm was MD, and BC was classified as the third-best algorithm among the examined ones. Furthermore, it can be seen that only MD achieved consensus in all the performed scenarios, but other approaches were also able achieve consensus in the overwhelming majority of the scenarios. The authors of [64] show that OW achieved the best performance in the asymptotic phase; meanwhile, LD was considered to be superior in the transient phase. These identified facts allowed the authors of that paper to blend these algorithms via signal-adaptive morphing coefficients. In [51], CW and GMH with various mixing parameters were examined. In these papers, it was observed that higher values of \(\epsilon\) resulted in a higher performance of the algorithm in the case of CW. In contrast, GMH achieved higher performance, provided that \(\epsilon\) produced lower values (for \(\epsilon=0\), the algorithm performed the best). In [65], the performance of MD, MH, LD, BC, and OW was evaluated in random geometric graphs, in which the algorithms were applied to estimate the network size. From the presented results, it can be seen that OW performed the best in terms of the asymptotic convergence factor and its associated time, as also identified in [62]. In terms of the number of iterations required for consensus, OW outperformed its concurrent approaches in almost all of the examined scenarios. Only when the precision of the applied stopping criterion was low, and the best-connected entity was selected as the leader, was LD the best-performing algorithm among the studied ones. The worst performance was, in general, observed in the case of MD. In general, BC achieved an average performance, as shown in the figures. If the best-connected entity was selected as the leader, both OW and BC showed low estimation precision in the transient phase. In addition, it is shown that a higher precision of the stopping criterion led to a deceleration in every algorithm. Similarly, in [66], OW outperformed all the other approaches if the algorithms were applied for distributed summing in random geometric graphs and random graphs with various connectivities. This algorithm only achieved lower performance in the early phases in sparsely connected graphs, where it was outperformed by LD.