Linear Exact Repair Schemes for Distributed Storage and Secure Distributed Matrix Multiplication
| dc.contributor.author | Valvo, Daniel William | en |
| dc.contributor.committeechair | Matthews, Gretchen L. | en |
| dc.contributor.committeemember | LeGrow, Jason T. | en |
| dc.contributor.committeemember | Mihalcea, Constantin Leonardo | en |
| dc.contributor.committeemember | Morrison, Travis William | en |
| dc.contributor.department | Mathematics | en |
| dc.date.accessioned | 2023-05-13T08:00:07Z | en |
| dc.date.available | 2023-05-13T08:00:07Z | en |
| dc.date.issued | 2023-05-08 | en |
| dc.description.abstract | In 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.abstractgeneral | Distributed 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.degree | Doctor of Philosophy | en |
| dc.format.medium | ETD | en |
| dc.identifier.other | vt_gsexam:36725 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/115028 | en |
| dc.language.iso | en | en |
| dc.publisher | Virginia Tech | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject | coding theory | en |
| dc.subject | erasure recovery | en |
| dc.subject | locally recoverable code | en |
| dc.subject | linear exact repair scheme | en |
| dc.subject | distributed storage | en |
| dc.subject | matrix multiplication | en |
| dc.subject | parallel computing | en |
| dc.subject | field trace | en |
| dc.title | Linear Exact Repair Schemes for Distributed Storage and Secure Distributed Matrix Multiplication | en |
| dc.type | Dissertation | en |
| thesis.degree.discipline | Mathematics | en |
| thesis.degree.grantor | Virginia Polytechnic Institute and State University | en |
| thesis.degree.level | doctoral | en |
| thesis.degree.name | Doctor of Philosophy | en |
Files
Original bundle
1 - 1 of 1