Availability

In a peer-to-peer network the number of peers on which an object is present/shared. E.g. the availability of a file, a piece or a hash.

Local vs global availability

Usually availability is either local (information about known/connected peers, the neighbors) or global (network wide). Global availability (of an object) is always greater than or equal to local.

Often in cases where global availability would be preferable, local availability is instead (as an approximation), due to the high overhead usually associated with keeping track of global availability (collecting, compiling and distributing the information). This is especially the case in distributed systems such as peer-to-peer networks.

Rarest-first problem

Although local availability often is a pretty good approximation, problems can arise due to the local variations. Especially, consider the case of a peer with deciding whether to download a rare piece (low availability) or not, using a rarest-first algorithm. While local availability gives a fair approximation of the global availability of a piece for most peers, there's an important exception--peers with access to a rare piece. To the peers connected to a peer with a rare piece, the availability of the piece will be higher than in the rest of the network; it might even be quite average. Thus, local availability is a bad approximation of global in this situation and, a (globally) less rare might be chosen piece instead, leading to suboptimal behavior.

Solution

A solution would be to ask one or more random peers (possibly your neighbors) what they see . (What's the availability at their neighbors?) That way you get a better picture of whether the pieces you happened to get near are easily available to other peers as well. This way, the probability of misrepresentation of availability of rare pieces goes from 100% to something like being proportional to 1/N (with N being number of peers in net).

A proposal with this has been added to the BitTorrentWishList.