Existing Byzantine fault tolerant (BFT) storage solutions that achieve strong consistency and high availability, are costly compared to solutions that tolerate simple crashes. This cost is one of the main obstacles in deploying BFT storage in practice. In this paper, we present PoWerStore, a robust and efficient data storage protocol. PoWerStore's robustness comprises tolerating network outages, maximum number of Byzantine storage servers, any number of Byzantine readers and crash-faulty writers, and guaranteeing high availability (wait-freedom) and strong consistency (linearizability) of read/write operations. PoWerStore's efficiency stems from combining lightweight cryptography, erasure coding and metadata write-backs, where readers write-back only metadata to achieve strong consistency. Central to PoWerStore is the concept of “Proofs of Writing” (PoW), a novel data storage technique inspired by commitment schemes. PoW rely on a 2-round write procedure, in which the first round writes the actual data and the second round only serves to “prove” the occurrence of the first round. PoW enable efficient implementations of strongly consistent BFT storage through metadata write-backs and low latency reads. We implemented PoWerStore and show its improved performance when compared to state of the art robust storage protocols, including protocols that tolerate only crash faults.

Besides well-known benefits, commodity cloud storage also raises concerns that include security, reliability, and consistency. We present Hybris key-value store, the first robust hybrid cloud storage system, aiming at addressing these concerns leveraging both private and public cloud resources. Hybris robustly replicates metadata on trusted private premises (private cloud), separately from data, which are dispersed (using replication or erasure coding) across multiple untrusted public clouds. Hybris maintains metadata stored on private premises at the order of few dozens of bytes per key, avoiding the scalability bottleneck at the private cloud. In turn, the hybrid design allows Hybris to efficiently and robustly tolerate cloud outages but also potential malice in clouds without overhead. Namely, to tolerate up to f malicious clouds, in the common case of the Hybris variant with data replication, writes replicate data across f +1 clouds, whereas reads involve a single cloud. In the worst case, only up to f additional clouds are used. This is considerably better than earlier multi-cloud storage systems that required costly 3 f +1 clouds to mask f potentially malicious clouds. Finally, Hybris leverages strong metadata consistency to guarantee to Hybris applications strong data consistency without any modifications to the eventually consistent public clouds. We implemented Hybris in Java and evaluated it using a series of micro and macro-benchmarks. Our results show that Hybris significantly outperforms comparable multi-cloud storage systems and approaches the performance of bare-bone commodity public cloud storage.

Besides well-known benefits, commodity cloud storage also raises concerns that include security, reliability, and consistency. We present Hybris key-value store, the first robust hybrid cloud storage system, aiming at addressing these concerns leveraging both private and public cloud resources.

Existing Byzantine fault tolerant (BFT) storage solutions that achieve strong consistency and high availability, are costly compared to solutions that tolerate simple crashes. This cost is one of the main obstacles in deploying BFT storage in practice.

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. © 2011 ACM.

So far, all implementations providing fork-consistent semantics are based on objects with read-modify-write capabilities (also termed servers). We propose constructions of fork-consistent shared objects from single-writer multiple-reader(SWMR) read/write base registers, that are strictly weaker than servers. Our shared object constructions provide linearizability if all base registers behave correctly, and gracefully degrade to either fork-linearizability or weak fork-linearizability if any number of registers fails Byzantine. We make the following contributions: (a) A fork-linearizable construction of a universal type where operations are allowed to abort under concurrency, and (b) a weak fork-linearizable implementation of a shared memory that ensures wait-freedom when the registers are correct.

Byzantine-Fault-Tolerant (BFT) state machine replication is an appealing technique to tolerate arbitrary failures. However, Byzantine agreement incurs a fundamental trade-off between being fast (i.e. optimal latency) and achieving optimal resilience (i.e. 2f + b + 1 replicas, where f is the bound on failures and b the bound on Byzantine failures). Achieving fast Byzantine replication despite f failures requires at least f + b - 2 additional replicas. In this paper we show, perhaps surprisingly, that fast Byzantine agreement despite f failures is practically attainable using only b - 1 additional replicas, which is independent of the number of crashes tolerated. This makes our approach particularly appealing for systems that must tolerate many crashes (large f) and few Byzantine faults (small b). The core principle of our approach is to have replicas agree on a quorum of responsive replicas before agreeing on requests. This is key to circumventing the resilience lower bound of fast Byzantine agreement.

Linearizability is the strongest known consistency property of shared objects. In asynchronous message passing systems, Linearizability can be achieved with ◊S and a majority of correct processes. In this paper we introduce the notion of Eventual Linearizability, the strongest known consistency property that can be attained with ◊S and any number of crashes. We show that linearizable shared object implementations can be augmented to support weak operations, which need to be linearized only eventually. Unlike strong operations that require to be always linearized, weak operations terminate in worst case runs. However, there is a tradeoff between ensuring termination of weak and strong operations when processes have only access to ◊S. If weak operations terminate in the worst case, then we show that strong operations terminate only in the absence of concurrent weak operations. Finally, we show that an implementation based on P exists that guarantees termination of all operations.

We address the problem of message-parsimonious asynchronous atomic broadcast when a subset t out of n parties may exhibit byzantine behavior. Message parsimony involves using only the optimal O(n) message exchanges per atomically delivered payload in the normal case. Message parsimony is desirable for Internet-like deployment environments in which message loss rates are non-negligible. Protocol PABC, the only previously-known message-parsimonious solution, suffered from two limitations vis-a-vis the solutions with O(n2) message complexity: more communication steps and the use of digital signatures. We present a protocol termed AMP that for the first time provides signature-free message parsimony while at the same time reducing the number of communication steps to the minimum necessary. In contrast to many previous atomic broadcast solutions, our protocol satisfies both safety and liveness in the asynchronous model.

In the asynchronous distributed system model, consensus is obtained in one communication step if all processes propose the same value. Assumingf \lt n/3, this is regardless of the failure detector output. A zero-degrading protocol reaches consensus in two communication steps in every stable run, i.e., when the failure detector makes no mistakes and its output does not change. We show that no leaderbased consensus protocol can be simultaneously one-step and zero-degrading. We propose two approaches to circumvent the impossibility result and present corresponding consensus protocols. Further, we present an atomic broadcast protocol that has a latency of 3d in every stable run and a latency of 2d in case of no collisions. Finally, we evaluate its performance in a cluster of workstations.