CMU-CS-03-187
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-03-187

Byzantine-Tolerant Erasure-Coded Storage

Garth R. Goodson, Jay J. Wylie, Gregory R. Ganger, Michael K. Reiter

September 2003

CMU-CS-03-187.ps
CMU-CS-03-187.pdf


Keywords: Survivable storage, Byzantine fault-tolerance, atomic registers, erasure codes


This paper describes a decentralized consistency protocol for survivable storage that exploits data versioning within storage-nodes. 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. Exploiting versioning storage-nodes, the protocol shifts most work to clients. Reads occur in a single round-trip unless clients observe concurrency or write failures. Measurements of a storage system using this protocol show that the protocol scales well with the number of failures tolerated, and that it outperforms a highly-tuned instance of Byzantine-tolerant state machine replication.

pages


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu