  The \textit{facility location} problem consists of a set of
\textit{facilities} $\mathcal{F}$, a set of \textit{clients} $\mathcal{C}$, an
\textit{opening cost} $f_i$ associated with each facility $x_i$, and a
\textit{connection cost} $D(x_i,y_j)$ between each facility $x_i$ and client
$y_j$. The goal is to find a subset of facilities to \textit{open}, and to
connect each client to an open facility, so as to minimize the total facility
opening costs plus connection costs. This paper presents the first
expected-sub-logarithmic-round distributed O(1)-approximation algorithm in the
$\mathcal{CONGEST}$ model for the \textit{metric} facility location problem on
the complete bipartite network with parts $\mathcal{F}$ and $\mathcal{C}$. Our
algorithm has an expected running time of $O((\log \log n)^3)$ rounds, where $n
= |\mathcal{F}| + |\mathcal{C}|$. This result can be viewed as a continuation
of our recent work (ICALP 2012) in which we presented the first
sub-logarithmic-round distributed O(1)-approximation algorithm for metric
facility location on a \textit{clique} network. The bipartite setting presents
several new challenges not present in the problem on a clique network. We
present two new techniques to overcome these challenges. (i) In order to deal
with the problem of not being able to choose appropriate probabilities (due to
lack of adequate knowledge), we design an algorithm that performs a random walk
over a probability space and analyze the progress our algorithm makes as the
random walk proceeds. (ii) In order to deal with a problem of quickly
disseminating a collection of messages, possibly containing many duplicates,
over the bipartite network, we design a probabilistic hashing scheme that
delivers all of the messages in expected-$O(\log \log n)$ rounds.
