\chapter{Distributed Algorithm via Survey Propagation}

It is noted that the PA problem inherits a unique nature that states interactively constrain each other, thus incurring many local solutions that significantly differ from the optimum. This corresponds to so-called {\em replica symmetry breaking} phenomenon in the field of statistical physics \cite{mezard1987spin}. 
The SP \cite{2005survey} approach is investigated to tackle this challenge induced by such property. 
%This is originally investigated in the field of statistical physics. 
From the analogy of the PA solution space with the formation of stable interaction relationships among variables, this approach can be exploited to characterize an efficient distributed solution \cite{2016beyound}. To be precise, the central peak-point probabilities of the PA contained in a cluster of the local optimal solutions are found by implementing a distributed search algorithm via message-passing techniques \cite{2001factor,2007affinity}. Therefore, individual users may be able to participate in obtaining computationally demanding solutions. A detailed description of the strategy is presented in the following sections.

\begin{figure}[!]
    \centering
    \includegraphics[width=\columnwidth]{figures/fig3_factor_graph}
    \caption{Graphical representation for pilot assignment problem. (a) Factor graph model for \textbf{(P2)}. (b) Two types of messages between $\mathcal{F}_a$ and $x_i$.}
    \label{fig:3_factor}
\end{figure}

\section{Graphical Representation}
To derive the corresponding message-passing based distributed algorithm, the structure of a graphical model that facilitates the understanding of the problem structure is necessarily considered. 
Fig. \ref{fig:3_factor}(a) illustrates a factor graph model \cite{2001factor} associated with the toy example. 
Note that if the group $\mathcal{K}_1$ is used for assignment, it limits the groups in $\mathcal{N}(1)$ unused. While the use of $\mathcal{K}_1$ constrains the states of corresponding neighbor groups, other states are not determined but are prohibited from assigning the same pilot with $\mathcal{K}_1$.
% In a valid PA solution with $x_1 = 1, x_6 = 2,$ and $x_i=0$ for $i\in\{2,3,4,5\}$, penalizing functions becomes zero, and two utility function take the outputs of $R_{1,1}$ and $R_{6,2}$, respectively.

\section{Derivation of Algorithm}

\subsection{Design Principles for Computation}
According to generic message-passing computational rules \cite{2001factor}, the tendency for the allocation of the $a$-th pilot to group $\mathcal{K}_i$ in optimal states are characterized by messages exchanged between node $x_i$ and node $\mathcal{F}_a$. To this end, two different types of messages are defined, respectively, as shown in Fig. \ref{fig:3_factor}(b): $\rho_{i a}(x_i=x)$, a message transferred from $x_i$ to $\mathcal{F}_a$ informing how evident the value of $x_i$ can take on a value of $x$, and $\alpha_{i a}(x_i=x)$, a message sent from $\mathcal{F}_a$ to $x_i$ representing how preferable the value of $x_i=x$ is to satisfy the constraint enforced by the factor function $\mathcal{F}_a$.
Under equilibrium states, both messages necessarily represent certain relationships between group $\mathcal{K}_i$ and $a$-th pilot is given according to the state of $x_i$ to maximize unconstrained formulation (\textbf{P2}) as
\begin{align}
    \rho_{i a}(x_i) = & ~\mathcal{R}_{i}(x_i) + \sum_{b \neq a} \alpha_{i b}(x_i) \, ,\label{eq:def_rho(x)}\\%[-.3em]
    \alpha_{i a}(x_i) = & \max_{\mathbf{x}\backslash\{x_i\}}\Big(\mathcal{F}_a (\mathbf{x})+\sum_{j \neq i}\rho_{j a}(x_j)\Big) \, .\label{eq:def_alp(x)}
\end{align}%\\[-.7em]
Thus, $\rho_{i a}(x_i)$ and $\alpha_{i a}(x_i)$ take the values associated with the maximal objective when  group $\mathcal{K}_i$ is assigned to the $a$-th pilot. %In particular, while $\rho_{i a}(x_i)$ evaluates $x_i$'s allocation state, $\alpha_{i a}(x_i)$ searches optimal system state given $x_i$'s state.
% weight function의 출력의 합을 최대화 하는 조합을 고려하는 와중에, penalizing 함수에 의해 system state에 가해지는 strict condition을 유의할 필요가 있음.

%%%%%%%%%%%책갈피: fig3

However, there may exist too many states of a PA task that slightly differ from optimal state $\mathbf{x}$ and take corresponding objective values very close to the optimum. 
In order to control all these assignments collectively, a basic principle of handling combinatorial optimization with the SP framework is applied by introducing multiple possible states for individual discrete variables, representing {\em chosen}, {\em unchosen}, and {\em undetermined}. In the PA task, the state of an individual variable $x_i$ imposed by the constraint $\mathcal{F}_a$ can be categorized into three types: {\em assigned}, {\em idle}, and {\em elsewhere}. If $x_i = a$, any group that shares members with $\mathcal{K}_i$ becomes idle, and no other group is assigned to the $a$-th pilot. If $x_i = 0$, which means that $\mathcal{K}_i$ is idle, other groups do not care about it and go into the so-called don't-care state\cite{2005survey}.
If $x_i \notin \{0, a\}$, which is associated with the elsewhere state, only the neighbor groups of $\mathcal{K}_i$ are restricted to being idle. % which is associated with elsewhere state, that only restrict the neighbor group of $\mathcal{K}_i$ idle state.
%The elsewhere state is similar with the don't care state that many possible states is involved in both states. 

To consolidate the relationship among these three states, three different types of messages are defined, i.e., %derivation of messages corresponding both Eq.\eqref{eq:def_rho(x)} and Eq.\eqref{eq:def_alp(x)} is available. While the messages about first two state, assigned and idle state, are 
$\{\rho_{i a}^{(a)}, \alpha_{i a}^{(a)}\}$ and $\{\rho_{i a}^{(0)}, \alpha_{i a}^{(0)}\}$ along with new messages associated with elsewhere state, $\{\rho_{i a}^{(*)}, \alpha_{i a}^{(*)}\}$. 
% The definition is given by
% \begin{align}
%     \rho_{i a}(*) \triangleq& \max_{x_i \notin \{0,a\}}\Big(\mathcal{R}_{i}(x_i) + \sum_{b \neq a} \alpha_{i b}(x_i)\Big),\label{eq:def_rho(else)}\\
%     \alpha_{i a}(*) \triangleq& \max_{x_i \notin \{0,a\}} \max_{\ \mathbf{x}\backslash\{x_i\}} \Big(\mathcal{F}_a (\mathbf{x})+\sum_{j \neq i}\rho_{j a}(x_j)\Big).\label{eq:def_alp(else)}
% \end{align}
% While there are too many possible states corresponding to vector $x$, the quantization can be adopted, one of the strategy for establishing survey propagation\cite{2016beyound}. We quantize the set of messages $\{\rho_{i a}, \alpha_{i a}\}$ into three newly defined states; $\{\rho_{i a}(a), \alpha_{i a}(a)\}$ denotes the messages when $\mathcal{K}_i$ is assigned to $a$-th pilot such that $x_i = a$, $\{\rho_{i a}(0), \alpha_{i a}(0)\}$ denotes the messages when $\mathcal{K}_i$ is not used such that $x_i = 0$, and $\{\rho_{i a}(*), \alpha_{i a}(*)\}$ denotes the messages when $\mathcal{K}_i$ is assigned elsewhere such that $x_i \notin \{0,a\}$. The first two types of messages are equivalent to predefined messages 
% where $x_i=a$ and $x_i=0$ respectively. The last type of messages are given by

\subsection{Messages for Assigned States}

If $x_{i}=a$, the message $\rho_{ia}(x_{i})$ is computed as follows.
\begin{equation}
    \rho_{ia}(a) = \mathcal{R}_{i}(a) + \sum_{b \neq a} \alpha_{i b}(a) = R_{i a} + \sum_{b \neq a} \alpha_{i b}(a) \, .
\end{equation}
Since the group $\mathcal{K}_{i}$ is assigned elsewhere from the $b$-th pilot such that $b \neq a$,
\begin{equation}
    \rho_{i a}^{(a)} = R_{i a}+\sum_{b \neq a} \alpha_{i b}^{(*)} \, .
\end{equation}

In the same case, the message $\alpha_{ia}(x_{i})$ is computed as follows.
\begin{equation}
    \alpha_{i a}(a) = \max_{\mathbf{x}\backslash\{x_i\}}\Big(\mathcal{F}_a (\mathbf{x})+\sum_{j \neq i}\rho_{j a}(x_j)\Big) \, .
\end{equation}
To avoid the penalizing function $\mathcal{F}_a$ returns negative infinity, all of the other state variables in $\mathbf{x}$ are prohibited to be $a$. The assigned message $\alpha_{i a}^{(a)}$ is then given by
\begin{equation}
    \alpha_{i a}^{(a)} = ~\sum_{\mathclap{i^{\prime} \in \mathcal{N}(i)}} \rho_{i^{\prime} r}^{(0)}
    + \; \sum_{\mathclap{i^{\prime \prime} \in \mathcal{N}(i)^{c}\backslash \{i\}}} \max\Big(\rho_{i^{\prime \prime} r}^{(0)},\rho_{i^{\prime \prime} r}^{(*)}\Big) \, .
\end{equation}

\subsection{Messages for Idle States}

If $x_{i}=0$, the message $\rho_{ia}(x_{i})$ is computed as follows.
\begin{equation}
    \rho_{ia}(0) = \mathcal{R}_{i}(0) + \sum_{b \neq a} \alpha_{i b}(0) = \sum_{b \neq a} \alpha_{i b}(0) \, .
\end{equation}
The corresponding idle message is straightforwardly given as follows, although the message $\alpha_{i a}^{(0)}$ is not.
\begin{equation}
    \rho_{i a}^{(0)} = ~\sum_{b \neq a} \alpha_{i b}^{(0)} \, .
\end{equation}

To compute the idle message $\alpha_{i a}^{(0)}$, we divide the idle state into two cases.
    \begin{itemize}
        \item \textbf{$a$-th pilot is utilized anyway:}\\
        There is only one $j \neq i \text{ s.t. } x_{j}=a$,\\
        then $x_{j^{\prime}}=0 \text{ for } j^{\prime} \in (N(j)\backslash \{i\}) \text{ and } x_{j^{\prime \prime}} \neq a \text{ for } j^{\prime \prime} \notin (N(j)\cup\{i\})$.
        \item \textbf{$a$-th pilot is not used for the uplink training:}\\
        $\nexists j \neq i \text{ s.t. } x_{j}=a$.
        % $x_{\hat{i}}=0, \forall \hat{i} \neq i$.
    \end{itemize}
Since the message $\alpha_{i a}^{(0)}$ returns the maximum value among these cases, it is given by
\begin{equation}
    \alpha_{i a}^{(0)} = \max\begin{cases}
        \ \max\limits_{j \neq i} \bigg(
            \rho_{j a}^{(a)} + \quad \displaystyle\sum\limits_{\mathclap{{j}^{\prime} \in \mathcal{N}({j})\backslash \{i\}}} \rho_{{j}^{\prime} a}^{(0)} \ + \quad \sum\limits_{\mathclap{{j}^{\prime \prime} \in \mathcal{N}({j})^{c}\backslash\{{i, j}\}}} \quad \max\Big(
                \rho_{{j}^{\prime \prime} r}^{(0)}, \ \rho_{{j}^{\prime \prime} r}^{(*)}
                \Big)
        \bigg)\ ,\\[2em]
        \ \displaystyle\sum\limits_{j \neq i} \max \Big(\rho_{j a}^{(0)}, \rho_{j a}^{(*)}\Big)\ .
    \end{cases}\label{eq:alpha_idle}
\end{equation}

\subsection{Messages for Elsewhere States}

For representing a number of elsewhere states, we pick the maximum value of $\rho_{ia}(x_{i})$ and $\alpha_{ia}(x_{i})$, while $x_{i} \notin \{0,a\}$, respectively. The message $\rho_{i a}^{(*)}$ is then given by
\begin{equation}
    \rho_{i a}^{(*)} = ~\max_{b \neq a} \Big(R_{i b}+\alpha_{i b}^{(b)}
    +\sum_{\mathclap{s \notin \{a, b\}}} \alpha_{i s}^{(*)}\Big) \, .
\end{equation}

We divide the idle state into two cases as same as $\alpha_{i a}^{(0)}$ to compute the idle message $\alpha_{i a}^{(*)}$, but the states of neighbor groups are limited to be idle in both of cases. Remainer descriptions of each case are as follows.
    \begin{itemize}
        \item \textbf{$a$-th pilot is utilized anyway:}\\
        There is only one $j \notin (\mathcal{N}(i)\cup\{i\}) \text{ s.t. } x_{j}=a$,\\
        then $x_{j^{\prime}}=0 \text{ for } j^{\prime} \in (N(i)\cup N(j)) \text{ and } x_{j^{\prime \prime}} \neq a \text{ for others}$.
        \item \textbf{$a$-th pilot is not used for the uplink training:}\\
        There is no state variable $x_{j}$ such that $x_{j}=a$.
        % $x_{\hat{i}}=0, \forall \hat{i} \neq i$.
    \end{itemize}
Note that if $j \notin \mathcal{N}(i)$, $i \notin \mathcal{N}(j)$. The corresponding message is given by
\begin{align}
    \alpha_{i a}^{(*)} =& \sum\limits_{i^{\prime} \in \mathcal{N}(i)} \rho_{i^{\prime} a}^{(0)}\nonumber\\
    &+ \max \begin{cases}
    ~\max\limits_{j\in \mathcal{N}(i)^{c}\backslash \{i\}}\bigg(
            \rho_{j a}^{(a)} + \ \displaystyle\sum\limits_{\mathclap{j^{\prime} \in \mathcal{N}(j) \backslash \mathcal{N}(i)}} \rho_{j^{\prime} a}^{(0)} \quad\;  + \quad\;  \sum\limits_{\mathclap{j^{\prime \prime} \in \mathcal{N}(j)^{c}\backslash(\{i\} \cup \mathcal{N}(i))}} \quad \max\Big(\rho_{j^{\prime \prime} a}^{(0)}, \rho_{j^{\prime \prime} a}^{(*)}\Big)
        \bigg)\ , \\[2em]
        \quad\;\
        \displaystyle\sum\limits_{\mathclap{i^{\prime \prime} \in \mathcal{N}(i)^{c}\backslash \{i,j\}}} \max\Big
            (\rho_{i^{\prime \prime} a}^{(0)},\ \rho_{i^{\prime \prime} a}^{(*)}
        \Big)\ .
    \end{cases}\label{eq:alpha_else}
\end{align}

\section{Rules for Message Update and Decision}

The message-passing algorithm is conducted to collect the information of optimality that is encoded as aforementioned descriptions.
Upon convergence of the messages, The decision of the value for $x_i$ is made using
\begin{align}
\tilde{b}_{i a} \triangleq& \ (\rho_{i a}^{(a)} - \rho_{i a}^{(0)}) + (\alpha_{i a}^{(a)} - \alpha_{i a}^{(0)})\, ,\\
\bar{b}_{i a} \triangleq& \ (\rho_{i a}^{(a)} - \rho_{i a}^{(*)}) + (\alpha_{i a}^{(a)} - \alpha_{i a}^{(*)})\, .
\end{align}
If group index $a$ is found with possible $\max_{a} \tilde{b}_{i a}$, the $i$-th users combination is assigned the $\hat{x}_i$-th pilot resource, which is given by $\hat{x}_{i}=\arg\max_{ a} \bar{b}_{i a}$. Otherwise, the $i$-th users combination is released idle. 

Note that the finally used forms of the messages are only two measures, difference between assigned state and idle state ($\{\rho_{i a}^{(a)} - \rho_{i a}^{(0)},~\alpha_{i a}^{(a)} - \alpha_{i a}^{(0)}\}$), difference between assigned state and elsewhere state ($\{\rho_{i a}^{(a)} - \rho_{i a}^{(*)},~\alpha_{i a}^{(a)} - \alpha_{i a}^{(*)}\}$). 
While the compactness of the message exchange is essential, it is sufficient to make decisions by the compressed forms of messages that are reduced from three to two types. The corresponding measures can be defined and calculated, respectively, as %To make the expression shortly, part of the notation is shown in superscript, i.e. $\rho_{i a}^{(a)}=\rho_{i a}(a)$. The results are given as 

\begin{align}
    \tilde{\rho}_{i a} \triangleq& ~\rho_{i a}^{(0)} - \rho_{i a}^{(*)}= \sum\limits_{b \neq a}\left(\tilde{\alpha}_{i b} - \bar{\alpha}_{i b}\right)- \max_{ b \neq  a} \left(R_{i b}-\bar{\alpha}_{i b}\right),\nonumber\\[-1.4em]\label{eq:rho_tilde}\\
    \bar{\rho}_{i a} \triangleq& ~\rho_{i a}^{(a)} - \rho_{i a}^{(*)}= R_{i a} - \max_{ b \neq  a} \left(R_{i b}-\bar{\alpha}_{i b}\right),\label{eq:rho_bar}\\%\\[10pt]
    \tilde{\alpha}_{i a} \triangleq& ~\alpha_{i a}^{(0)} - \alpha_{i a}^{(a)}\nonumber\\%\text{ \textcolor{red}{부호 바꿔서 baseline을 통일시키기} }
    =&  \bigg[\max\limits_{j \neq i}\Big(
        \bar{\rho}_{j a} - \left[\tilde{\rho}_{j a}\right]^{+}
        + \ \sum\limits_{\mathclap{ j^{\prime} \in \mathcal{N}({j})\backslash\{i\} }} \left[\tilde{\rho}_{j^{\prime} a}\right]^{-}
        \Big)
        \bigg]^{+}
        - \sum\limits_{\mathclap{ i^{\prime} \in \mathcal{N}(i) }} \left[\tilde{\rho}_{i^{\prime} a}\right]^{-},\label{eq:alp_tilde}\\
    \bar{\alpha}_{i a} \triangleq& ~\alpha_{i a}^{(*)}-\alpha_{i a}^{(a)}\nonumber\\
    =& \bigg[
        \max\limits_{{j}\in \mathcal{N}(i)^{c}\backslash \{i\} }\Big(
        \bar{\rho}_{{j} a} - \left[\tilde{\rho}_{{j} a}\right]^{+}
        + \ \sum\limits_{\mathclap{ {j}^{\prime} \in \mathcal{N}({j}) \backslash \mathcal{N}(i) }}{\left[\tilde{\rho}_{{j}^{\prime} a}\right]^{-}}
        \Big)\bigg]^{+},\label{eq:alp_bar}
\end{align}
where $[\ \cdot \ ]^{+}=\max(0,\ \cdot\ ), \ [\ \cdot\ ]^{-}=\min(0,\ \cdot \ )$. Then the decision variables are caculated as followings.

\begin{align}
\tilde{b}_{i a}=&\ (\bar{\rho}_{i a}-\tilde{\rho}_{i a}) - \tilde{\alpha}_{i a} \, , \label{eq:b_tilde}\\
\bar{b}_{i a}=&\ \bar{\rho}_{i a} - \bar{\alpha}_{i a}  \, . \label{eq:b_bar}
\end{align}

Algorithm 1 summarizes the overall SP-based distributed algorithm, where individual message update computations can be handled by individual users and tentative decisions are made by the CPU interconnected to APs. 

\begin{algorithm}[!t]\label{alg:PA1}
    \setstretch{1.2}
    \caption{Distributed PA algorithm}
    \begin{algorithmic}[1]
    \renewcommand{\algorithmicrequire}{\textbf{Input:}}
    \renewcommand{\algorithmicensure}{\textbf{Output:}}
    \REQUIRE Partial sum-rate $\{R_{i a}\}$ for all $(i, a)$ in \eqref{eq:weight_rate}.
    \ENSURE  Pilot indices of all users $\{x_i\}$
    \STATE \textit{Initialization} : Set $\tilde{\alpha}^{[1]}_{i a} = 0$, and $\bar{\alpha}^{[1]}_{i a} = 0$ for all $(i,r)$ and $t \gets 1$.
    \\\textbf{repeat}
    \\\quad \textit{Message updates}
    \STATE \qquad Update $\tilde{\rho}^{[t]}_{i a}$ and $\bar{\rho}^{[t]}_{i a}$ using \eqref{eq:rho_tilde} and \eqref{eq:rho_bar}, respectively.
    \STATE \qquad Update $\tilde{\alpha}^{[t+1]}_{i a}$ and $\bar{\alpha}^{[t+1]}_{i a}$ using \eqref{eq:alp_tilde} and \eqref{eq:alp_bar}.
    \\ \quad \textit{Tentative decision}
    \STATE \qquad Evaluate $\tilde{b}_{ia}$ and $\bar{b}_{ia}$ using \eqref{eq:b_tilde} and \eqref{eq:b_bar}.
    \STATE \qquad \textbf{if} ($\max_{a} \tilde{b}_{i a}>0$) \textbf{then} ${x}_{i} \gets \arg\max_{a} \bar{b}_{i a}$.
    \STATE \qquad \textbf{else} ${x}_{i} \gets 0$.
    \\ %\qquad \textbf{end if}
     \STATE \quad \textit{Increment} : $t \gets t+1$.
    \\\textbf{until} Convergence of all messages
    \RETURN Allocate pilot according to $\{x_i\}$. 
    \end{algorithmic} 
\end{algorithm}