  We consider communication-efficient weighted and unweighted (uniform) random
sampling from distributed data streams presented as a sequence of mini-batches
of items. This is a natural model for distributed streaming computation, and
our goal is to showcase its usefulness. We present and analyze fully
distributed, communication-efficient algorithms for both versions of the
problem. An experimental evaluation of weighted reservoir sampling on up to 256
nodes (5120 processors) shows good speedups, while theoretical analysis
promises further scaling to much larger machines.
