Automatic Reconfiguration for Large-Scale Reliable Storage Systems

Download: pdf.

“Automatic Reconfiguration for Large-Scale Reliable Storage Systems” by Rodrigo Rodrigues, Barbara Liskov, Kathryn Chen, Moses Liskov, and David Schultz. IEEE Transactions on Dependable and Secure Computing, vol. 9, no. 2, Mar. 2012, pp. 146-158.


Byzantine-fault-tolerant replication enhances the availability and reliability of Internet services that store critical state and preserve it despite attacks or software errors. However, existing Byzantine-fault-tolerant storage systems either assume a static set of replicas, or have limitations in how they handle reconfigurations (e.g., in terms of the scalability of the solutions or the consistency levels they provide). This can be problematic in long-lived, large-scale systems where system membership is likely to change during the system lifetime. In this paper, we present a complete solution for dynamically changing system membership in a large-scale Byzantine-fault-tolerant system. We present a service that tracks system membership and periodically notifies other system nodes of membership changes. The membership service runs mostly automatically, to avoid human configuration errors; is itself Byzantine-fault-tolerant and reconfigurable; and provides applications with a sequence of consistent views of the system membership. We demonstrate the utility of this membership service by using it in a novel distributed hash table called dBQS that provides atomic semantics even across changes in replica sets. dBQS is interesting in its own right because its storage algorithms extend existing Byzantine quorum protocols to handle changes in the replica set, and because it differs from previous DHTs by providing Byzantine fault tolerance and offering strong semantics. We implemented the membership service and dBQS. Our results show that the approach works well, in practice: the membership service is able to manage a large system and the cost to change the system membership is low.

Download: pdf.

BibTeX entry:

   author = {Rodrigo Rodrigues and Barbara Liskov and Kathryn Chen and
	Moses Liskov and David Schultz},
   title = {Automatic Reconfiguration for Large-Scale Reliable Storage
   journal = {IEEE Transactions on Dependable and Secure Computing},
   volume = {9},
   number = {2},
   pages = {146--158},
   month = mar,
   year = {2012}

Also see all authors, all publications by date, and all publications by topic.

Programming Methodology Group