# Distributed Average Consensus Algorithms in d-Regular Bipartite Graphs: Comparative Study
## 3 Theoretical Background
### General Definition of Average Consensus Algorithms  
Average consensus is an essential issue in designing suitable algorithms for distributed computing [70]. Over the past decades, average consensus algorithms have been widely applied in many distributed systems in order to accomplish various computing and controlling tasks [78]. The principle of the mentioned algorithms is based on regular communication among the agents forming MAS and updating their inner states according to neighbors' information. The primary purpose of these algorithms is to estimate the arithmetic mean from the initial inner states of all the agents in MAS, but they can also be applied for other tasks after tiny modifications (sum estimation, network size estimation) [65; 66]. The agents in MAS executing a distributed average consensus algorithm are required to initiate their inner states with a scalar value (e.g., a local sensor-measured value) and exchange their inner states with their adjacent agents in an iterative manner [79]. More specifically, the agents regularly exchange their current inner state with their neighbors and determine the inner state for the next iteration by applying the update rule expressible (from a global view) as the difference Equation (4) [70].  
\[\mathbf{x}(k+1)=\mathbf{W}\mathbf{x}(k) \tag{4}\]  
Here, \(\mathbf{x}(k)\) is a column variant vector formed by the inner states of all the agents in MAS at \(k\)-th iteration. The value of \(k=0\) represents the initial inner states. \(\mathbf{W}\) is the weight matrix of an algorithm whose spectrum is defined as follows [52]:  
\[SPEC(\mathbf{W})=\{\lambda_{1}(\mathbf{W}),\lambda_{2}(\mathbf{W}),...,\lambda _{n}(\mathbf{W})\} \tag{5}\]  
Similar to the Laplacian spectrum, \(\lambda_{1}(\mathbf{W})\) refers to the largest eigenvalue of the weight matrix \(\mathbf{W}\), \(\lambda_{2}(\mathbf{W})\) represents its second largest eigenvalue, and \(\lambda_{n}(\mathbf{W})\) is its smallest eigenvalue. Distributed consensus algorithms differ from each other by the entries of this matrix. As discussed in the mentioned paper, the weight matrix \(\mathbf{W}\) conditions many algorithm aspects such as the convergence/the divergence, the convergence rate, the robustness to potential threads, the distortion of the final estimates caused by various noises, etc.  
From a local view, the difference equation from (4) can be reformulated as follows [62]:  
\[x_{i}(k+1)=\sum_{j}^{n}[\textbf{W}]_{ij}x_{j}(k)\;\;for\;\forall v_{i}\in\textbf{ V} \tag{6}\]  
As further stated, the average consensus algorithms operate properly, provided that the limit (7) exists.  
\[\lim_{k\rightarrow\infty}\textbf{x}(k)=\lim_{k\rightarrow\infty}\textbf{W}^{ \textbf{k}}\textbf{x}(0)=\frac{1}{n}\textbf{1}\textbf{1}^{\text{T}}\textbf{x }(0) \tag{7}\]  
Here, **1** is an all-ones vector, whose entries are all equal to one, and \(\textbf{1}^{\text{T}}\) represents its transpose [52]. The existence of this limit means that all the inner states asymptotically converge to the value of the wanted aggregated function. Thus, a precise estimate of (for example) the arithmetic mean from the initial inner states of all the agents in MASs can be obtained by applying distributed consensus algorithms. As identified in [62], meeting the three convergence conditions provided in (8)-(10) guarantees that this limit is sure to exist.  
\[\textbf{1}^{\text{T}}\textbf{W}=\textbf{1}^{\text{T}} \tag{8}\]  
\[\textbf{W}\textbf{1}=\textbf{1} \tag{9}\]  
\[\rho\Bigg{(}\textbf{W}-\frac{1}{n}\textbf{1}\textbf{1}^{\text{T}}\Bigg{)}<1 \tag{10}\]  
The parameter \(\rho\) is a spectral radius, i.e., the largest eigenvalue in the magnitude of the corresponding matrix (see (11)) [80].  
\[\rho(\cdot)=\max_{i}\{|\;\lambda_{i}(\cdot)\;|\colon i=1,2,...n\} \tag{11}\]