D ability at least 1 − 1/(min{k, n − k})^d for every constant d < 1/2. In particular, finding the median requires at least Ω(D log n)

D

rounds.

Similar proof techniques have been used in the area of com-minication complexity where people try to find bounds on the total number of bits that have to be transmitted to solve a certain communication problem. ²² In particular, ²¹ introduces a simulation technique to run two-party protocols in paths and more general graphs in order to extend lower bound for computations between two nodes to computations on more general topologies. In contrast to communication complexity, our focus is on minimizing the number of communication rounds rather than minimizing the number of transmitted bits.

6. conclusion

In this article, we studied the k-selection problem, a prominent data aggregation problem, and proved upper and lower bounds on its (time) complexity. Our results are presented in an entirely abstract way, i.e., it remains to show that our algorithms have a notable impact on the performance of aggregation functions in real networks and thus prove to be relevant in practical applications. Apparently, it is usually not possible to simply implant a distributed algorithm in an application domain, as additional constraints imposed by the application need to be respected. In wireless sensor networks, e.g., aggregation needs to adhere to wireless channel characteristics. We believe that our work can shed additional light on the achievable aggregation rate and capacity^{10, 11} in wireless networks, or, combined with other algorithmic work on data gathering such as, e.g., ^{5, 6} may even provide basic aggregation functionality for various application domains. We hope that our results and techniques may eventually find their way into several application areas, providing aggregation support for, e.g., streaming databases or multi-core architectures.

acknowledgments

We would like to thank Pascal von Rickenbach and Roland Flury for their help with the illustrations. Moreover, we would like to express our gratitude to Hagit Attiya for providing valuable feedback, which helped us greatly to improve this article, and also for finding the time to write a technical perspective.

The original version of this paper is entitled “Tight Bounds for Distributed Selection” and can be found in the Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (San Diego, CA, June 2007).

References

1. Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., and Tarjan, R. E. Time bounds for selection. Journal of Computer and System Sciences, 7:448–461, 1973.

2. Burri, N., von Rickenbach, P., and Wattenhofer, R. Dozer. Ultra-low power data gathering in sensor

networks. In International Conference on Information Processing in Sensor Networks (IPSN), 2007.

3. Chin, F. Y. L. and Ting, H. F. An improved algorithm for finding the median distributively. Algorithmica, 2: 77–86, 1987.

4. Frederickson, G. N. Tradeoffs for selection in distributed networks. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 154–160, 1983.

5. Goel, A. and Estrin, D. Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk. Algorithmica, 43( 1–2): 5–15, 2005.

6. Jia, L., Lin, G., Noubir, G., Rajaraman, R., and Sundaram, R. Universal approximations for TSP, Steiner Tree, and set cover. In 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 386–395, 2005.

7. Kempe, D., Dobra, A., and Gehrke, J., Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003.

8. Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. TAG: a tiny aggregation service for ad-hoc sensor networks. In Proceedings of the 5th Annual Symposium on Operating Systems Design and Implementation (OSDI), pp. 131–146, 2002.

9. Marberg, J. M. and Gafni, E. An optimal shout-echo algorithm for selection in distributed sets. In Proceedings of the 23rd Allerton Conference on Communication, Control, and Computing, 1985.

10. Moscibroda, T. The worst-case capacity of wireless sensor networks. In 6th International Conference on Information Processing in Sensor Networks (IPSN), 2007.

11. Moscibroda, T. and Wattenhofer, R. The complexity of connectivity in wireless networks. In 25th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2006.

12. Negro, A., Santoro, N., and Urrutia, J. Efficient distributed selection with bounded messages. IEEE Transactions of Parallel and Distributed Systems, 8( 4):397–401, 1997.

13. Patt-Shamir, B. A note on efficient aggregate queries in sensor networks. In Proceedings of the 23rd Annual ACM Symposium on Principles of

 

Fabian Kuhn ( [e-mail]) Postdoc researcher, Institute of Theoretical Computer Science, ETH Zurich, Switzerland

Thomas Locher ( [e-mail])
PhD student, Computer Engineering
and Net works Laboratory, E TH Zurich,
Switzerland

© 2008 ACM 0001-0782/08/0900 $5.00

Distributed Computing (PODC), pp. 283–289, 2004.

14. Peleg, D. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, 2000.

15. Rodeh, M. Finding the median distributively. Journal of Computer and System Science, 24( 2):162–166, 1982.

16. Rodem, D., Santoro, N., and Sidney, J. Shout-echo selection in distributed files. Networks, 16:235–249, 1986.

17. Santoro, N., Scheutzow, M., and Sidney, J. B. On the expected complexity of distributed selection. Journal on Parallel and Distributed Computing, 5( 2):194–203, 1988.

18. Santoro, N., Sidney, J. B., and Sidney, S. J. A distributed selection algorithm and its expected communication complexity. Theoretical Computer Science, 100( 1):185–204, 1992.

19. Schönhage, A., Paterson, M. S., and Pippenger, N. Finding the median. Journal of Computer and System Sciences, 13:184–199, 1976.

20. Shrira, L., Francez, N., and Rodeh. M. Distributed k-selection: From a sequential to a distributed algorithm. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 143–153, 1983.

21. Tiwari, P. Lower bounds on communication complexity in distributed computer networks. Journal of the ACM (JACM), 34( 4):921, 1987.

22. Yao, A. Some complexity questions related to distributive computing. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 209, 1979.

23. Yao, Y. and Gehrke, J. The Cougar approach to in-network query processing in sensor networks. ACM SIGMOD record, 31( 3): 9–18, 2002.

24. Zhao, J., Govindan, R., and Estrin, D. Computing aggregates for monitoring wireless sensor networks. In Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications (SNPA), 2003.

 

Roger Wattenhofer (wattenhofer@tik. ee.ethz.ch) Professor, Head of Distributed Computing Group, Computer Engineering and Networks Laboratory, E TH Zurich, Switzerland