Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data
This project investigates the challenge of achieving the stringent atomic read-modify-write (aRMW) semantics over an erasure-coded distributed storage system in the presence of Byzantine failures. We propose a quorum-based solution to achieve the same and fill in the gap in the current state of rese...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/165894 |
| _version_ | 1826110835865419776 |
|---|---|
| author | Siddharth, Meenachi Sundaram |
| author2 | Anwitaman Datta |
| author_facet | Anwitaman Datta Siddharth, Meenachi Sundaram |
| author_sort | Siddharth, Meenachi Sundaram |
| collection | NTU |
| description | This project investigates the challenge of achieving the stringent atomic read-modify-write (aRMW) semantics over an erasure-coded distributed storage system in the presence of Byzantine failures. We propose a quorum-based solution to achieve the same and fill in the gap in the current state of research for the aRMW semantics. The Byzantine fault-tolerance is achieved using homomorphic fingerprints proposed by Hendricks et. al. [1] to allow for independent verification of correctness of blocks by servers. The quorum system’s design is inspired by the design of quorums proposed in [2]. We design and prove rigorously the termination, agreement and correctness of the novel update and update propagation protocols using counting arguments in the presence of a specified bound on Byzantine failures. Simulations are performed to verify the correctness of the proposed system, and the effects of the code parameters of the erasure code as well as the number of Byzantine failures are investigated. It is observed that increasing the number of failures increases the number of messages transmissions as well as quorum size, as expected, while the code parameter does not seem to have a direct correlation with these properties. Also, the occurrence of excessive lags in the system are explored through the simulations, and it was empirically observed that the frequency of such lags is directly proportional to the write load on the storage system. Finally, the limitations of the study are explored and recommendations for future work are made. |
| first_indexed | 2024-10-01T02:41:00Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/165894 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:41:00Z |
| publishDate | 2023 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1658942023-04-21T15:37:09Z Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data Siddharth, Meenachi Sundaram Anwitaman Datta School of Computer Science and Engineering Anwitaman@ntu.edu.sg Engineering::Computer science and engineering::Computer systems organization::Performance of systems Engineering::Computer science and engineering::Computer systems organization::Computer system implementation This project investigates the challenge of achieving the stringent atomic read-modify-write (aRMW) semantics over an erasure-coded distributed storage system in the presence of Byzantine failures. We propose a quorum-based solution to achieve the same and fill in the gap in the current state of research for the aRMW semantics. The Byzantine fault-tolerance is achieved using homomorphic fingerprints proposed by Hendricks et. al. [1] to allow for independent verification of correctness of blocks by servers. The quorum system’s design is inspired by the design of quorums proposed in [2]. We design and prove rigorously the termination, agreement and correctness of the novel update and update propagation protocols using counting arguments in the presence of a specified bound on Byzantine failures. Simulations are performed to verify the correctness of the proposed system, and the effects of the code parameters of the erasure code as well as the number of Byzantine failures are investigated. It is observed that increasing the number of failures increases the number of messages transmissions as well as quorum size, as expected, while the code parameter does not seem to have a direct correlation with these properties. Also, the occurrence of excessive lags in the system are explored through the simulations, and it was empirically observed that the frequency of such lags is directly proportional to the write load on the storage system. Finally, the limitations of the study are explored and recommendations for future work are made. Bachelor of Engineering (Computer Engineering) 2023-04-16T04:02:29Z 2023-04-16T04:02:29Z 2023 Final Year Project (FYP) Siddharth, M. S. (2023). Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/165894 https://hdl.handle.net/10356/165894 en CE4079 application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering::Computer systems organization::Performance of systems Engineering::Computer science and engineering::Computer systems organization::Computer system implementation Siddharth, Meenachi Sundaram Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data |
| title | Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data |
| title_full | Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data |
| title_fullStr | Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data |
| title_full_unstemmed | Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data |
| title_short | Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data |
| title_sort | byzantine fault tolerant quorums for atomic read modify write operations on erasure coded data |
| topic | Engineering::Computer science and engineering::Computer systems organization::Performance of systems Engineering::Computer science and engineering::Computer systems organization::Computer system implementation |
| url | https://hdl.handle.net/10356/165894 |
| work_keys_str_mv | AT siddharthmeenachisundaram byzantinefaulttolerantquorumsforatomicreadmodifywriteoperationsonerasurecodeddata |