Byzantine fault-tolerant quorums for atomic read-modify-write operations on erasure coded data

• Main Author: Siddharth, Meenachi Sundaram
• Other Authors: Anwitaman Datta
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering::Computer systems organization::Performance of systems; Engineering::Computer science and engineering::Computer systems organization::Computer system implementation
• Online Access: https://hdl.handle.net/10356/165894
• Institution: Nanyang Technological University

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.