Remote storage with byzantine servers

ABSTRACT

We consider the problem of providing byzantine-tolerant storage in distributed systems where client-server links are much thinner and slower than server-server links. We provide storage algorithms that are unique in two ways. First, our algorithms take into consideration the asymmetry in network connectivity by minimizing client-server communication. To provide this property, we rely on a small amount of partial (eventual) synchrony. Second, our algorithms provide a new property called limited effect, which is important for storage systems. To provide the latter property, we use synchronized clocks, which are increasingly common due to GPS devices and NTP, even in otherwise "asynchronous systems" like the Internet. We present two algorithms called QUAD and LINEAR, which provide a trade-off between failure resiliency and efficiency. Our algorithms implement an abortable register [3], which is an abstraction used in some real storage systems, but abortable registers are weaker than atomic registers. Thus, one might wonder if we could have implemented atomic registers instead. We answer this question in the negative: we prove that there are no implementations of atomic registers that provide the limited effect property in systems with failures, even with synchronized clocks.

REFERENCES

• 1: Michael Abd-El-Malek , Gregory R. Ganger , Garth R. Goodson , Michael K. Reiter , Jay J. Wylie, Fault-scalable Byzantine fault-tolerant services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 2: Ittai Abraham , Gregory Chockler , Idit Keidar , Dahlia Malkhi, Wait-free regular storage from Byzantine components, Information Processing Letters, v.101 n.2, p.60-65, January, 2007 [doi>10.1016/j.ipl.2006.07.012]
• 3: Marcos K. Aguilera , Svend Frolund , Vassos Hadzilacos , Stephanie L. Horn , Sam Toueg, Abortable and query-abortable objects and their efficient implementation, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281107]
• 4: A. S. Aiyer, L. Alvisi, and R. A. Bazzi. Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions. In International Symposium on Distributed Computing, pages 7--19, Sept. 2007.
• 5: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 6: H. Attiya and A. Bar-Or. Sharing memory with semi-byzantine clients and faulty storage servers. Parallel Processing Letters, 16(4):419--428, Dec. 2006.
• 7: Christian Cachin , Stefano Tessaro, Optimal Resilience for Erasure-Coded Byzantine Distributed Storage, Proceedings of the International Conference on Dependable Systems and Networks, p.115-124, June 25-28, 2006 [doi>10.1109/DSN.2006.56]
• 8: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 9: Gregory Chockler , Dahlia Malkhi, Active disk paxos with infinitely many processes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571837]
• 10: James Cowling , Daniel Myers , Barbara Liskov , Rodrigo Rodrigues , Liuba Shrira, HQ replication: a hybrid quorum protocol for byzantine fault tolerance, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 11: Partha Dutta , Svend Frølund , Rachid Guerraoui , Bastian Pochon, An Efficient Universal Construction for Message-Passing Systems, Proceedings of the 16th International Conference on Distributed Computing, p.133-147, October 28-30, 2002
• 12: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 13: Svend Frolund , Arif Merchant , Yasushi Saito , Susan Spence , Alistair Veitch, A Decentralized Algorithm for Erasure-Coded Virtual Disks, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.125, June 28-July 01, 2004
• 14: Garth R. Goodson , Jay J. Wylie , Gregory R. Ganger , Michael K. Reiter, Efficient Byzantine-Tolerant Erasure-Coded Storage, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.135, June 28-July 01, 2004
• 15: Danny Hendler , Nir Shavit, Operation-valency and the cost of coordination, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.84-91, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872047]
• 16: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 17: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 18: Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin , Allen Clement , Edmund Wong, Zyzzyva: speculative byzantine fault tolerance, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 19: Dahlia Malkhi , Michael K. Reiter, Secure and Scalable Replication in Phalanx, Proceedings of the The 17th IEEE Symposium on Reliable Distributed Systems, p.51, October 20-23, 1998
• 20: Jean-Philippe Martin , Lorenzo Alvisi , Michael Dahlin, Minimal Byzantine Storage, Proceedings of the 16th International Conference on Distributed Computing, p.311-325, October 28-30, 2002
• 21: David L. Mills, Computer Network Time Synchronization: The Network Time Protocol, CRC Press, Inc., Boca Raton, FL, 2006
• 22: Svend Frølund , Arif Merchant , Yasushi Saito , Susan Spence , Alistair Veitch, FAB: enterprise storage systems on a shoestring, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.29-29, May 18-21, 2003, Lihue, Hawaii
• 23: Yasushi Saito , Svend Frølund , Alistair Veitch , Arif Merchant , Susan Spence, FAB: building distributed enterprise disk arrays from commodity components, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Algorithms, Design, Reliability, Security, Theory

Keywords:
algorithms, byzantine failures, digital signatures, distributed storage, distributed system