Optimal plans for aggregation

ABSTRACT

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 Rk(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.

REFERENCES

• 1: Miklos Ajtai , Nimrod Megiddo , Orli Waarts, Improved Algorithms and Analysis for Secretary Problems and Generalizations, SIAM Journal on Discrete Mathematics, v.14 n.1, p.1-27, 2001 [doi>10.1137/S0895480195290017]
• 2: Susanne Albers , Günter Schmidt, Scheduling with Unexpected Machine Breakdowns, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.269-280, August 08-11, 1999
• 3: Baruch Awerbuch , Yossi Azar , Amos Fiat , Tom Leighton, Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.519-530, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238000]
• 4: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 5: Justin Boyan , Michael Mitzenmacher, Improved results for route planning in stochastic transportation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.895-902, January 07-09, 2001, Washington, D.C., United States
• 6: Y. S. Chow, H. Robbins, and D. Siegmund. Great Expectations: The Theory of Optimal Stopping, Houghton Mifflin Company, Boston, 1971.
• 7: Mayur Datar , Abhiram Ranade, Commuting with delay prone buses, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.22-29, January 09-11, 2000, San Francisco, California, United States
• 8: E. B. Dynkin. Markov processes and related problems of analysis, Cambridge University Press, Cambridge, 1981.
• 9: T. Ferguson. A Poisson Fishing Model. In Festschrift for Lucien Le Cam, pp. 234-244, Springer, 1997.
• 10: Bala Kalyanasundaram , Kirk R. Pruhs, Fault-tolerant scheduling, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.115-124, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195115]
• 11: Bala Kalyanasundaram , Kirk Pruhs, Fault-Tolerant Real-Time Scheduling, Proceedings of the 5th Annual European Symposium on Algorithms, p.296-307, September 15-17, 1997
• 12: K. C. Kapur and L. A. Lamberson. Reliability in Engineering Design. John Wiley and Sons, New York, 1977.
• 13: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 14: S. Ross. Infinitesimal Look-Ahead Stopping Rules. The Annals of Mathematical Statistics, 42(1):297-303, 1971.
• 15: S. Ross. Stochastic Processes. John Wiley and Sons, New York, 1983.
• 16: M. Shaked and J. G. Shanthikumar. Stochastic Orders and Their Applications. Academic Press, San Diego, 1994.
• 17: N. Starr and M. Woodroofe. Gone fishin': Optimal stopping based on catch times. University of Michigan Technical Report, Department of Statistics, 1974.
• 18: N. Starr, R. Wardrop, and M. Woodroofe. Estimating a mean from delayed observations. Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebeite, 35:103-116, 1976.
• 19: D. Stoyan. Comparison Methods for Queues and Other Stochastic Models. John Wiley and Sons, Berlin, 1983.