####
Optimal Plans for Aggregation

We consider the following problem, which arises in the context of
distributed Web computations. An aggregator aims to combine
specific data from n sources. The aggregator contacts all
sources at once. The time for each source to return its data to the
aggregator is independent and identically distributed according to a
known distribution. The aggregator at some point stops waiting for
data and returns an answer depending only on the data received so far.
If the aggregator returns the aggregated information from k of the
n sources at time t it obtains a reward R(k,t) that grows with
k and decreases with t. The goal of the aggregator is to maximize
its expected reward.
We prove that for certain broad families of distributions and broad
classes of reward functions, the optimal plan for the aggregator has a
simple form and hence can be easily computed.