We present PoWerStore, the first efficient robust storage protocol that achieves optimal latency without using digital signatures. PoWerStore's robustness comprises tolerating asynchrony, maximum number of Byzantine storage servers, any number of Byzantine readers and crash-faulty writers, and guaranteeing wait-freedom and linearizability of read write operations. PoWerStore's efficiency stems from combining lightweight authentication, erasure coding and metadata write-backs where readers write-back only metadata to achieve linearizability. At the heart of PoWerStore are Proofs of Writing (PoW): a novel storage technique based on lightweight cryptography. PoW enable reads and writes in the single-writer variant of PoWerStore to have latency of 2 rounds of communication between a client and storage servers in the worst-case (which we show optimal). We further present and implement a multi-writer PoWerStore variant featuring 3-round writes reads where the third read round is invoked only under active attacks, and show that it outperforms existing robust storage protocols, including crash-tolerant ones.
Data write-backs are also not needed in case of robust storage implementations that feature single round reads and writes @cite_18 . Namely, @cite_18 presents fast single-writer crash-tolerant and BFT storage implementations in which readers only write metadata reading data in the single round of read and hence, without any write-back. However, fast implementations are fundamentally limited and cannot be optimally resilient, since the number of required servers is inherently linear in number of readers @cite_18 . The limitation on the number of readers of @cite_18 was relaxed in @cite_37 , where a single-writer crash-tolerant robust linearizable storage implementation was presented, in which most of the reads complete in a single round, yet a fraction of reads is permitted to be slow'' and complete in 2 rounds.
@cite_18 @cite_37
2086186470 1967118107
We study the time-complexity of robust atomic read write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures (optimal resilience) without relying on data authentication. We show that no single-writer multiple-reader (SWMR) robust atomic storage implementation exists if (a) read operations complete in less than four communication round-trips (rounds), and (b) the time complexity of write operations is constant. More precisely, we present two lower bounds. The first is a read lower bound stating that three rounds of communication are necessary to read from a SWMR robust atomic storage. The second is a write lower bound, showing that (log(t)) write rounds are necessary to read in three rounds from such a storage. Applied to known results, our lower bounds close a fundamental gap: we show that time-optimal robust atomic storage can be obtained using well-known transformations from regular to atomic storage and existing time-optimal regular storage implementations. This paper investigates time-efficient implementations of atomic read-write registers in message-passing systems where the number of readers can be unbounded. In particular we study the case of a single writer, multiple readers, and S servers, such that the writer, any subset of the readers, and up to t servers may crash. A recent result of [P. Dutta, R. Guerraoui, R.R. Levy, A. Chakraborty, How fast can a distributed atomic read be? In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing, 2004, pp. 236-245] shows how to obtain fast implementations in which both reads and writes complete in one communication round-trip, under the constraint that the number of readers is less than St-2, where t