1.1 A home on the Internet — Ludovic Courtès — Peer-to-Peer Distributed Storage
  • Opportunistic Use of Content Addressable Storage for Distributed File Systems [tolia03:opportunistic]
    Niraj Tolia, Michael Kozuch, Mahadev Satyanarayanan, Brad Karp, Thomas Bressoud, Adrian Perrig (Intel Research, Pittsburgh; Carnegie Mellon University; Denison University (USA)), Proceedings of the USENIX Annual Technical Conference, 2003

    An ode to content-addressable storage (CAS). The authors propose the use of recipes adverted by CAS providers so that users can adapt to the CAS providers encountered (e.g. use the right hash functions.). See also other papers on CAS at the author's web page.

  • Towards an Archival Intermemory [goldberg98:intermemory]
    Andrew V. Goldberg, Peter N. Yianilos (NEC Research Institute, Inc., NJ, USA), Proceedings IEEE International Forum on Research and Technology Advances in Digital Libraries (ADL'98), April 1998

    This paper describes the design of an hypothetical archival storage such that "the probability of losing an old memory given random node failures is vanishingly small". The archival system presented works at the block level (like, e.g., Venti), and assumes a write-once model (again, like Venti). It addresses only a limited number of attacks: the authors are mostly concerned about attacks by deletion but they do not consider attacks well-known in the P2P literature such as flooding, selfishness, etc. The authors suggest the use of erasure codes. In order to optimize the read operation, they propose to store data blocks at several levels of dispersal: first, entirely a single node, then dispersed among 32 nodes, then dispersed among 1,024 nodes, etc. However, such a scheme with 4 levels of dispersion would cost 7 times the size of the original block. Later on, they propose a storage model from a theoretical point of view which turns out to be close to DHTs and the likes.

  • Economy-Based Data Replication Broker Policies in Data Grids [lin05:replication-broker]
    Henry Lin (Department of Computer Science and Software Engineering, The University of Melbourne, Australia), January 2005
  • Improving Data Availability Through Dynamic Model-Driven Replication in Large Peer-to-Peer Communities [ranganathan02:replication]
    Kavitha Ranganathan, Adriana Iamnitchi, Ian Foster (Department of Computer Science, The University of Chicago, Chicago, IL (USA)), Proceedings of the Workshop on Global and Peer-to-Peer Computing on Large Scale Distributed Systems, May 2002
  • An Analysis of GNUnet and the Implications for Anonymous, Censorship-Resistant Networks [kugler03:gnunet]
    Dennis K?gler (Federal Office for Information Security, Germany), Proceedings of the Conference on Privacy Enhancing Technologies, March 2003

    This paper describes the basic ideas behind GAP and what makes it censorship resistant. A very brief description of the data encoding mechanisms (ECRS) is also included but the reader may prefer to refer to bennett04:gnunet-ecrs instead.

  • Efficient Sharing of Encrypted Data [bennett02:gnunet-esed]
    Krista Bennett, Christian Grothoff, Tzvetan Horozov, Ioana Patrascu, Proceedings of the 7th Australasian Conference on Information Security and Privacy (ACISP 2002), 2002

    Describes ESED, the ancestor of the current ECRS.

  • An Encoding for Censorship-Resistant Sharing [bennett04:gnunet-ecrs]
    Krista Bennett, Christian Grothoff, Tzvetan Horozov, J. T. Lindgren (Purdue University, USA, Motorola Labs, USA, University of Helsinki, Finland), 2003

    This document presents the data dissemination and encoding protocol implemented in GNUnet which is called ECRS. The protocol is designed in such a way that queries, replies, and data blocks are encrypted (using content-hash keys or CHK) yet allowing intermediaries to verify that an encrypted response matches an encrypted query (note that unlike Freenet, GNUnet stores whole files rather than blocks). ECRS also makes it possible to store file data under descriptive keywords. You probably should read this file: it summarizes and clarifies earlier work on content-based indexing and the likes and is probably one of the best papers on that topic. Additionally, you might want to look at the GNUnet papers page which contains a whole lot of pointers to related work.

  • Protocols for Public Key Cryptosystems [merkle80:protocols]
    Ralph C. Merkle (ELXSi International), Proceedings of the IEEE Symposium on Security and Privacy, April 1980

    This paper presents the fundamental hash tree structure (called Merkle trees) that underlies Venti's, GNUnet's, and other such systems' file encoding mechanism. It shows how one tree leaf can be authenticated without knowing the whole file it comes from. "The information needed to authenticate [a leaf], given that [the root] R has already been authenticated, lies along the path from R to [the leaf] and will be called the authentication path." See also the Tree Hash Exchange Format (THEX).

  • OceanStore: An Architecture for Global-Scale Persistent Storage [kubiatowicz00:oceanstore]
    John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton, Dennis Geels, Ramakrishna Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, Chris Wells, Ben Zhao (University of California, Berkeley, USA), Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), November 2000

    OceanStore is a large-scale distributed store built on top of an unstructured overlay network. Its update model allows users to modify data objects while preserving ACID semantics. It also handles concurrent writes and reconciliation. They argue about deep archival storage, stating that fragmentation increases reliability. They show that, assuming that only 10% of the contributors are down, using erasure codes increases the probability of being able to retrieve a document. This would be much different with fewer machines up.

  • Wide-Area Cooperative Storage With CFS [dabek01:cfs]
    Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica (MIT Laboratory for Computer Science), Proceedings 18th ACM Symposium on Operating Systems Principles, October 2001

    CFS, the cooperative file-system (part of the Chord project), is a read-only distributed, peer-to-peer filesystem that is presumably as fast as FTP and is supposed to run on GNU/Linux, OpenBSD and FreeBSD (I say "supposed to" because unfortunately code of CFS itself doesn't seem to be available). It stores files on a per-block basis, where each block is encrypted and indexed using content-hash-keys (as in GNUnet and Freenet). Blocks are linked together in a tree fashion (using inodes as in traditional filesystems, as in GNUnet's ECRS too) whose root block is signed with the publisher's private key (as with GNUnet's pseudonyms). Unlike in GNUnet/Freenet, blocks may not be lost inadvertently (e.g. under storage shortage conditions) since CFS nodes explicitly store blocks for an agreed-upon time interval (which is made possible by the fact that CFS does not aim at providing anonymity unlike GNUnet and Freenet). Each block is replicated several times on the publisher node's successors in the ID space.
    The implementation itself uses Chord (data location service) on top of DHash (DHT). The impressing thing is the Chord lookup protocol itself which works in O(log(N)), N being the total number of nodes. The idea is that the node ID space is represented as a ring where each node stores the list of its log(N) successors as well as fingers to nodes located at power of two of the node's ID in the ID space. IDs are guaranteed to be global since they merely consists of a hash of the nodes IP address plus a virtual server ID. Since each block is replicated on several nodes, clients may select one of these nodes based on latency information that is maintained by each node. Cost estimation can be made and require an estimate of the total node number that is computed "based on the density of nodes nearby in the ID ring".
    There are in my opinion two design flaws:

    • load balance relies on having nodes run several virtual servers proportionally to their available storage space and the total number of servers; this requires nodes to trust each other and administrators to not forget to launch more virtual servers if they can afford storing more data (papers about GNUnet and Samsara address this);
    • quotas, which are meant to avoid having one publisher flood the whole network with useless data, work as follows: each node should make sure that each IP address does not use more than, say, 0.1% of its storage; this would result in making it impossible to publish data even though most of the overall system storage is unused.
    Besides, this is a wonderful paper.

  • Chirp: An Architecture for Cooperative Storage [thain05:chirp]
    Douglas Thain (Univ. of Notre Dame, Computer Science and Engineering Dept., USA), February 2005
  • Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility [rowstron01:past]
    A. Rowstron, P. Druschel (Microsoft Research, Cambridge, UK; Rice University, Houston, USA), 18th ACM SOSP'01, October 2001
  • A Peer-to-Peer Mobile Storage System [garg02:skunk]
    Nitin Garg, Yilei Shao, Elisha Ziskind, Sumeet Sobti, Fengzhou Zheng, Junwen Lai, Arvind Krishnamurthy, Randolph Y. Wang (Department of Computer Science, Princeton University (USA)), October 2002
  • High Availability in DHTs: Erasure Coding vs. Replication [rodrigues05:erasure]
    Rodrigo Rodrigues, Barbara Liskov (MIT, USA), Proceedings of the 4th International Workshop of Peer-to-Peer Systems, February 2005
  • Network Coding for Large Scale Content Distribution [gkantsidis05:netcoding]
    Christos Gkantsidis, Pablo Rodriguez Rodriguez (College of Computing, Georgia Institute of Technology (USA); Microsoft Research (UK)), IEEE Infocom 2005, March 2005

    Lots of interesting papers on wireless networking and P2P content distribution on Rodiguez' webpage!

  • Protecting Freedom of Information Online with Freenet [clarke02:freenet]
    Ian Clarke, Scott G. Miller, Theodore W. Hong, Oskar Sandberg, Brandon Wiley (Uprizer), appeared in IEEE Internet Computer, 2002

    An introduction to Freenet, only published on the Internet it seems.

  • Exploiting Similarity for Multi-Source Downloads using File Handprints [pucha07:set]
    Himabindu Pucha, David G. Andersen, Michael Kaminsky (Carnegie Mellon University, USA), Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), April 2007

    An example use of Manber's technique manber94:finding for so-called similarity-enhanced transfer (SET), by the authors of tolia06:dot. To appear.

  • Feasibility of a Serverless Distributed File System Deployed on an Existing Set of Desktop PCs [bolosky00:serverless]
    William J. Bolosky, John R. Douceur, David Ely, Marvin Theimer (Microsoft Research, Redmond, WA, USA), Proceedings of the International Conference on Measurement and Modeling of Computer Systems, 2000

    The very paper that introduced (or, rather, clarified) the idea of single-instance storage first. This technique is used by most P2P file sharing systems, by several versioning and archival systems, including GNUnet, Pastiche cox02:pastiche, Venti quinlan02:venti, GNU Arch (revision libraries), etc.

  • Freenet: A Distributed Anonymous Information Storage and Retrieval System [clarke01:freenet]
    Ian Clarke, Oskar Sandberg, Brandon Wiley, Theodore W. Hong, Proceedings of the International Workshop on Designing Privacy Enhancing Technologies, 2001
  • Segank: A Distributed Mobile Storage System [sobti04:segank]
    Sumeet Sobti, Nitin Garg, Fengzhou Zheng, Junwen Lai, Yilei Shao, Chi Zhang, Elisha Ziskind, Arvind Krishnamurthy, Randolph Y. Wang, Proceedings of the Third Conference on File and Storage Technologies, March 2004
  • An Architecture for Internet Data Transfer [tolia06:dot]
    Niraj Tolia, Michael Kaminsky, David G. Andersen, Swapnil Patil (Carnegie Mellon University, USA), Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2006

    Another use of Manber's technique manber94:finding, by the authors of pucha07:set.

  • POST: A secure, resilient, cooperative messaging system [mislove03:post]
    Alan Mislove, Ansley Post, Charles Reis, Paul Willmann, Peter Druschel, Dan S. Wallach, Xavier Bonnaire, Pierre Sens, Jean-Michel Busca, Luciana Arantes-Bezerra (Rice University, Houston, TX, USA; LIP6, Universite Paris VI, Paris, France), Proceedings of the 9th Workshop on Hot Topics in Operating Systems, May 2003

    Beside presenting an interesting DHT-based decentralized email storage system, this paper contains a small discussion of the weaknesses of convergent encryption with respect to confidentiality and how they can be worked around.

  • Total Recall: System Support for Automated Availability Management [bhagwan04:totalrecall]
    Ranjita Bhagwan, Kiran Tati, Yu-Chung Cheng, Stefan Savage, Geoffrey M. Voelker (University of California, San Diego, CA, USA), Proceedings of the ACM/USENIX Symposium on Networked Systems Design and Implementation, March 2004

    TotalRecall is a peer-to-peer storage system which design goal is to allow user-defined target file availabilities to be honored. To accommodate the inherent dynamic behavior of the peer-to-peer environment, the author focus on three key aspects:

    • host availability prediction, at multiple time scales (important to distinguish between transient unavailability and final host departure);
    • redundancy managements, that is, choosing the best redundancy parameters (erasure coding, simple replication, etc.) based on host availability predictions;
    • dynamic repair policies, either "eager" or "lazy" depending on the tradeoff between storage and bandwidth that is made.
    See also lin04:revisited on that topic.

  • MD5 Collisions [daum05:md5-collisions]
    Magnus Daum, Stefan Lucks (CITS Research Group, RUB; University of Mannheim), 2005

    An excellent real-world example of how to take advantage of an MD5 collision between two unrelated documents (PostScript files).

  • A Low-Bandwidth Network File System [muthitacharoen01:lbfs]
    Athicha Muthitacharoen, Benjie Chen, David Mazi?res (Laboratory for Computer Science, MIT (USA); Department of Computer Science, NYU (USA)), Proceedings of the 18th ACM Symposium on Operating Systems Principles, October 2001

    Uses Rabin fingerprint to determine block boundaries, as in manber94:finding.

  • Understanding Availability [bhagwan03:availability]
    Ranjita Bhagwan, Stefan Savage and Geoffrey M. Voelker (University of California, San Diego, CA, USA), Proceedings of the Second International Workshop on Peer-to-Peer Systems, February 2003

    An empirical study of peer availability in the DHT-based Overnet peer-to-peer network. The authors study the effect of aliasing (i.e., multiple IP address per host) and conclude that previous measurements which were made under the assumption that each host corresponds to one IP address were underestimating peer availability "by a factor of four".

(made with skribilo)