Towards a scalable and robust DHT

ABSTRACT

The problem of scalable and robust distributed data storage has recently attracted a lot of attention. A common approach in the area of peer-to-peer systems has been to use a distributed hash table (or DHT). DHTs are based on the concept of virtual space. Peers and data items are mapped to points in that space, and local-control rules are used to decide, based on these virtual locations, how to interconnect the peers and how to map the data to the peers.DHTs are known to be highly scalable and easy to update as peers enter and leave the system. It is relatively easy to extend the DHT concept so that a constant fraction of faulty peers can be handled without any problems, but handling adversarial peers is very challenging. The biggest threats appear to be join-leave attacks (i.e., adaptive join-leave behavior by the adversarial peers) and attacks on the data management level (i.e., adaptive insert and lookup attacks by the adversarial peers) against which no provably robust mechanisms are known so far. Join-leave attacks, for example, may be used to isolate honest peers in the system, and attacks on the data management level may be used to create a high load-imbalance, seriously degrading the correctness and scalability of the system.We show, on a high level, that both of these threats can be handled in a scalable manner, even if a constant fraction of the peers in the system is adversarial, demonstrating that open systems for scalable distributed data storage that are robust against even massive adversarial behavior are feasible.

REFERENCES

• 1: Helmut Alt , Torben Hagerup , Kurt Mehlhorn , Franco P. Perparata, Deterministic simulation of idealized parallel computers on more realistic ones, SIAM Journal on Computing, v.16 n.5, p.808-835, Oct. 1987 [doi>10.1137/0216053]
• 2: James Aspnes , Gauri Shah, Skip graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: B. Awerbuch and C. Scheideler. Group Spreading: A protocol for provably secure distributed name service. In Proc. of the 31st International Colloquium on Automata, Languages and Programming (ICALP), 2004.
• 4: Miguel Castro , Peter Druschel , Ayalvadi Ganesh , Antony Rowstron , Dan S. Wallach, Secure routing for structured peer-to-peer overlay networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060317]
• 5: 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
• 6: S. Crosby and D. Wallach. Denial of service via algorithmic complexity attacks. In Usenix Security, 2003.
• 7: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
• 8: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 9: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 10: D. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms. Unpublished manuscript, accessible via http://www.cs.unibo.it/~pancones/papers.html, October 20 1998.
• 11: A. Fiat, J. Saia, and M. Young. Making Chord robust to Byzantine attacks. In Proc. of the European Symposium on Algorithms (ESA), 2005.
• 12: Rosario Gennaro , Yuval Ishai , Eyal Kushilevitz , Tal Rabin, The round complexity of verifiable secret sharing and secure multicast, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.580-589, July 2001, Hersonissos, Greece [doi>10.1145/380752.380853]
• 13: Kieran T. Herley , Gianfranco Bilardi, Deterministic Simulations of Prams on Bounded Degree Networks, SIAM Journal on Computing, v.23 n.2, p.276-292, April 1994 [doi>10.1137/S0097539789164765]
• 14: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 15: F. Kuhn, S. Schmid, and R. Wattenhofer. A self-repairing peer-to-peer system resilient to dynamic adversarial churn. In Proc. of the 4th International Workshop on Peer-to-Peer Systems (IPTPS), 2005.
• 16: F. Luccio, A. Pietracaprina, and G. Pucci. A new scheme for the deterministic simulation of PRAMs in VLSI. Algorithmica, 5:529--544, 1990.
• 17: McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pages 195--247. Springer Verlag, Berlin, 1998.
• 18: Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
• 19: Moni Naor , Udi Wieder, Novel architectures for P2P applications: the continuous-discrete approach, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777421]
• 20: S. Nielson, S. Crosby, and D. Wallach. Kill the messenger: A taxonomy of rational attacks. In Proc. of the 4th International Workshop on Peer-to-Peer Systems (IPTPS), 2005.
• 21: Venkata N. Padmanabhan , Kunwadee Sripanidkulchai, The Case for Cooperative Networking, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.178-190, March 07-08, 2002
• 22: C. Greg Plaxton , Rajmohan Rajaraman , Andréa W. Richa, Accessing nearby copies of replicated objects in a distributed environment, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.311-320, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258523]
• 23: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 24: S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz. Handling churn in a DHT. In USENIX Annual Technical Conference, 2004.
• 25: Jared Saia , Amos Fiat , Steven D. Gribble , Anna R. Karlin , Stefan Saroiu, Dynamically Fault-Tolerant Content Addressable Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.270-279, March 07-08, 2002
• 26: Christian Scheideler, How to spread adversarial nodes?: rotate!, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060694]
• 27: Atul Singh , Miguel Castro , Peter Druschel , Antony Rowstron, Defending against eclipse attacks on overlay networks, Proceedings of the 11th workshop on ACM SIGOPS European workshop: beyond the PC, September 19-22, 2004, Leuven, Belgium [doi>10.1145/1133572.1133613]
• 28: Emil Sit , Robert Morris, Security Considerations for Peer-to-Peer Distributed Hash Tables, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.261-269, March 07-08, 2002
• 29: Mudhakar Srivatsa , Ling Liu, Vulnerabilities and Security Threats in Structured Overlay Networks: A Quantitative Analysis, Proceedings of the 20th Annual Computer Security Applications Conference (ACSAC'04), p.252-261, December 06-10, 2004 [doi>10.1109/CSAC.2004.50]
• 30: Tyron Stading , Petros Maniatis , Mary Baker, Peer-to-Peer Caching Schemes to Address Flash Crowds, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.203-213, March 07-08, 2002
• 31: Angelos Stavrou , Dan Rubenstein , Sambit Sahu, A Lightweight, Robust P2P System to Handle Flash Crowds, Proceedings of the 10th IEEE International Conference on Network Protocols, p.226-235, November 12-15, 2002
• 32: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 33: Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987 [doi>10.1145/7531.7926]
• 34: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory

Keywords:
overlay networks, peer-to-peer systems, robustness