All of the aforementioned algorithms rely on a Gauss-Seidel updating scheme, where the variable blocks are iteratively optimized in a particular sequence.
Specifically, when updating a given variable block (say \(x_t\) ), the values of all other blocks that appear earlier in the sequence (e.g., \(x_1, \ldots , x_{t-1}\) ) must be fixed to their newest values.
The overall convergence relies critically on the sequential nature of this update.
Unfortunately, this makes these algorithms unsuitable for distributed parallel computations.
A common workaround (e.g., see [1]}, [2]}) to enable parallel computation is to equivalently reformulate (REF ), (REF ) by introducing additional variables \(y_t\)  as follows:
\(\begin{array}{r@{\;\;}l}\displaystyle \mathop {\text{minimize}}_{\begin{array}{c}x_1, \ldots , x_T\\y_1, \ldots , y_T\end{array}} & \displaystyle \sum _{t = 1}^T f_t(x_t) \\\text{subject to} & \displaystyle x_t \in X_t, \;\; A_tx_t = y_t, \;\; t \in \lbrace 1,2, \ldots , T\rbrace , \\& \displaystyle \sum _{t = 1}^T y_t = b,\end{array}\) 
