We investigate a metric facility location problem in a distributed setting.
In this problem, we assume that each point is a client as well as a potential
location for a facility and that the opening costs for the facilities and the
demands of the clients are uniform. The goal is to open a subset of the input
points as facilities such that the accumulated cost for the whole point set,
consisting of the opening costs for the facilities and the connection costs
for the clients, is minimized.

We present a randomized distributed algorithm that computes in expectation an
O(1)-approximate solution to the metric facility location problem described
above. Our algorithm works in a synchronous message passing model, where each
point is an autonomous computational entity that has its own local memory and
that communicates with the other entities by message passing. We assume that
each entity knows the distance to all the other entities, but does not know
any of the other pairwise distances. Our algorithm uses three rounds of all-
to-all communication with message sizes bounded to O(log(n)) bits, where n is
the number of input points.

We extend our distributed algorithm to constant powers of metric spaces. For a
metric exponent l>=1, we obtain a randomized O(1)-approximation algorithm that
uses three rounds of all-to-all communication with message sizes bounded to
O(log(n)) bits.