Files in this item



application/pdfParsimonious Se ... nchronous Environments.pdf (941kB)
(no description provided)PDF


Title:Parsimonious Service Replication for Tolerating Malicious Attacks in Asynchronous Environments
Author(s):Ramasamy, Harigovind Venkatraj
Subject(s):computer science
Abstract:We consider the subject of tolerance of the most severe kind of faults, namely Byzantine faults, through state machine replication in asynchronous environments such as the Internet. In Byzantine-fault-tolerant (BFT) state machine replication, state consistency among the replicas of a service is maintained by first agreeing on the order of requests to be processed (agreement or atomic broadcast phase) and then executing the requests in the agreed-upon order (execution phase). We propose a methodology for constructing asynchronous BFT replication protocols that leverage perceived normal conditions for parsimony and do not compromise correctness even when such perceptions are inaccurate. Parsimony is to be as frugal as possible for a given metric of interest. We apply this methodology to obtain parsimonious protocols that achieve efficiency in three metrics: (1) overall resource use of request execution, (2) message complexity of atomic broadcast, and (3) latency degree of atomic broadcast. We then present a suite of group management protocols that allow for the dynamic change of the composition of the replication group. Our parsimonious protocols are designed to withstand corruptions of at most one-third of the replicas and do not require the removal of suspected faulty replicas in order to provide liveness. Such a design allows for the enforcement of very selective and conservative policies regarding changes to the replication group membership. We describe the implementation of the protocols within a reusable software framework called the Component-Based Framework for Intrusion Tolerance, or CoBFIT. We also present the experimental evaluation of our protocols in the context of a representative application in both LAN and WAN (Planetlab) settings under both fault-free and controlled fault injection scenarios.
Issue Date:2005-12
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2005-2655
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-20

This item appears in the following Collection(s)

Item Statistics