Thumbnail
Access Restriction
Open

Author Aiyer, Amitanand S. ♦ Alvisi, Lorenzo ♦ Clement, Allen ♦ Dahlin, Mike ♦ Martin, Jean-Philippe ♦ Porth, Carl
Source CiteSeerX
Content type Text
Publisher ACM
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Byzantine User ♦ Building Service ♦ Unbounded Number ♦ Multiple Administrative Domain ♦ Local Benefit ♦ Selfish Node ♦ Rational Behavior ♦ Rational User ♦ Bar Model ♦ Liveness Guarantee ♦ Bar-tolerant State Machine ♦ Byzantine Behavior ♦ Asynchronous Replicated State Machine ♦ General Three-level Architecture ♦ Bar Fault Tolerance ♦ Acceptable Performance ♦ General Approach ♦ Bar-b Backup Service ♦ Cooperative Service ♦ Customary Safety ♦ First Cooperative Backup Service ♦ Malicious Node
Description This paper describes a general approach to constructing cooperative services that span multiple administrative domains. In such environments, protocols must tolerate both Byzantine behaviors when broken, misconfigured, or malicious nodes arbitrarily deviate from their specification and rational behaviors when selfish nodes deviate from their specification to increase their local benefit. The paper makes three contributions: (1) It introduces the BAR (Byzantine, Altruistic, Rational) model as a foundation for reasoning about cooperative services; (2) It proposes a general three-level architecture to reduce the complexity of building services under the BAR model; and (3) It describes an implementation of BAR-B, the first cooperative backup service to tolerate both Byzantine users and an unbounded number of rational users. At the core of BAR-B is an asynchronous replicated state machine that provides the customary safety and liveness guarantees despite nodes exhibiting both Byzantine and rational behaviors. Our prototype provides acceptable performance for our application: our BAR-tolerant state machine executes 15 requests per second, and our BAR-B backup service can back up 100 MB of data in under 4 minutes.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2005-01-01
Publisher Institution IN SOSP’05 20TH ACM SYMPOSIUM ON OPERATING SYSTEMS PRINCIPLES (P