Linear Exact Repair Schemes for Distributed Storage and Secure Distributed Matrix Multiplication

dc.contributor.authorValvo, Daniel Williamen
dc.contributor.committeechairMatthews, Gretchen L.en
dc.contributor.committeememberLeGrow, Jason T.en
dc.contributor.committeememberMihalcea, Constantin Leonardoen
dc.contributor.committeememberMorrison, Travis Williamen
dc.contributor.departmentMathematicsen
dc.date.accessioned2023-05-13T08:00:07Zen
dc.date.available2023-05-13T08:00:07Zen
dc.date.issued2023-05-08en
dc.description.abstractIn this thesis we develop exact repair schemes capable of repairing or circumventing unavailable servers of a distributed network in the context of distributed storage and secure distributed matrix multiplication. We develop the (Λ, Γ, W, ⊙)-exact repair scheme framework for discussing both of these contexts and develop a multitude of explicit exact repair schemes utilizing decreasing monomial-Cartesian codes (DMC codes). Specifically, we construct novel DMC codes in the form of augmented Cartesian codes and rectangular monomial-Cartesian codes, as well as design exact repair schemes utilizing these constructions inspired by the schemes from Guruswami and Wootters [16] and Chen and Zhang [6]. In the context of distributed storage we demonstrate the existence of both high rate and low bandwidth systems based on these schemes, and we develop two methods to extend them to the l-erasure case. Additionally, we develop a family of hybrid schemes capable of attaining high rates, low bandwidths, and a balance in between which proves to be competitive compared to existing schemes. In the context of secure distributed matrix multiplication we develop similarly impactful schemes which have very competitive communication costs. We also construct an encoding algorithm based on multivariate interpolation and prove it is T-secure.en
dc.description.abstractgeneralDistributed networks may be thought of as networks of computers and/or servers which are capable of transmitting and receiving data from one another. For many applications it is possible for distributed networks to perform better than the sum of their constituent parts. In this thesis we will focus on the particular applications of distributed storage and secure distributed multiplication. A distributed storage system is a system that is capable of storing a single data file over every server in a distributed network. Distributed storage systems often come with exact repair schemes which are algorithms designed to reconstruct the data from a server in the network given the data from the other servers. In particular, if a server on the network ever fails or is otherwise unavailable an exact repair scheme can be used to repair the lost data from the server and maintain the original file. A distributed matrix multiplication scheme on the other hand is a process by which two matrices stored on a source server can be multiplied using a distributed network of helper servers. Again if a helper server becomes unavailable during this process we may use an exact repair scheme to circumvent this delay. The main goal of this thesis is to develop exact repair schemes for the distributed storage and secure distributed matrix multiplication contexts utilizing a mathematical object known as an evaluation code. We will develop several families of exact repair schemes which may be finely tuned to fit particular situations within these contexts, and we will compare these schemes to the existing schemes in the field.en
dc.description.degreeDoctor of Philosophyen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:36725en
dc.identifier.urihttp://hdl.handle.net/10919/115028en
dc.language.isoenen
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectcoding theoryen
dc.subjecterasure recoveryen
dc.subjectlocally recoverable codeen
dc.subjectlinear exact repair schemeen
dc.subjectdistributed storageen
dc.subjectmatrix multiplicationen
dc.subjectparallel computingen
dc.subjectfield traceen
dc.titleLinear Exact Repair Schemes for Distributed Storage and Secure Distributed Matrix Multiplicationen
dc.typeDissertationen
thesis.degree.disciplineMathematicsen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.nameDoctor of Philosophyen

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Valvo_DW_D_2023.pdf
Size:
1.86 MB
Format:
Adobe Portable Document Format