  This paper is motivated by two applications, namely i) generalizations of
cuckoo hashing, a computationally simple approach to assigning keys to objects,
and ii) load balancing in content distribution networks, where one is
interested in determining the impact of content replication on performance.
These two problems admit a common abstraction: in both scenarios, performance
is characterized by the maximum weight of a generalization of a matching in a
bipartite graph, featuring node and edge capacities. Our main result is a law
of large numbers characterizing the asymptotic maximum weight matching in the
limit of large bipartite random graphs, when the graphs admit a local weak
limit that is a tree. This result specializes to the two application scenarios,
yielding new results in both contexts. In contrast with previous results, the
key novelty is the ability to handle edge capacities with arbitrary integer
values. An analysis of belief propagation algorithms (BP) with multivariate
belief vectors underlies the proof. In particular, we show convergence of the
corresponding BP by exploiting monotonicity of the belief vectors with respect
to the so-called upshifted likelihood ratio stochastic order. This auxiliary
result can be of independent interest, providing a new set of structural
conditions which ensure convergence of BP.
