BAR Fault Tolerance for Cooperative ServicesAmitanand S. Aiyer, Lorenzo Alvisi, Allen ClementMike Dahlin, Jean-Philippe Martin, Carl PorthUniversity of Texas at Austin - Dept. of Computer Science1 University Station C0500Austin, Texas{anand,lorenzo,aclement,dahlin,jpmartin,elite}@cs.utexas.eduABSTRACTThis paper describes a general approach to constructing cooperativeservices that span multiple administrative domains. In such envi-ronments, protocols must tolerate both Byzantine behaviors whenbroken, misconfigured, or malicious nodes arbitrarily deviate fromtheir specification and rational behaviors when selfish nodes de-viate from their specification to increase their local benefit. Thepaper makes three contributions: (1) It introduces the BAR (Byzan-tine, Altruistic, Rational) model as a foundation for reasoning aboutcooperative services; (2) It proposes a general three-level architec-ture to reduce the complexity of building services under the BARmodel; and (3) It describes an implementation of BAR-B, the firstcooperative backup service to tolerate both Byzantine users and anunbounded number of rational users. At the core of BAR-B is anasynchronous replicated state machine that provides the custom-ary safety and liveness guarantees despite nodes exhibiting bothByzantine and rational behaviors. Our prototype provides accept-able performance for our application: our BAR-tolerant state ma-chine executes 15 requests per second, and our BAR-B backup ser-vice can back up 100 MB of data in under 4 minutes.Categories and Subject DescriptorsC.2.4 [COMPUTER-COMMUNICATION NETWORKS]: Dis-tributed SystemsGeneral TermsALGORITHMS, RELIABILITYKeywordsGame theory, Byzantine fault tolerance, Reliable systems, Peer toPeerThis work was supported in part by NSF award CNS 0509338 and NSFCyberTrust award 0430510. Lorenzo Alvisi was also supported by anAlfred P. Sloan Fellowhip.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SOSP’05, October 23–26, 2005, Brighton, United Kingdom.Copyright 2005 ACM 1-59593-079-5/05/0010 ...$5.00.1. INTRODUCTIONThis paper describes a general approach to constructing cooper-ative services that span multiple administrative domains (MADs).In a cooperative service, nodes collaborate to provide some servicethat benefits each node, but there is no central authority that con-trols the nodes’ actions. Examples of such services include Internetrouting [21, 59], wireless mesh routing [33], file distribution [14],archival storage [38], or cooperative backup [5, 16, 31]. As MADdistributed systems become more commonplace, developing a solidfoundation for constructing this class of services becomes increas-ingly important.There currently exists no satisfactory way to model MAD ser-vices. In these systems, the classical dichotomy between correctand faulty nodes [56] becomes inadequate. Nodes in MAD systemsmay depart from protocols for two distinct reasons. First, as in tra-ditional systems, nodes may be broken and arbitrarily deviate froma protocol because of component failure, misconfiguration, securitycompromise, or malicious intent. Second, nodes may be selfish andalter the protocol in order to increase their utility [1, 27]. Byzan-tine Fault Tolerance (BFT) [10, 30, 36] handles the first class ofdeviations well. However, the Byzantine model classifies all devi-ations as faults and requires a bound on the number of faults in thesystem; this bound is not tenable in MAD systems where all nodesmay benefit from selfish behavior and be motivated to deviate fromthe protocol. Models that only account for selfish behavior [59]handle the second class of deviations, but may be vulnerable to ar-bitrary disruptions if even a single node is broken and deviates fromexpected rational behavior.Given the potential for nodes to develop arbitrarily subtle tactics,it is not sufficient to verify experimentally that a protocol toleratesa collection of attacks identified by the protocol’s creator. Instead,just as for authentication systems [8] or Byzantine-tolerant proto-cols [30], it is necessary to design protocols that provably meettheir goals, no matter what strategies nodes may concoct within thescope of the adversary model.To allow construction of such protocols, we define a model thatcaptures the essential aspects of MADs. The Byzantine-Altruistic-Rational (BAR) model accommodates three classes of nodes. Ra-tional [59] nodes participate in the system to gain some net benefitand can depart from a proposed program in order to increase theirnet benefit. Byzantine [10, 30, 36] nodes can depart arbitrarily froma proposed program whether it benefits them or not. Finally, BARaccommodates the presence of altruistic [46] nodes that executea proposed program even if the rational choice is to deviate. Aprotocol is BAR Tolerant (BART) if it provably provides to its non-Byzantine participants a set of desired safety and liveness proper-ties. In this paper, we focus on BART protocols that do not dependon the existence of altruistic nodes in the system: we assume that atmostn−23of the nodes in the system are Byzantine and that everynon-Byzantine node is rational.A key question is whether useful systems can be built under theBAR model. To answer this question, we develop a general three-level architecture for BART services. The bottom level implementsa small set of key abstractions (e.g., state machine replication andterminating reliable broadcast) that simplify implementing and rea-soning about BART distributed services. The middle level parti-tions and assigns work to individual nodes. Finally, the top levelimplements the application-specific aspects of BART services (e.g.,verifying that responses to requests conform to application seman-tics.)We use this architecture to construct BAR-B, a BART coopera-tive backup service. BAR-B is targeted at environments—such asa group of students in a dorm, home machines for researchers in agroup, or machines donated to non-profit organizations [32]—that,by supporting a notion of identity that is “expensive” to obtain,avoid the Sybil attack [18]. We do not target open membershippeer-to-peer systems.We