Polar Coded Computing:
The Role of the Scaling Exponent

In recent years, there has been a high demand for data processing at large scale. This has motivated a paradigm shift towards distributed computing, where a large scale computation is spread over $n$ workers. A central issue is that some workers may finish later than others or crash, and a common solution is to add redundancy: coded distributed computing breaks a given large computational job into $k$ smaller tasks and adds $n-k$ redundant tasks, so that the computation is performed over $n$ workers. As a result, the final output is available even if we receive only part of the outputs.

Applications of coding theory to distributed computing have been studied extensively, see e.g. [1, 2, 3, 4, 5, 6, 7, 8] and references therein. Product codes are applied to distributed matrix multiplication in [1]. In [2], maximum distance separable (MDS) codes are used to speed up matrix multiplication, and for matrix multiplication in a large finite field polynomial codes are employed in [3]. Luby Transform (LT) codes are proposed in [4, 5] for coded computation, and the application of polar codes to serverless computing is considered in [6, 7]. In [8], the average execution time of a coded computing system is related to the error probability of the linear code used to add redundancy. Although MDS codes are optimal in terms of average delay, they suffer from numerical stability and high decoding complexity, hence binary linear codes are studied in [8]: the authors characterize the performance gap between MDS and random binary linear codes and provide a numerical analysis of systems based on polar and Reed-Muller codes.

In this paper, we analyze the performance of polar codes for coded distributed computing. Polar codes provably achieve capacity for any binary memoryless symmetric (BMS) channel with quasi-linear encoding and decoding complexity [9]. The code construction can be performed with linear complexity [10, 11] and, by exploiting a partial order between the synthetic channels, the construction complexity becomes sub-linear [12]. The error probability under successive cancellation (SC) decoding scales as $2^{-\sqrt{n}}$ [13], $n$ being the block length, and polar codes are not affected by error floors [14]. Because of their attractive properties, polar codes have been recently adopted for the 5G wireless communications standard [15].

A central object of interest in the analysis of polar codes has been the speed of convergence of the rate to capacity [16, 17, 18, 19, 14, 20, 21]. This line of work shows that the gap to capacity scales with the block length as $n^{-1/\mu}$. The parameter $\mu$ is called the scaling exponent, it depends on the transmission channel and, for the special case of the binary erasure channel (BEC), $\mu\approx 3.63$ [16, 14]. Furthermore, by using large polarization kernels, it is possible to approach the optimal scaling exponent $\mu=2$ [20, 21].

The goal of this paper is to characterize the average execution time of a coded computing system using polar codes via their scaling exponent. In particular, our main contributions can be summarized as follows:

• •

  In Section III, we prove an upper bound on the average execution time of polar codes (Theorem 1) and, as a consequence, we show that the normalized gap between polar codes and the optimal MDS codes is $O(n^{-1/\mu})$, $\mu$ being the scaling exponent (Corollary 1).

• •

  In Section IV, we show that the normalized gap can be improved to roughly $O(n^{-1/2})$ by considering polar codes with large kernels (Theorem 2).

• •

  In Section V, we consider codes of rate $R=1/2$ and provide a heuristic argument suggesting that, for polar codes with scaling exponent $\mu$, the normalized gap should scale as $n^{-2/\mu}$. The argument is also validated by numerical evidence. Hence, as polar codes with large kernels approach the optimal $\mu=2$ [20, 21], this would lead to a gap scaling as $n^{-1}$, which matches the performance of random binary linear codes.

Our characterization of the average execution time via the scaling exponent exploits an intermediate result from [14]: we count the fraction of synthetic channels $W_{m}^{(i)}$ whose erasure probability is polynomially small in $n=2^{m}$, and we show that this fraction is at least the channel capacity $1-\epsilon$ minus a term scaling as $n^{-1/\mu}=2^{-m/\mu}$, where $\mu$ is the scaling exponent.

The proof of Lemma 2 follows by setting $\nu=9$ into (35) of [14], where $\rho$ is given by (33) and $\alpha$ is a factor $10$ smaller than in (31). At this point, we are ready to state and prove our main result on the average execution time.

Armed with this result, we can bound the gap between polar codes and MDS codes, which achieve the minimum average execution time (cf. Corollary 6 in [8]).

We remark that random binary linear codes achieve a smaller gap with respect to the optimal MDS codes. In fact, $nT_{\rm avg}^{\rm BRC}(n,R)-nT_{\rm avg}^{\rm MDS}(n,R)$ is $O\left(\frac{\log_{2}n}{n}\right)$, where $T_{\rm avg}^{\rm BRC}(n,R)$ denotes the average execution time for a random binary linear code of block length $n$ and rate $R$ (cf. Corollary 9 in [8]). Thus, a natural question is whether it is possible to reduce the gap between polar and MDS codes. We answer this question affirmatively in the next section, where we consider polar codes obtained from large random kernels.

First, we consider the fraction of synthetic channels whose erasure probability is polynomially small in $n=\ell^{m}$, and we show that it is lower bounded by the channel capacity $1-\epsilon$ minus a term scaling roughly as $\ell^{-m/2}=n^{-1/2}$. This result is stated below, and it is a (slight) improvement over Theorem 3 in [20]. Its proof is deferred to the appendix.

At this point, we are ready to state our results for polar codes based on large kernels.

The proof of (24) is analogous to that of Theorem 1, the only difference being that the application of Lemma 2 is replaced by the application of Lemma 3. The proof of (25) follows from (24) and from the lower bound on $nT_{\rm avg}^{\rm MDS}(n,R)$ in (21).

The upper bound in (25) roughly scales as $n^{-1/2}$, hence the result of Theorem 2 still does not match the performance of random binary linear codes. We conjecture that this is not due to a sub-optimality of polar codes using large kernels, but rather to a sub-optimality of our bounds. In fact, in the following section, we will give a simple heuristic argument suggesting that, for a family of polar codes of rate $R=1/2$ and scaling exponent $\mu$, the gap to optimum $nT_{\rm avg}^{\rm polar}(n,R)-nT_{\rm avg}^{\rm MDS}(n,R)$ is $O(n^{-2/\mu})$ (as opposed to $O(n^{-1/\mu})$ via Corollary 1). Since polar codes with large kernels approach $\mu=2$, this improved bound would match the gap to optimum of random binary linear codes.

We focus on the case $R=1/2$. Our heuristic argument relies on the assumption that the error probability $P_{e}(\epsilon,n)$ behaves as the lower bound $\max_{i\in\mathcal{I}}Z_{m}^{(i)}$ in (5). We also assume the existence of a scaling law s.t.

Here, $\mu$ represents the scaling exponent and $f$ is typically referred to as the mother curve. The idea is that, as the block length diverges, the gap to capacity $1/2-\epsilon$ scales as $n^{-1/\mu}$, and in this regime the error probability tends to the limit $f(n^{1/\mu}(1/2-\epsilon))\triangleq f(z)$. In [24], the authors provide numerical and rigorous evidence that the lower bound in (5) satisfies such a scaling law. Furthermore, the scaling exponent for the BEC is estimated as $\mu\approx 3.6261$, a value which is close to the rigorous upper bound of $3.639$ coming from [14].

We will also use that the derivative of the mother curve $f^{\prime}(\cdot)$ is even. To justify this, recall that $Z_{m}(\epsilon)$ is given by the recursion (4) with initial condition $Z_{0}=\epsilon$, $\{Z_{m}^{(i)}(\epsilon)\}_{i=1}^{n}$ are the erasure probabilities of the synthetic channels obtained by polarizing a BEC($\epsilon$), and $\mathcal{I}(\epsilon)$ is the set of indices corresponding to the synthetic channels with the smallest erasure probabilities $Z_{m}^{(i)}(\epsilon)$. Similarly, $Z_{m}(1-\epsilon)$ is given by (4) with initial condition $Z_{0}=1-\epsilon$, $\{Z_{m}^{(i)}(1-\epsilon)\}_{i=1}^{n}$ denote the erasure probabilities obtained from the polarization of a BEC($1-\epsilon$), and $\mathcal{I}(1-\epsilon)$ is the corresponding set of indices. Then, one can easily verify that $Z_{m}(1-\epsilon)=1-Z_{m}(\epsilon)$. As $R=1/2$, this implies that $\max_{i\in\mathcal{I}(1-\epsilon)}Z_{m}^{(i)}(1-\epsilon)=1-\min_{i\in\mathcal{I}^{c}(\epsilon)}Z_{m}^{(i)}(\epsilon)$, where $\mathcal{I}^{c}(\epsilon)$ is the complement set of $\mathcal{I}(\epsilon)$. Furthermore, as $m\to\infty$, $\min_{i\in\mathcal{I}^{c}(\epsilon)}Z_{m}^{(i)}(\epsilon)\approx\max_{i\in\mathcal{I}(\epsilon)}Z_{m}^{(i)}(\epsilon)$. Therefore, assuming that the lower bound in (5) is tight, $P_{e}(1-\epsilon,n)=1-P_{e}(\epsilon,n)$, which under the scaling assumption (26), implies that $f^{\prime}(\cdot)$ is even.

The goal of our heuristic argument is to show that

Note that, by using (11) and (15), the integral of $P_{e}(\epsilon,n)/\epsilon$ over the interval $[0,1/4]$ is $O(n^{-2})$. Furthermore, by using the trivial upper bound $P_{e}(\epsilon,n)\leq 1$, the same integral over the interval $[3/4,1]$ is upper bounded by $-\ln(3/4)$. Hence, (27) implies that

which implies that the gap to optimum for polar codes scales as $n^{-2/\mu}$, as desired.

We now show how to obtain (27). By performing the change of variables $z=n^{1/\mu}(1/2-\epsilon)$ and using the scaling law assumption (26), we have

Next, we integrate by parts the RHS of (29), which gives

The term $T_{1}$ in the first line of (30) is upper bounded by $\ln(3/4)+O(n^{-9})$. In fact, $f(-n^{1/\mu}/4)\approx P_{e}(3/4,n)\approx 1$ and $f(n^{1/\mu}/4)\approx P_{e}(1/4,n)\leq n^{-9}$, where the last inequality follows from (12) and (14). Finally, by performing a Taylor expansion of $\ln(1/2-zn^{-1/\mu})$ around $1/2$, the term $T_{2}$ in the second line of (30) is upper bounded by

where we have used that the second term in the first line is $0$ (being the integral of an odd function over a symmetric interval). By summing up these bounds on $T_{1}$ and $T_{2}$, we obtain that the quantity in (30) is upper bounded by $\ln(3/4)-\ln(1/2)+O(n^{-2/\mu})$, which combined with (29) implies the desired result (27).

The scaling suggested by the heuristic argument above is also supported by numerical results. Let $g(n)$ be defined as

where the upper bound follows from (5). The plot of Figure 1 shows that $g(n)-\ln(1-R)$ scales as $n^{-2/\mu}$, where the numerical value of $\mu$ matches the scaling exponent of the BEC.

In this paper, we consider the average execution time of a coded computing system using polar codes. We show that the performance gap between polar codes and the optimal MDS codes is upper bounded as $O(n^{-1/\mu})$, $n$ being the block length. Here, $\mu$ is the scaling exponent of polar codes for transmission over the BEC, and tight bounds have been proved on this quantity ($\mu\approx 3.63$). Next, we consider polar codes based on large kernels, which are known to approach the optimal scaling exponent $\mu=2$. For this family of codes, we prove that the gap to MDS codes scales roughly as $O(n^{-1/2})$. Finally, we conjecture that our bounds could be improved to $O(n^{-2/\mu})$ and $O(n^{-1})$, respectively, which would imply that polar codes with large kernels match the performance of binary random linear codes. Our conjecture is supported by a heuristic argument, as well as by numerical evidence.

D. Fathollahi and M. Mondelli were partially supported by the 2019 Lopez-Loreta Prize. The authors thank Hamed Hassani and Hessam Mahdavifar for helpful discussions.