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_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
  @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_33: 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.
  @cite_41: 
  @cite_42: 
  @cite_23: We present a new distributed data replication algorithm tailored especially for large-scale read write data objects such as files. The algorithm guarantees atomic data consistency, while incurring low latency costs. The key idea of the algorithm is to maintain copies of the data objects separately from information about the locations of up-to-date copies. Because it performs most of its work using only the location information, our algorithm needs to access only a few copies of the actual data; specifically, only one copy during a read and only f+1 copies during a write, where f is an assumed upper bound on the number of copies that can fail. These bounds are optimal. The algorithm works in an asynchronous message-passing environment. It does not use additional mechanisms such as group communication or distributed locking. It is suitable for implementation in WANs as well as LANs. We also present two lower bounds on the costs of data replication. The first lower bound is on the number of low-level writes required during a read operation on the data. The second bound is on the minimum space complexity of a class of efficient replication algorithms. These lower bounds suggest that some of the techniques used in our algorithm are necessary. They are also of independent interest.
  @cite_49: It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contention. This paper initiates the first study of quorum systems that help design such implementations by encompassing, at the same time, optimal resilience (just like traditional quorum systems), as well as optimal best-case complexity (unlike traditional quorum systems). We introduce the notion of a refined quorum system (RQS) of some set S as a set of three classes of subsets (quorums) of S: firstclass quorums are also second class quorums, themselves being also third class quorums. First class quorums have large intersections with all other quorums, second class quorums typically have smaller intersections with those of the third class, the latter simply correspond to traditional quorums. Intuitively, under uncontended and synchronous conditions, a distributed object implementation would expedite an operation if a quorum of the first class is accessed, then degrade gracefully depending on whether a quorum of the second or the third class is accessed. Our notion of refined quorum system is devised assuming a general adversary structure, and this basically allows relying on refined quorum systems to relax the assumption of independent process failures, often questioned in practice. We illustrate the power of refined quorums by introducing two new optimal Byzantine-resilient distributed object implementations: anatomic storage and a consensus algorithm. Both match previously established resilience and best-case complexity lower bounds, closing open gaps, as well as new complexity bounds we establish here.
  @cite_5: This paper presents an algorithm that emulates atomic read write shared objects in a dynamic network setting. To ensure availability and faulttolerance, the objects are replicated. To ensure atomicity, reads and writes are performed using quorum configurations, each of which consists of a set of members plus sets of read-quorums and write-quorums. The algorithm is reconfigurable: the quorum configurations may change during computation, and such changes do not cause violations of atomicity. Any quorum configuration may be installed at any time. The algorithm tolerates processor stopping failure and message loss. The algorithm performs three major tasks, all concurrently: reading and writing objects, introducing new configurations, and "garbage-collecting" obsolete configurations. The algorithm guarantees atomicity for arbitrary patterns of asynchrony and failure. The algorithm satisfies a variety of conditional performance properties, based on timing and failure assumptions. In the "normal case", the latency of read and write operations is at most 8d, where d is the maximum message delay.
  @cite_47: Phalanx is a software system for building a persistent, survivable data repository that supports shared data abstractions (e.g., variables, mutual exclusion) for clients. Phalanx implements data abstraction that ensures useful properties without trusting the servers supporting these abstractions or the clients accessing them, i.e., Phalanx can survive even the arbitrarily malicious corruption of clients and (some number of) servers. At the core of the system are survivable replication techniques that enable efficient scaling to hundreds of Phalanx servers. In this paper we describe the implementation of some of the data abstractions provided by Phalanx, discuss their ability to scale to large systems, and describe an example application.
  @cite_13: Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures. These results make it possible to view the shared-memory model as a higher-level language for designing algorithms in asynchronous distributed systems. Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected. The overhead introduced by these emulations is polynomial in the number of processors in the system. Immediate new results are obtained by applying the emulators to known shared-memory algorithms. These include, among others, protocols to solve the following problems in the message-passing model in the presence of processor or link failures: multi-writer multi-reader registers, concurrent time-stamp systems, l -exclusion, atomic snapshots, randomized consensus, and implementation of data structures.
summary: A seminal crash-tolerant read write storage implementation assuming a majority of correct processes was presented in @cite_13 . In the original single-writer variant of @cite_13 , read operations always take 2 rounds between a client and servers with write-backs in the second round. On the other hand all write operations complete in a single round; in the multi-writer variant @cite_5 , the second write round is necessary. Server state modifications by readers introduced by @cite_13 are unavoidable; namely, @cite_23 showed a @math lower bound on the number of servers that a reader has to modify in any wait-free linearizable storage. However, robust storage implementations differ in the strategy employed by readers: in some protocols readers write-back data (e.g., @cite_13 @cite_47 @cite_42 @cite_37 @cite_49 @cite_33 ) whereas in others readers only write metadata to servers (e.g., @cite_23 @cite_18 @cite_41 ).