  We give an improved algorithm for drawing a random sample from a large data
stream when the input elements are distributed across multiple sites which
communicate via a central coordinator. At any point in time the set of elements
held by the coordinator represent a uniform random sample from the set of all
the elements observed so far. When compared with prior work, our algorithms
asymptotically improve the total number of messages sent in the system as well
as the computation required of the coordinator. We also present a matching
lower bound, showing that our protocol sends the optimal number of messages up
to a constant factor with large probability. As a byproduct, we obtain an
improved algorithm for finding the heavy hitters across multiple distributed
sites.
