Title
Storage Management and Caching in PAST, a large-scale, persistent peer-to-peer storage utility

Author
Antony Rowstron, Peter Druschel

Location
SOSP

Date
2001

Goals:
PAST's goal is to achieve load balance and high storage utilization in
a read-only distributed file system.  PAST differs from the Cooperative File
System (CFS) of the same conference in several respects:
- PAST's nodes explicitly state their storage capacity
- PAST uses Pastry as its routing scheme
- Insert (name, credentials, k, file) takes k which says how many
hosts this file should be propagated to.  Seems very trusting.  The k
insertions go to consecutive node identifiers, which are geographicly
and network-connectivity random.

Their handling of node failures seems much less elegant than CFS,
where server entry and exit seemed to be built in by design.  Here
nodes periodically exchange keep-alive messages.  Ugly.

They try to excuse their focus on graceful degradation by saying that
high utilization should be a goal for any storage system (section 3).  I just
don't buy this.  In keeping with this, their experiments do not
include latency or bandwidth numbers; they only seem to look at space utilization.

Mechanisms:
To achieve load balance, they use two mechanisms:
1) replica diversion.  Sends replicas to other nodes in the same "leaf set."
2) file diversion.  Sends the original file (and its k friends-to-be)
to another leaf set entirely.  This is done by recomputing the fileID
for the file (which then results in a different leaf set).

Oddly, PAST does allow multiple nodeIDs per physical node, but only
when that physical node has lots more space.  I don't see why it
doesn't do this explicitly like CFS.

The caching mechanism causes some number of additional copies to be
placed at sites beyond the k primary replicas.  Mechanism is based on
the Greedy-Dual Sized policy (Cao97).

Interestingly, PAST, like CFS, does not have a working search
mechanism at this time.  They also comment that there is no good
benchmark for peer-to-peer read-only systems like theirs.

They use smart cards to prevent people from fiddling with public keys.  Does this work?