Algebraic approaches for coded caching and distributed computing

dc.contributor.advisor Aditya Ramamoorthy Tang, Li
dc.contributor.department Electrical and Computer Engineering 2020-06-26T19:49:41.000 2020-06-30T03:21:30Z 2020-06-30T03:21:30Z Fri May 01 00:00:00 UTC 2020 2020-06-23 2020-01-01
dc.description.abstract <p>This dissertation examines the power of algebraic methods in two areas of modern interest: caching for large scale content distribution and straggler mitigation within distributed computation.</p> <p>Caching is a popular technique for facilitating large scale content delivery over the Internet. Traditionally, caching operates by storing popular content closer to the end users. Recent work within the domain of information theory demonstrates that allowing coding in the cache and coded transmission from the server (referred to as coded caching) to the end users can allow for significant reductions in the number of bits transmitted from the server to the end users. The first part of this dissertation examines problems within coded caching.</p> <p>The original formulation of the coded caching problem assumes that the server and the end users are connected via a single shared link. In Chapter 2, we consider a more general topology where there is a layer of relay nodes between the server and the users. We propose novel schemes for a class of such networks that satisfy a so-called resolvability property and demonstrate that the performance of our scheme is strictly better than previously proposed schemes. Moreover, the original coded caching scheme requires that each file hosted in the server be partitioned into a large number (i.e., the subpacketization level) of non-overlapping subfiles. From a practical perspective, this is problematic as it means that prior schemes are only applicable when the size of the files is extremely large. In Chapter 3, we propose a novel coded caching scheme that enjoys a significantly lower subpacketization level than prior schemes, while only suffering a marginal increase in the transmission rate. We demonstrate that several schemes with subpacketization levels that are exponentially smaller than the basic scheme can be obtained.</p> <p>The second half of this dissertation deals with large scale distributed matrix computations. Distributed matrix multiplication is an important problem, especially in domains such as deep learning of neural networks. It is well recognized that the computation times on distributed clusters are often dominated by the slowest workers (called stragglers). Recently, techniques from coding theory have found applications in straggler mitigation in the specific context of matrix-matrix and matrix-vector multiplication. The computation can be completed as long as a certain number of workers (called the recovery threshold) complete their assigned tasks.</p> <p>In Chapter 4, we consider matrix multiplication under the assumption that the absolute values of the matrix entries are sufficiently small. Under this condition, we present a method with a significantly smaller recovery threshold than prior work. Besides, the prior work suffers from serious numerical issues owing to the condition number of the corresponding real Vandermonde-structured recovery matrices; this condition number grows exponentially in the number of workers. In Chapter 5, we present a novel approach that leverages the properties of circulant permutation matrices and rotation matrices for coded matrix computation. In addition to having an optimal recovery threshold, we demonstrate an upper bound on the worst case condition number of our recovery matrices grows polynomially in the number of workers.</p>
dc.format.mimetype application/pdf
dc.identifier archive/
dc.identifier.articleid 8880
dc.identifier.contextkey 18242405
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/17873
dc.language.iso en
dc.source.bitstream archive/|||Fri Jan 14 21:30:05 UTC 2022
dc.subject.keywords algebra
dc.subject.keywords caching
dc.subject.keywords coding theory
dc.subject.keywords distributed computing
dc.title Algebraic approaches for coded caching and distributed computing
dc.type article
dc.type.genre thesis
dspace.entity.type Publication
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff Electrical Engineering thesis Doctor of Philosophy
Original bundle
Now showing 1 - 1 of 1
1.3 MB
Adobe Portable Document Format