Lv et. al. examine a pair of search methods that are =
superior to flooding in unstructured P2P networks. The first is =
expanding ring, which is essentially flooding with an iteratively =
deepening TTL (which fixes the problem of finding the right TTL). =
The second is a number of random walks on the graph, which gives two =
orders of magnitude improvement in search costs for realistic graph =
models. This has the nice side effect of supporting partial =
searches because the walkers "call home" to see if they should =
continue so the user can decide when the partial search has produced =
sufficient results. They then examine the effects of replication =
in their models. Their results show that uniform replication and =
replication proportional to the query frequency give the same weighted =
average performance. However, replicating proportional to the =
square root of the query frequency gives optimal performance. The =
downside is that this proportion is difficult to implement.

The claims about the implementation square root replication are =
theoretically shaky (though their results show that it is an improvement =
in practice). In particular, they say that it their path =
replication system is described by a differential equation that has a =
fixed point corresponding to the sqrt n. This immediately raises =
several issues. Is this the only fixed point? If not, why =
should the system converge to it rather than some other? Is it =
even stable (i.e will the system converge to it from nearby or do you =
tend to drift farther away once you get a little distance away)? =
If the system does converge to this fixed point, how long will it =
take? In their evaluation, they seemingly arbitrarily wait 5000s =
in Figure 7, but it is unclear how this extends beyond the specific =
settings of their simulation. This convergence rate is of =
practical importance, because the rate will effect the ability of the =
system to handle sudden changes in request frequency.

Beehive is a replication system built on top of a structured DHT that =
provides O(1) lookups by exploiting the search patterns of the =
DHT. Since there is a deterministic set of possible paths to an =
object, Beehive can shorten every path by one hop by replicating the =
object at every node one hop back along one of these paths. Using =
a closed-form optimal solution to a system of equations, Beehive can =
provide average lookup of c hops for any constant c while still having =
the worst case O(log n) hops provided by Pastry. Experimental =
results show significant performance improvements over Pastry with =
passive caching of objects at every node along a query path =
(PC-Pastry). Once concern is that Figure 6 shows that after a =
large change in object popularity, Beehive's latency rises to that of =
PC-Pastry and takes longer to return to its basely. If the =
popularity of objects is constantly changing, this may lead to no =
improvement in latency over Pastry (although it will still have =
significantly fewer object transfers).