# Distributed Average Consensus Algorithms in d-Regular Bipartite Graphs: Comparative Study
###### Abstract  
Consensus-based data aggregation in \(d\)-regular bipartite graphs poses a challenging task for the scientific community since some of these algorithms diverge in this critical graph topology. Nevertheless, one can see a lack of scientific studies dealing with this topic in the literature. Motivated by our recent research concerned with this issue, we provide a comparative study of frequently applied consensus algorithms for distributed averaging in \(d\)-regular bipartite graphs in this paper. More specifically, we examine the performance of these algorithms with bounded execution in this topology in order to identify which algorithm can achieve the consensus despite no reconfiguration and find the best-performing algorithm in these graphs. In the experimental part, we apply the number of iterations required for consensus to evaluate the performance of the algorithms in randomly generated regular bipartite graphs with various connectivities and for three configurations of the applied stopping criterion, allowing us to identify the optimal distributed consensus algorithm for this graph topology. Moreover, the obtained experimental results presented in this paper are compared to other scientific manuscripts where the analyzed algorithms are examined in non-regular non-bipartite topologies. bipartite graphs; consensus; data aggregation; distributed averaging; distributed computing; information fusion; multi-agent systems; regular graphs +
Footnote †: journal:  
0000-0001-4000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000  
in the so-called big data era [2]. Therefore, many experts from various areas have been dealing with this challenge over the last decades [3; 4; 5; 6]. As seen in the literature [7; 8; 9; 10; 11], data aggregation seems to be an appropriate technique to organize the mass of raw data in a meaningful manner. In general, one can understand the term data aggregation as a data/information mining process for searching, collecting, and expressing a set of raw data from independent sources in a more transparent and summarized form [12]. In other words, it is a commonplace procedure to simplify various daily processes in our technologically developed era [13]. Data aggregation enables the effective identification of patterns (hard to identify by a common user) in a processed dataset [14]. The final form of aggregated data is conditioned by the purpose that the data are expected to be used for. Generally, the process of data aggregation can be partitioned into four successive phases, namely [15]. Phase 1: extracting data from independent sources;  
Phase 2: storing the extracted data;  
Phase 3: interpretation of the stored data;  
Phase 4: presenting the processed data in an appropriate form. As seen in the literature [16; 17; 18; 19], the application of data aggregation is beneficial in various areas e.g., the financial sector, marketing, medicine, technical industries, etc. In this paper, we consider a group of independent entities (referred to as agents) forming MAS, where data aggregation is exploited in order to optimize the applications executed in these systems in numerous aspects [20]. The agents in these systems are required to communicate with each other and interact with their adjacent environment (see Figure 1 for the characteristic features of agents forming MAS) [11]. The primary task of MASs is to efficiently and quickly solve difficult issues unmanageable for individual solvers. This technology has applications in different areas, e.g., artificial intelligence, monitoring, control, grid computing, military, electronics, manufacturing, etc. [21]. In this paper, we consider a scenario where agents of MAS are expected to independently measure a physical quantity of one's interest, and an algorithm for aggregating these independent data is subsequently applied in order to determine an appropriate aggregate function from these measured values (see Figure 2 for a general architecture of the data aggregation in this scenario).