Proceedings of the International Conference on Dependable Systems and Networks (DSN-2004). Palazzo dei Congressi, Florence, Italy. June 28th - July 1, 2004. Supercedes Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-03-104, December, 2003.
Garth R. Goodson, Jay J. Wylie, Gregory R. Ganger, Michael K. Reiter
Parallel Data Laboratory
Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213
This paper describes a decentralized consistency protocol for survivable
storage that exploits local data versioning within each storage-node.
Such versioning enables the protocol to efficiently provide linearizability
and wait-freedom of read and write operations to erasure-coded data
in asynchronous environments with Byzantine failures of clients and
servers. By exploiting versioning storage-nodes, the protocol shifts
most work to clients and allows highly optimistic operation: reads occur
in a single round-trip unless clients observe concurrency or write failures.
Measurements of a storage system prototype using this protocol show
that it scales well with the number of failures tolerated, and its single
request response time compares favorably with an efficient implementation
of Byzantine-tolerant state machine replication.
KEYWORDS: survivable storage, Byzantine fault-tolerance, atomic registers, erasure codes
FULL PAPER: pdf / ps
ORIGINAL TR VERSION OF THIS PAPER: pdf