ABSTRACT Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-03-105, March, 2004. The Safety and Liveness Properties of a Protocol Family for Versatile Garth R. Goodson, Jay J. Wylie, Gregory R. Ganger, Michael K. Reiter Parallel Data Laboratory Survivable storage systems mask faults. A protocol family shifts the decision of which types of faults from implementation time to data-item creation time. If desired, each data-item can be protected from different types and numbers of faults with changes only to client-side logic. This paper presents proofs of the safety and liveness properties for a family of storage access protocols that exploit data versioning to efficiently provide consistency for erasure-coded data. Members of the protocol family may assume either a synchronous or asynchronous model, can tolerate hybrid crash-recovery and Byzantine failures of storage-nodes, may tolerate either crash or Byzantine clients, and may or may not allow clients to perform repair. Additional protocol family members for synchronous systems under omission and fail-stop failure models of storage-nodes are developed. KEYWORDS: survivable storage, Byzantine fault-tolerance, crash-recovery failures, omission failures, fail-stop failures, hybrid failure models, atomic registers, erasure codes |
