text: 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.
  @cite_18: We study efficient and robust implementations of an atomic read-write data structure over an asynchronous distributed message-passing system made of reader and writer processes, as well as a number of servers implementing the data structure. We determine the exact conditions under which every read and write involves one round of communication with the servers. These conditions relate the number of readers to the tolerated number of faulty servers and the nature of these failures.
  @cite_37: 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
summary: 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.