{'fraction_non_alphanumeric': 0.04223223282555865, 'fraction_numerical': 0.013988500978009603, 'mean_word_length': 4.449450904392765, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
OverSketch: Approximate Matrix Multiplication for the Cloud

We propose OverSketch, an approximate algorithm for distributed matrix multiplication in serverless computing. OverSketch leverages ideas from matrix sketching and high-performance computing to enable cost-efficient multiplication that is resilient to faults and straggling nodes pervasive in low-cost serverless architectures. We establish statistical guarantees on the accuracy of OverSketch and empirically validate our results by solving a large-scale linear program using interior-point methods and demonstrate a 34% reduction in compute time on AWS Lambda.


I. INTRODUCTION
Matrix multiplication is a frequent computational bottleneck in fields like scientific computing, machine learning, graph processing, etc. In many applications, such matrices are very large, with dimensions easily scaling up to millions. Consequently, the last three decades have witnessed the development of many algorithms for parallel matrix multiplication for High Performance Computing (HPC). During the same period, technological trends like Moore's law made arithmetic operations faster and, as a result, the bottleneck for parallel computation shifted from computation to communication. Today, the cost of moving data between nodes exceeds the cost of arithmetic operations by orders of magnitude, and this gap is increasing exponentially with time [1]- [3]. This has led to the popularity of communication-avoiding algorithms for parallel computation [3], [4].
In the last few years, there has been a paradigm shift from HPC towards distributed computing on the cloud due to extensive and inexpensive commercial offerings. In spite of developments in recent years, server-based cloud computing is inaccessible to a large number of users due to complex cluster management and a myriad of configuration tools. Serverless computing 1 has recently begun to fill this void by abstracting away the need for maintaining servers and thus removing the need for complicated cluster management while providing greater elasticity and easy scalability [5]- [7]. Some examples are Amazon Web Services (AWS) based Lambda, Microsoft Azure functions, and Google This work was supported by NSF Grants CCF-1703678, CCF-1704967 and CCF-0939370 (Center for Science of Information) 1 The term 'serverless' is a misnomer, servers are still used for computation but their maintenance and provisioning is hidden from the user. Figure 1: Job times for 3000 AWS Lambda nodes where the median job time is around 40 seconds, and around 5% of the nodes take 100 seconds, and two nodes take as much as 375 seconds to complete the same job.

Stragglers
Cloud Functions. Large-scale matrix multiplication, being embarrassingly parallel and frequently encountered, is a natural fit for serverless computing.
Existing distributed algorithms for HPC/server-based systems cannot, in general, be extended to serverless computing due to the following crucial differences between the two architectures: • Workers in the serverless setting, unlike cluster nodes, do not communicate amongst themselves. They read/write data directly from/to a single data storage entity (for example, cloud storage like AWS S3) and the user is only allowed to submit prespecified jobs and does not have any control over the management of workers [5]- [7]. • Distributed computation in HPC/server-based systems is generally limited by the number of workers at disposal. However, in serverless systems, the number of inexpensive workers can easily be scaled into the thousands, but these low-commodity nodes are generally limited by the amount of memory and lifespan available. • Unlike HPC, nodes in the cloud-based systems suffer degradation due to system noise which can be a result of limited availability of shared resources, network latency, hardware failure, etc. [8], [9]. This causes variability in job times, which results in subsets of slower nodes, often called stragglers, which significantly slow the computation. Time statistics for worker job times are plotted in Figure  1 for AWS Lambda. Notably, there are a few workers (∼ 5%) that take much longer than the median job time, thus decreasing the overall computational efficiency of the system. Distributed algorithms robust to such unreliable nodes are desirable in cloud computing.

A. Main Contributions
This paper bridges the gap between communicationefficient algorithms for distributed computation and existing methods for straggler-resiliency. To this end, we first analyze the monetary cost of distributed matrix multiplication for serverless computing for two different schemes of partitioning and distributing the data. Specifically, we show that rowcolumn partitioning of input matrices requires asymptotically more communication than blocked partitioning for distributed matrix multiplication, similar to the optimal communicationavoiding algorithms in the HPC literature.
In applications like machine learning, where the data itself is noisy, solution accuracy is often traded for computational efficiency. Motivated by this, we propose OverSketch, a sketching scheme to perform blocked approximate matrix multiplication and prove statistical guarantees on the accuracy of the result. OverSketch has threefold advantages: 1) Reduced computational complexity by significantly decreasing the dimension of input matrices using sketching, 2) Resiliency against stragglers and faults in serverless computing by over-provisioning the sketch dimension, 3) Communication efficiency for distributed multiplication due to the blocked partition of input matrices. Sketching for OverSketch requires linear time that is embarrassingly parallel. Through experiments on AWS Lambda, we show that small redundancy (≈ 5%) is enough to tackle stragglers using OverSketch. Furthermore, we use OverSketch to calculate the Hessian distributedly while solving a large linear program using interior point methods and demonstrate a 34% reduction in total compute time on AWS Lambda.

B. Related Work
Traditionally, techniques like speculative execution are used to deal with stragglers, for example, Hadoop MapReduce [10] and Apache Spark [11]. Such techniques work by detecting nodes that are running slowly or will slow down in the future and then assigning their jobs to new nodes without shutting down the original job. The node that finishes first submits its results. This has many limitations. A constant monitoring of jobs is required, which might be costly if there are many workers in the system. It is also possible that a node will straggle only towards the end of the job, and by the time the job is resubmitted, the additional time and computational overhead has already hurt the overall efficiency of the system. The situation is even worse for smaller jobs, as spinning up an extra node requires additional invocation and setup time which can exceed the job time itself.
Recently, approaches based on coding theory have been developed which cleverly introduce redundancy into the while B is divided into two column chunks B1 and B2. During the encoding process, redundant chunks A1 + A2 and B1 + B2 are created. To compute C, 9 workers store each possible combination of a chunk of A and B and multiply them. During the decoding phase, the master can recover the affected data (C11, C12 and C22 in this case) using the redundant chunks. computation to deal with stragglers [12]- [17]. Many of these proposed schemes have been dedicated to distributed matrix multiplication [13]- [16]. In [13], the authors develop a coding scheme for matrix multiplication that uses Maximum Distance Separable (MDS) codes to code A in a column-wise fashion and B in a row-wise fashion, so that the resultant is a product-code of C, where C = A × B. An illustration is shown in Figure 2. A simpler version of this has been known in the HPC community as Algorithm-Based-Fault-Tolerance (ABFT) [18]. Authors in [14] generalize the results in [13] to a d-dimensional product code with only one parity in each dimension. In [15], the authors develop polynomial codes for matrix multiplication, which is an improvement over [13] in terms of recovery threshold, that is, the minimum number of workers required to recover the product C.
The commonality in these and other similar results is that they divide the input matrices into row and column blocks, where each worker multiplies a row block (or some combination of row blocks) of A and a column block (or some combination of column blocks) of B. These methods provide straggler resiliency but are not cost-efficient as they require asymptotically more communication than blocked partitioning of data, as discussed in detail in the next section. Another disadvantage of such coding-based methods is that there are separate encoding and decoding phases that require additional communication and potentially large computational burden at the master node, which may make the algorithm infeasible in some distributed computing environments.

II. PRELIMINARIES
There are two common schemes for distributed multiplication of two matrices A ∈ R m×n and B ∈ R n×l , as illustrated in Figures 3a and 3b. We refer to these schemes as naive and blocked matrix multiplication, respectively. Detailed steps for these schemes are provided in Algorithms 1 and 2, respectively, for the serverless setting. During naive matrix multiplication, each worker receives and multiplies an a × n row-block of A and n × a column-block of B to compute an a × a block of C. Blocked matrix multiplication consists of two phases. During the computation phase, each worker gets two b × b blocks, one each from A and B, which are then multiplied by the workers. In the reduction phase, to  It is accepted in High Performance Computing (HPC) that blocked partitioning of input matrices takes less time than naive matrix multiplication [3], [4], [19]. For example, in [4], the authors propose 2.5D matrix multiplication, an optimal communication avoiding algorithm for matrix multiplication in HPC/server-based computing, that divides input matrices into blocks and stores redundant copies of them across processors to reduce bandwidth and latency costs. However, perhaps due to lack of a proper analysis for cloudbased distributed computing, existing algorithms for straggler mitigation in the cloud do naive matrix multiplication [13]- [15]. Next, we bridge the gap between cost analysis and straggler mitigation for distributed computation in the serverless setting.

MULTIPLICATION
There are communication and computation costs associated with any distributed algorithm. Communication costs themselves are of two types: latency and bandwidth. For example, sending n words requires packing them into contiguous memory and transmitting them as a message. The latency cost α is the fixed overhead time spent in packing and transmitting a message over the network. Thus, to send Q messages, the total latency cost is αQ. Similarly, to transmit Algorithm 1: Distributed naive matrix multiplication Input : Matrices A ∈ R m×n and B ∈ R n×l Result: C = A × B 1 Initialization: Divide A into submatrices of size a × n (row-wise division) and B into submatrices of size n × a (column-wise division) 2 for i=1 to m/a do 3 for j=1 to l/a do 4 1. Worker W ij receives i-th chunk of A, say A(i, :), and j-th chunk of B, say B(:, j) 5 2. W ij computes the a × a chunk of C, that is, and (k, j)-th block of B, say B(k, j), from the cloud storage sub-block C ij 14 for k = 1 to n/b do 15 1. W ij extracts the outputĈ ijk written by W ijk from cloud storage 16 2. W ij does C ij = C ij +Ĉ ijk 17 end 18 W ij writes C ij back to the cloud storage 19 end 20 end K words, a bandwidth cost proportional to K, given by βK, is associated. Letting γ denote the time to perform one floating point operation (FLOP), the total computing cost is γF , where F is the total number of FLOPs at the node. Hence, the total time pertaining to one node that sends M messages, K words and performs F FLOPs is where α β γ. The (α, β, γ) model defined above has been well-studied and is used extensively in the HPC literature [2]- [4], [20], [21]. It is ideally suited for serverless computing, where network topology does not affect the latency costs as each worker reads/writes directly from/to the cloud storage and no multicast gains are possible.
However, our analysis for costs incurred during distributed matrix multiplication differs from previous works in three principle ways. 1) Workers in serverless architecture cannot communicate amongst themselves, and hence, our algorithm for blocked multiplication is very different from optimal communication avoiding algorithm for HPC that involves message passing between workers [4].
2) The number of workers in HPC analyses is generally fixed, whereas the number of workers in the serverless setting is quite flexible, easily scaling into the thousands, and the limiting factor is memory/bandwidth available at each node. 3) Computation on the inexpensive cloud is more motivated by savings in expenditure than the time required to run the algorithm. We define our cost function below.
If there are W workers, each doing an equal amount of work, the total amount of money spent in running the distributed algorithm on the cloud is proportional to Eq. (1) does not take into account the straggling costs as they increase the total cost by a constant factor (by re-running the jobs that are straggling) and hence does not affect our asymptotic analysis. Inexpensive nodes in serverless computing are generally constrained by the amount of memory or communication bandwidth available. For example, AWS Lambda nodes have a maximum allocated memory of 3008 MB 2 , a fraction of the memory available in today's smartphones. Let the memory available at each node be limited to M words. That is, the communication bandwidth available at each worker is limited to M words, and this is the main bottleneck of the distributed system. We would like to multiply two large matrices A ∈ R m×n and B ∈ R n×l in parallel, and let M = O(n δ ). Note that if δ ≥ 2, one of the following will happen: • m = O(n) and l = O(n), and the input matrices can fit into one worker's memory and parallelism is not required. • Either m = ω(n) or l = ω(n) or both, and block-size for blocked matrix multiplication is n. The two schemes, naive and blocked multiplication, would exactly be the same in this case. Thus, for all practical cases in consideration, δ < 2.  Table I.
Proof: See Appendix A. The rightmost column in Table I lists the ratio of communication costs for naive and blocked matrix multiplication. We note that the latter significantly outperforms the former, Matrix dimension (n) with communication costs being asymptotically worse for naive multiplication. An intuition behind why this happens is that each worker in distributed blocked multiplication does more work than in distributed naive multiplication for the same amount of received data. For example, to multiply two square matrices of dimension n, where memory at each worker limited by M = 2n, a = 1 for naive multiplication and b = √ n for blocked multiplication. We note that the amount of work done by each worker in naive and blocked multiplication is O(n) and O(n 3/2 ), respectively. Since the total amount of work is constant and equal to O(n 3 ), blocked matrix multiplication ends up communicating less during the overall execution of the algorithm as it requires fewer workers. Note that naive multiplication takes less time to complete as each worker does asymptotically less work, however, the number of workers required is asymptotically more, which is not an efficient utilization of resources and increases the expenditure significantly. Figure 4 supports the above analysis where we plot the cost in dollars of multiplying two square matrices in AWS Lambda, where each node's memory is limited by 3008 MB and price per worker per 100 millisecond is $0.000004897. However, as discussed earlier, existing schemes for stragglerresiliency in distributed matrix multiplication consider naive multiplication which is impractical from a user's point of view. In the next section, we propose OverSketch, a scheme to mitigate the detrimental effects of stragglers for blocked matrix multiplication.

IV. OVERSKETCH: STRAGGLER-RESILIENT BLOCKED MATRIX MULTIPLICATION USING SKETCHING
Many of the recent advances in algorithms for numerical linear algebra have come from the technique of linear sketch-ing, in which a given matrix is compressed by multiplying it with a random matrix of appropriate dimension. The resulting product can then act as a proxy for the original matrix in expensive computations such as matrix multiplication, least-squares regression, low-rank approximation, etc. [22]- [25]. For example, computing the product of A ∈ R m×n and B ∈ R n×l takes O(mnl) time. However, if we use S ∈ R n×d to compute the sketches, sayÃ = AS ∈ R m×d andB = S T B ∈ R d×l , where d n is the sketch dimension, we can reduce the computation time to O(mdl) by computing an approximate product ASS T B. This is very useful in applications like machine learning, where the data itself is noisy, and computing the exact result is not needed.
Key idea behind OverSketch: Sketching accelerates computation by eliminating redundancy in the matrix structure through dimension reduction. However, the codingbased approaches described in Section I-B have shown that redundancy can be good for combating stragglers if judiciously introduced into the computation. With these competing points of view in mind, our algorithm OverSketch works by "oversketching" the matrices to be multiplied by reducing dimensionality not to the minimum required for sketching accuracy, but rather to a slightly higher amount which simultaneously ensures both the accuracy guarantees and speedups of sketching and the straggler resilience afforded by the redundancy which was not eliminated in the sketch. OverSketch further reduces asymptotic costs by adopting the idea of block partitioning from HPC, suitably adapted for a serverless architecture.
Next, we propose a sketching scheme for OverSketch and describe the process of straggler mitigation in detail.

A. OverSketch: The Algorithm
During blocked matrix multiplication, the (i, j)-th block of C is computed by assimilating results from d/b workers who compute the productÃ(i, k) ×B(k, j), for k = 1, · · · , d/b. Thus, the computation C(i, j) can be viewed as the product of the row sub-blockÃ(i, :) ∈ R b×d ofÃ and the column sub-blockB(:, j) ∈ R d×b ofB. An illustration is shown in Figure  5. Assuming d is large enough to guarantee the required accuracy in C, we increase the sketch dimension from d to z = d + eb, where e is the worst case number of stragglers in N = d/b workers. For the example in Figure 5, e = 1. To get a better insight on e, we observe in our simulations for cloud systems like AWS lambda and EC2 that the number of stragglers is < 5% for most runs. Thus, if N = d/b = 40, i.e. 40 workers compute one block of C, then e ≈ 2 is sufficient to get similar accuracy for matrix multiplication. Next, we describe how to compute the sketched matricesÃ andB.
Many sketching techniques have been proposed recently for approximate matrix computations. For example, to sketch a m×n matrix A with sketch dimension d, Gaussian projection takes O(mnd) time, Subsampled Randomized Hadamard Transform (SRHT) takes O(mn log n) time, count sketch takes O(nnz(A)) time, where nnz(·) is the number of nonzero entries [23], [26]- [28]. Count sketch is one of the most popular sketching techniques as it requires linear time to compute the matrix sketch with similar approximation guarantees.
To compute the count sketch of A ∈ R m×n of sketch dimension b, each column in A is multiplied by −1 with probability 0.5 and then mapped to an integer sampled uniformly from {1, 2, · · · , b}. Then, to compute the sketch A c = AS c , columns with the same mapped value are summed. An example of count sketch matrix with n = 9 and b = 3 is Here, A has 9 columns, and columns 4, 5 and 7 were mapped to 1, columns 1, 2 and 6 were mapped to 2, and columns 3, 8 and 9 were mapped to 3. Thus, the count sketchÃ c would have only 3 columns, which are obtained by summing the columns of A with the same mapped value (after possibly multiplying with -1). The sparse structure of S c ensures that the computation of sketch takes O(nnz(A)) time. However, a drawback of the desirable sparse structure of count sketch is that it cannot be directly employed for straggler mitigation in blocked matrix multiplication as it would imply complete loss of information from a subset of columns of A. For the example in (2), suppose the worker processing column 3 ofÃ c be straggling. Ignoring this worker would imply that columns 3, 8 and 9 of A were not considered in the computation. This will generally lead to poor accuracy for sketched matrix multiplication.
To facilitate straggler mitigation for blocked matrix multiplication, we propose a new sketch matrix S, inspired by count sketch, and define it as where N = d/b, e is the expected number of stragglers per block of C and S i ∈ R n×b , for i = 1, 2, · · · , (N + e), is a count sketch matrix with dimension b. Thus, the total sketchdimension for the sketch matrix in (3) Now, for blocked matrix multiplication using OverSketch and as illustrated in Figure 5, the following holds Theorem 4.1: Computing (AS) × (S T B) using sketch S ∈ R n×z in (3) and d = 2 θ , while ignoring e stragglers among any z b workers, is ( , θ) accurate. Proof: See Appendix B. For certain applications, the guarantee in theorem 4.1 may be too crude as the product of ||A|| 2 F and ||B|| 2 F in the RHS can get big for large matrices A and B. We can obtain a stronger result than in theorem 4.1 when min(rank(A), rank(B)) n, for example, when A is a fat matrix, or B is a tall matrix. Without loss of generality, say min(rank(A), rank(B)) = rank(A) = r. Thus, where ||·|| 2 denotes the spectral norm. Hence, with probability at least (1 − θ) with probability (1 − θ), which is a better approximation for the product ASS T B.
During the reduction phase, we use ml/b 2 workers, which is much less than the number of workers used during the computation phase, that is, mlz/b 3 . In our experiments, we observe that the possibility of stragglers reduces significantly if fewer workers are used. This is especially true for the reduction phase, as healthy running workers from the computation phase are reused, reducing the chances of stragglers. However, in the unfortunate event that stragglers are observed during reduction, speculative execution can be used, i.e. detecting and restarting the slow job. Another simple solution is to use existing coding techniques as described in Figure 2, that is, by adding one parity row-block toÃ and one parity row column toB before multiplying them, which can tolerate 3 stragglers in the worst case. However, this would require a decoding step to compensate for the missing stragglers.

A. Blocked Matrix Multiplication on AWS Lambda
We implement the straggler-resilient blocked matrix multiplication described above in the serverless computing    Figure 6a. The corresponding worker job times are shown in Figure 1, where the median job time is around 42 seconds, and some stragglers return their results around 100 seconds and some others take up to 375 seconds. We note that the compute time for matrix multiplication reduces by a factor of 9 if we ignore at most 4 workers per 30 workers that compute a block of C. In figure 6b, for same A and B, we plot average error in matrix multiplication by generating ten instances of sketches 3 A working implementation of OverSketch is available at https://github.com/vvipgupta/OverSketch and averaging the error in Frobenius norm, ||AB−ASS T B|| F ||AB|| F , across instances. We see that the average error is only 0.8% when 4 workers are ignored.

B. Solving Optimization Problems with Sketched Matrix multiplication
Matrix multiplication is the bottleneck of many optimization problems. Thus, sketching has been applied to solve several fairly common optimization problems using secondorder methods, like linear programs, maximum likelihood estimation, generalized linear models like least squares and logistic regression, semi-definite programs, support vector machines, Kernel ridge regression, etc., with essentially same convergence guarantees as exact matrix multiplication [24], [25]. As an instance, we solve the following linear program (LP) using interior point methods on AWS Lambda where x ∈ R m×1 , c ∈ R m×1 , b ∈ R n×1 and A ∈ R n×m is the constraint matrix with n > m. To solve (5) using the logarithmic barrier method, we solve the following sequence of problems using Newton's method where a i is the i-th row of A, τ is increased geometrically as τ = 2τ after every 10 iterations and the total number of iterations is 100. The update in the t-th iteration is given by where x t is the estimate of the solution in the t-th iteration and η is the appropriate step-size. The gradient and Hessian for the objective in (6) are given by respectively. The square root of the Hessian is given by The computation of Hessian requires O(nm 2 ) time and is the bottleneck in each iteration. Thus, we use our distributed and sketching-based blocked matrix multiplication scheme to mitigate stragglers while evaluating the Hessian approximately, i.e.
We take the block size, b, to be 1000, the dimensions of A to be n = 40b and m = 5b and the sketch dimension to be z = 20b. We use a total of 500 workers in each iteration. Thus, to compute each b × b block of C, 20 workers are assigned to compute matrix multiplication on two b × b blocks. We depict the time and error versus iterations in figure 7. We plot our results for different values of e, where e is the number of workers ignored per block of C. In our simulations, each iteration includes around 9 seconds of invocation time to launch AWS Lambda workers and assign tasks. In figure 7a, we plot the total time that includes the invocation time and computation time versus iterations. In 7b, we exclude the invocation time and plot just the compute time in each iteration and observe 34% savings in solving (5) when e = 1, whereas the effect on the error with respect to the optimal solution is insignificant (as shown in figure  7c).

C. Comparison with Existing Straggler Mitigation Schemes
In this section, we compare OverSketch with an existing coding-theory based straggler mitigation scheme described in [13]. An illustration for [13] is shown in Figure 2. We multiply two square matrices A and B of dimension n on AWS Lambda using the two schemes, where A(x, y) = x+y and B(x, y) = x × y for all x, y ∈ [1, n]. We limit the bandwidth of each worker by 400 MB (i.e. around 48 million entries, where each entry takes 8 bytes) for a fair comparison. Thus, we have 3b 2 = 48 × 10 6 , or b = 4000 for OverSketch and 2an + a 2 = 48 × 10 6 for [13], where a is the size of the row-block of A (and column-block of B). We vary the matrix dimension n from 6b = 24000 to 14b = 56000. For OverSketch, we take the sketch dimension z to be n/2 + b, and take e = 1, i.e., ignore one straggler per block of C.
For straggler mitigation in [13], we add one parity row in A and one parity column in B. In Figures 8a and 8b, we compare the workers required and average cost in dollars, respectively, for the two schemes. We note that OverSketch requires asymptotically fewer workers, and it translates to the cost for doing matrix multiplication. This is because the running time at each worker is heavily dependent on communication, which is the same for both the schemes. For n = 20000, the average error in Frobenius norm for OverSketch is less than 2%, and decreases as n is increased. The scheme in [13] requires an additional decoding phase, and assume the existence of a powerful master that can store the entire product C in memory and decode for the missing blocks using the redundant chunks. This is also true for the other schemes in [14]- [16]. Moreover, these schemes would fail when the number of stragglers is more than the provisioned redundancy while OverSketch has a 'graceful degradation' as one can get away by ignoring more workers than provisioned at the cost of accuracy of the result.

VI. CONCLUSION
Serverless computing penetrates a large user base by allowing users to run distributed applications without the hassles of server management. We analyzed the cost of distributed computation in serverless computing for naive and blocked matrix multiplication. Through analysis and experiments on AWS Lambda, we show that the latter significantly outperforms the former. Thus, existing straggler mitigation schemes that do naive matrix multiplication are unsuitable. To this end, we develop OverSketch, a sketching based algorithm for approximate blocked matrix multiplication. Our sketching scheme requires time linear in the size of input matrices. As a distributed matrix multiplication algorithm, OverSketch has many advantages: reduction in dimension of input matrices for computational savings, and built-in straggler resiliency. Extensive experiments on AWS Lambda support our claims that OverSketch is resilient to stragglers, cost-efficient, and highly accurate for suitably chosen sketch dimension.

APPENDIX
A. Proof of Proposition 3.1 To compare naive and blocked multiplication, we first observe that the computation cost in (1), that is W × F , is the same for both naive and blocked multiplication and is equal to O(mnl), which is the total amount of work done during matrix-matrix multiplication 4 . Let W 1 be the number of workers required for naive matrix multiplication. Then, W 1 = ml/a 2 , as each worker is sent one row-block of A from m/a choices, and one column-block of B from l/a choices. Each worker receives 2an words and writes back a 2 words. Hence, the total communication incurred during the algorithm is W 1 × (2an + a 2 ) = (2nml/a + ml). Also, since each worker can only receive M words, we have M = 2an, thus a = M/2n. Hence, the total bandwidth cost for naive multiplication is β × (4n 2 ml/M + ml) = O(n 2−δ ml). Also, the total number of messages sent during the process is W 1 , and hence the total latency cost is O(mln 2(1−δ) ).
During the computation phase for blocked multiplication, W 2,comp = (n/b) × ml/b 2 , as computation of one b × b block of C ∈ R m×l requires n/b workers, and there are a total of ml/b 2 such blocks. Again, each worker receives two b × b blocks, one from each A and B, and writes back a b × b block, where b satisfies M = 2b 2 . Thus, the total bandwidth cost incurred during the computation phase is βW 2,comp × 3b 2 = 3βnml/b = O(mln 1−δ/2 ). The total number of messages received by the workers is W 2,comp , and, hence, the latency cost is αnml/b 3 = O(mln 1−3δ/2 ). During the reduction phase, the number of workers required is W 2,red = ml/b 2 , and each worker receives n/b blocks of size b × b to compute one block of C. Thus, for the reduction phase, the communication is W 2,red ×b 2 ×(n/b) = nml/b = O(mln 1−δ/2 ) and total messages sent is W 2,red × (n/b) = mln/b 3 = O(mln 1−3δ/2 ). Hence, the total latency and bandwidth costs for blocked multiplication are O(mln 1−3δ/2 ) and O(mln 1−δ/2 ), respectively. This analysis justifies the costs summarized in Table I and proves the theorem.

B. Proof of Theorem 4.1
The following three lemmas will assist us with the proof of Theorem 4.1.
Lemma A.1: let S c ∈ R n×b be a count sketch matrix. Then, for any vectors x, y ∈ R n×1 , the following holds 4 The computation cost for blocked matrix multiplication can be further improved by using Strassen type methods that take O(b 2.38 ) to multiply two square sub-blocks of dimension b × b, but we do not consider that advantage in this paper for clarity of exposition and to emphasize on savings just due to communication.
Proof: See [29], Appendix A. Lemma A.2: Let S = 1 √ N (S 1 , S 2 , · · · , S N ) ∈ R n×d , where d = N b and S i ∈ R n×b is a count sketch matrix that satisfies (10) and (11), for all i ∈ 1, 2, · · · , N . Then, for any vectors x, y ∈ R n×1 , the following holds Proof: Note that, SS T = 1 N (S 1 S T 1 + S 2 S T 2 + · · · + S N S T N ). Thus, and hence, E[x T SS T y] = x T y by (10) and linearity of expectation. Now, Noting that S 1 , S 2 , · · · , S N are independent random variables and using (10), we get Now, using the above equation and (11) in (12), we get which proves the lemma. Lemma A.3: Let d = 2/ . Then, for any A ∈ R m×n , B ∈ R n×l and S as defined in lemma A.2, Proof: By the property of Frobenius norm and linearity of expectation, we have where a (i) and b (j) are the i-th row and j-th columns of A and B, respectively. Now, using lemma A.2 in (14), we get which is the desired result.
We are now ready to prove theorem 4.1. As illustrated in figure 5, we can think of computation of a b × b sub-block C(i, j) as multiplication of row blockÃ(i, :) ofÃ = AS and column-blockB(:, j) ofB = S T B. Since we ignore upto only e workers in the calculation of a b × b block of C, the effective sketch dimension is greater than d = 2 θ , and therefore, from lemma A.
for all i ∈ 1, · · · , m/b and j ∈ 1, · · · , l/b. Note that even if we applied the same sketch on A and B across row and column blocks, respectively, S ij in the above equation might end up being different for each pair (i, j) depending upon the location of stragglers, though with a common property that the sketch dimension is at least d. Now, we note that

Now, by Markov's inequality
which proves the desired result.