A system and method for storing data in a peer-to-peer network. A computer system includes interconnected hosts configured to store data segments. A first host stores a first subset of the data segments received from other hosts. The first host maintains a portion of a distributed hash table corresponding to the first subset of data segments and de-duplicates the first subset of the data segments against the remaining data segments. The distributed hash table comprises entries corresponding to the data segments, each entry including a data segment fingerprint that unambiguously identifies the corresponding data segment. The first host selects and joins a group of hosts that maintains the distributed hash table. The first host conveys data to the selected group indicating its availability to own additional entries in the distributed hash table.