We are increasingly relying on online services to store, access, share, and disseminate critical information from anywhere and at all times. Such services include email, digital storage, photos, video, health and financial services, etc. With increasing evidence of non-fail-stop failures in practical systems, Byzantine fault tolerant state machine replication technique is becoming increasingly attractive for building highlyreliable services in order to tolerate such failures. However, existing Byzantine fault tolerant techniques fall short of providing high availability, high performance, and long-term data durability guarantees with competitive replication cost. In this dissertation, we present BFT replication techniques that facilitate the design and implementation of such highly-reliable services by providing high availability, high performance and high durability with competitive replication cost (hardware, software, network, management). First, we propose CBASE, a BFT state machine replication architecture that leverages application-level parallelism to improve throughput of the replicated system by identifying and executing independent requests concurrently. Traditional state machine replication based Byzantine fault tolerant (BFT) techniques provide high availability and security but fail to provide high throughput. This limitation stems from the fundamental assumption of generalized state machine replication techniques that all replicas execute requests sequentially in the same total order to ensure consistency across replicas. Our architecture thus provides a general way to exploit application parallelism in order to provide high throughput without compromising correctness. Second, we present Zyzzyva, an efficient BFT agreement protocol that uses speculation to significantly reduce the performance overhead and replication cost of BFT state machine replication. In Zyzzyva, replicas respond to a client’s request without first running an expensive three-phase commit protocol to reach agreement on the order in which the request must be processed. Instead, they optimistically adopt the order proposed by the primary and respond immediately to the client. Replicas can thus become temporarily inconsistent with one another, but clients detect inconsistencies, help correct replicas converge on a single total ordering of requests, and only rely on responses that are consistent with this total order. This approach allows Zyzzyva to reduce replication overheads to near their theoretical minima. Third, we design and implement SafeStore, a distributed storage system designed to maintain long-term data durability despite conventional hardware and software faults, environmental disruptions, and administrative failures caused by human error or malice. The architecture of SafeStore is based on fault isolation, which SafeStore applies aggressively along administrative, physical, and temporal dimensions by spreading data across autonomous storage service providers (SSPs). SafeStore also performs an efficient end-to-end audit of SSPs to detect data loss quickly and improve data durability by reducing MTTR. SafeStore offers durable storage with cost, performance, and availability competitive with traditional storage systems. We evaluate these techniques by implementing BFT replication libraries and further demonstrate the practicality of these approaches by implementing an NFS based replicated file system(CBASE-FS) and a durable storage system (SafeStore-FS). / text

published_or_final_version / Computer Science / Master / Master of Philosophy

No description available.

No description available.

This work proposes some generic approaches to offer transparency and efficiency to checkpoint-recovery implementations on Windows. On the one hand, a complete environment is proposed to prepare Windows to incorporate transparently any checkpoint-recovery implementation whose architecture respects a simple contract of reusability. The environment allows any application to use some checkpoint-recovery services with only the default process creation mechanisms offered by Windows. Moreover, it handles automatically the recovery of the processes in case of a crash and requires no human intervention in most scenarios. On the other hand, an optimization module is proposed to minimize the checkpointing time and to slow its degradation in situations of high checkpoint-recovery demands. The results show an excellent control of the checkpoint cost degradation and sometimes the complete absence of the penalty associated with concurrent checkpoint requests.

Thesis (Ph. D.)--Computing, Georgia Institute of Technology, 2008. / Committee Chair: Harrold, Mary Jean; Committee Member: Orso, Alessandro; Committee Member: Pande, Santosh; Committee Member: Reiss, Steven; Committee Member: Rugaber, Spencer.

Thesis (Ph. D.)--University of Texas at Austin, 2008. / Vita. Includes bibliographical references.

Thesis (Ph. D., Computer Science)--University of Idaho, August 20, 2008. / Major professor: Jim Alves-Foss. Includes bibliographical references (leaves 105-110). Also available online (PDF file) by subscription or by purchasing the individual file.

Thesis (M. Phil.)--University of Hong Kong, 1991.

Thesis supervisor: Sukumar Ghosh. Includes bibliographic references (p. 136-140).