Byzantine-Tolerant Erasure-Coded Storage

reportActive / Technical Report | Accession Number: ADA490141 | Open PDF

Abstract:

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.

Author(s):
Goodson, Garth R. ; Wylie, Jay J. ; Ganger, Gregory R. ; Reiter, Michael K.
Author Organization(s):
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Descriptive Note:
Research paper
Supplementary Note:
Sponsored in part by the Defense Advanced Research Projects Agency (DARPA).
Pagination:
0025

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release
Distribution Statement:
Approved For Public Release; Distribution Is Unlimited.

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
CMU-CS-03-187
Contract/Grant Number(s):
F49620-01-1-0433, F30602-99-2-0539
Monitor Series:
AFRL
 Subject Terms
Joint Capability Areas:
JCA_6_Net Centric; JCA_6.1.3_Switching and Routing; JCA_6.1_Information Transport; JCA_6.2.3_Core Enterprise Services; JCA_4.3_Maintain; JCA_6.2.1_Information Sharing; JCA_6.2.2_Computing Services; JCA_6.2_Enterprise Services; JCA_1.2.7_Experimentation; JCA_5_Command and Control; JCA_6.4.1_Secure Information Exchange; JCA_6.4.2_Protect Data and Networks; JCA_5.3_Planning; JCA_6.4_Information Assurance; JCA_8_Building Partnerships; JCA_3.2_Engagement; JCA_3_Force Application; JCA_8.2_Shape
Modernization Areas:
Cyber
Communities of Interest:
Cyber
Descriptor(s):
*COMMUNICATIONS PROTOCOLS, *CLIENT SERVER SYSTEMS, *DECENTRALIZATION, *FAULT TOLERANT COMPUTING, *CONSISTENCY, *INPUT OUTPUT PROCESSING, *DATA STORAGE SYSTEMS, REPLICAS, REDUNDANCY, CODING, NODES, FAILURE, PERFORMANCE(ENGINEERING), ASYNCHRONOUS SYSTEMS, HIGH LEVEL ARCHITECTURE, DISTRIBUTED DATA PROCESSING, SURVIVABILITY
Field(s)/Group(s):
Computer Programming and Software, Computer Hardware, Computer Systems
Keyword(s):
*DATA VERSIONING, *CONSISTENCY PROTOCOLS, *SURVIVABLE STORAGE, BYZANTINE FAULT TOLERANCE, ATOMIC REGISTERS, ERASURE CODING, READ WRITE OPERATIONS, PSEUDO CODES, SCALABILITY, CONCURRENCY, OFFLOADING, PASIS SYSTEM, STORAGE NODES
Report Date:
2003 Sep 01
Creation Date:
2008 Dec 17