Distributed Computing Interaction Framework: Optimizing the algorithm with the Server-Worker model
TeXMIT
Distributed Computing with Matrix Multiplication
Overview
Structure
Master node: The largest computer responsible for partitioning the matrix, encoding, and distributing tasks to smaller worker nodes for computation. It also collects results from workers to verify integrity.
Worker: A subordinate computer responsible for computing submatrices and sending results back to the server (which the Master node receives).
Encode Function: Two encoding functions responsible for encoding the divided matrices using F, G functions.
where F and G are encode function satisfied F: $\mathbb{F}^{\frac{M}{m} \times \frac{N}{n}} \rightarrow \mathbb{F}^{\frac{M}{m} \times \frac{N}{n}}$ and G: $\mathbb{F}^{\frac{N}{n} \times \frac{P}{p}} \to \mathbb{F}^{\frac{N}{n} \times \frac{P}{p}}$
2. Task computing
$i$-th worker calculate $F(z_{i})G(z_{i})$. As soon as worker $i$ completes the computation, it will send
the result back to themaster node, noting that the returned results from the workers may vary in speed depending on each worker’s computational capabilities, and the returned results may not be accurate.
The coefficient of $Z_{u, v}$ in the polynomial corresponding to the exponent z is $n(u-1) + n-1 +mn(v-1)$ in the case where the index $j = k$ in $X_{i,j}$ and $Y_{k,l}$
3. Decoding (Result recovering)
The master node will collect the fastest R results returned by the workers. Afterward, the master node will recover the result $Z_{i, j}$ with $i \in {1,2,...,m}, j \in {1,2,...,p}$ based on polynomial interpolation.
Since the degree of the polynomial is $mnp + n - 2$, when applying the polynomial interpolation method, a minimum of $mnp + n - 1$ values is required to achieve the fastest results from the workers for the recovery of the matrix $Z$. Therefore, the recovery threshold is:
To accomplish this objective,we add rows or columns containing random elements to matrices A and B, respectively.From there, we consider two distinct cases:
Let $n_0=\frac{N}{n},m_0=\frac{M}{m},p_0=\frac{P}{p}$.
In case: $m_0 < p_0$, master node will generate the key $k_i$ corresponding to $F^{* }(z_i)$, where the vectors $k^{T}_{i} \in \mathbb{F}^{m^{* }}$, as follows:
After receiving the result $F_z(z_i)$ returned by the $i$-th worker, the master code will proceed to perform a check:
$$
R_iG^{* } (z_i) = k_iF^{* }(z_i)G^{* }(z_i)
$$
$$
F^{* }(z_i)R_i = F^{* }(z_i)G^{* }(z_i)k_i
$$
corresponding to cases $m^{* }< p^{* }$ and $m^{* }\geq p^{* }$.
5. Recover result
Similar to the recovery step mentioned above, the master node will collect the results returned from the worker nodes to determine the coefficients through polynomial interpolation. It is important to note that these returned results must satisfy the key-checking step to be considered valid.
If the returned result is accurate, we add it to the $\mathbb{R_Z}$, and when $|R_z| \geq R_C$, the master node proceeds with decoding to obtain the final matrix.
B. Recovery Threshold And Computation Load
a. Case $n < m$
For a given security level $P_{c} < P, t, s, d, n^{* }, p^{* }$ are given as mentioned above, the SPC code has the recovery threshold $P_R$ as follows:
