Show simple item record

dc.contributor.authorOkpotse, Toritseju
dc.contributor.otherQueen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.))en
dc.description.abstractModern data storage systems are typically built using hard drives and other components that are prone to failure. The financial, operational and legal impact of data loss is usually quite high, particularly for owners of massive storage data-centers. Data loss prevention is therefore a critical aspect of storage system design. Techniques such as data replication are incapable of satisfying the cost and energy-efficiency required in a large-scale distributed storage system (DSS). Erasure codes for data storage are required to offer systematic encoding, low repair locality, low encoding/decoding complexity and low decoding/storage overhead. However, information theoretical bounds have shown that all these metrics might need to be carefully traded off with one another. In this dissertation, analysis and design of Fountain codes for DSSs with respect to key performance requirements is performed. The first design proposed starts with a theoretical characterization of repair locality and system reliability for a Fountain coded system. The symbol repair locality probability as well as Data loss probability under BP decoding for a Fountain code are both derived. A multi-objective optimization (MOO) procedure is then used to determine degree distributions that achieve a good trade-off between repair locality, edge complexity and reliability. The second proposed solution offers a closed-form degree distribution using a modified truncated Poisson distribution (MTPD). The design is motivated by a careful study of the contributions from different encoding degrees towards the system performance. An analysis of the Fountain code probability of redundancy is used to determine the Poisson parameter. Both proposed solutions come with approximately 10% additional decoding overhead compared to recent contributions based on algebraic codes. However, their design for implementation over a binary finite field and excellent repair capabilities make them quite attractive for implementation. Through simulations, we also show that their decoding overhead performance exhibits significant improvement over some existing Fountain code degree distributions in the literature. For instance, with the MTPD, we achieve a data loss probability closely approaching 10^-4, while other Fountain codes compared are about a factor of 10^2 higher.en_US
dc.relation.ispartofseriesCanadian thesesen
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
dc.rightsQueen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canadaen
dc.rightsProQuest PhD and Master's Theses International Dissemination Agreementen
dc.rightsIntellectual Property Guidelines at Queen's Universityen
dc.rightsCopying and Preserving Your Thesisen
dc.rightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.en
dc.subjectCoding Theoryen_US
dc.subjectData Storage Codesen_US
dc.subjectFault-Tolerant Data Storageen_US
dc.subjectErasure Codesen_US
dc.subjectFountain Codesen_US
dc.subjectBelief Propagation Decodingen_US
dc.titleFountain Codes for Fault Tolerance in Distributed Storage Systemsen_US
dc.description.degreeDoctor of Philosophyen_US
dc.contributor.supervisorYousefi, Shahram
dc.contributor.departmentElectrical and Computer Engineeringen_US
dc.embargo.termsThis thesis includes a chapter which is the primary subject of an ongoing patent application.en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 United States
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 United States