Search papers, labs, and topics across Lattice.
This paper introduces a new asynchronous verifiable information dispersal (AVID) protocol that optimizes data dispersal, storage, retrieval, and recovery in distributed storage systems, addressing a gap in existing protocols that focus primarily on retrieval and storage. By employing a novel two-dimensional matrix encoding and a tailored dispersal algorithm, the proposed method achieves low complexities across all operations while maintaining optimal communication for data retrieval. The results indicate significant improvements in recovery performance compared to state-of-the-art protocols, making it applicable to various real-world scenarios.
Achieving a balance of low complexities in data dispersal, storage, retrieval, and recovery could redefine efficiency standards in distributed storage systems.
The primary goal of a distributed storage system is to ensure that clients can both write and read data in a reliable and consistent manner, even in the presence of failures. While existing asynchronous verifiable information dispersal (AVID) protocols achieve optimal space complexity for storage and communication complexity for data retrieval in a Byzantine setting, the crucial operations of data dispersal and node recovery have received less attention. We propose an efficient AVID protocol that simultaneously guarantees low complexities for dispersal, storage, retrieval, and recovery. At the core of the proposed protocol lies a novel mechanism to encode data in a two-dimensional matrix and a bespoke dispersal algorithm. The protocol maintains an optimal communication complexity for retrieval while substantially improving upon the state of the art for recovery. Additionally, we describe a protocol variant that offers a reduced space complexity and communication complexity for dispersal, at the expense of a higher communication complexity for recovery and, depending on its parameterization, also retrieval. As the proposed protocols strike a balance across all considered metrics, they are suitable for a broad range of real-world use cases.
