Document Open Access Logo

Computation-Aware Data Aggregation

Authors Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.65.pdf
  • Filesize: 0.97 MB
  • 38 pages

Document Identifiers

Author Details

Bernhard Haeupler
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
D. Ellis Hershkowitz
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Anson Kahng
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Ariel D. Procaccia
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Haeupler, Bernhard: Supported in part by NSF grants CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808 and a Sloan Research Fellowship.
  • Hershkowitz, D. Ellis: Supported in part by NSF grants CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808 and a Sloan Research Fellowship.
  • Kahng, Anson: Supported in part by NSF grants IIS-1350598, IIS-1714140, CCF-1525932, and CCF-1733556; by ONR grants N00014-16-1-3075 and N00014-17-1-2428; and by a Sloan Research Fellowship and a Guggenheim Fellowship.
  • Procaccia, Ariel D.: Supported in part by NSF grants IIS-1350598, IIS-1714140, CCF-1525932, and CCF-1733556; by ONR grants N00014-16-1-3075 and N00014-17-1-2428; and by a Sloan Research Fellowship and a Guggenheim Fellowship.

Cite AsGet BibTex

Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, and Ariel D. Procaccia. Computation-Aware Data Aggregation. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 65:1-65:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.65

Abstract

Data aggregation is a fundamental primitive in distributed computing wherein a network computes a function of every nodes' input. However, while compute time is non-negligible in modern systems, standard models of distributed computing do not take compute time into account. Rather, most distributed models of computation only explicitly consider communication time. In this paper, we introduce a model of distributed computation that considers both computation and communication so as to give a theoretical treatment of data aggregation. We study both the structure of and how to compute the fastest data aggregation schedule in this model. As our first result, we give a polynomial-time algorithm that computes the optimal schedule when the input network is a complete graph. Moreover, since one may want to aggregate data over a pre-existing network, we also study data aggregation scheduling on arbitrary graphs. We demonstrate that this problem on arbitrary graphs is hard to approximate within a multiplicative 1.5 factor. Finally, we give an O(log n ⋅ log(OPT/t_m))-approximation algorithm for this problem on arbitrary graphs, where n is the number of nodes and OPT is the length of the optimal schedule.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Scheduling algorithms
Keywords
  • Data aggregation
  • distributed algorithm scheduling
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. IEEE Communications Magazine, 40(8):102-114, 2002. Google Scholar
  2. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: a survey. Computer Networks, 38(4):393-422, 2002. Google Scholar
  3. G. Anastasi, M. Conti, M. Di Francesco, and A. Passarella. Energy conservation in wireless sensor networks: a survey. Ad Hoc Networks, 7(3):537-568, 2009. Google Scholar
  4. Matthew Andrews and Michael Dinitz. Maximizing capacity in arbitrary wireless networks in the SINR model: Complexity and game theory. In IEEE INFOCOM 2009, pages 1332-1340. IEEE, 2009. Google Scholar
  5. Baruch Awerbuch, Shay Kutten, and David Peleg. Competitive distributed job scheduling. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 571-580. ACM, 1992. Google Scholar
  6. Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch, and Calvin Newport. Structuring unreliable radio networks. Distributed Computing, 27(1):1-19, 2014. Google Scholar
  7. Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz, and Goran Zuzic. Broadcasting in Noisy Radio Networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 33-42. ACM, 2017. Google Scholar
  8. Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz, and Goran Zuzic. Erasure Correction for Noisy Radio Networks, 2018. CoRR, Vol. abs/1805.04165. URL: http://arxiv.org/abs/1805.04165.
  9. Imrich Chlamtac and Shay Kutten. On broadcasting in radio networks-problem analysis and protocol design. IEEE Transactions on Communications, 33(12):1240-1246, 1985. Google Scholar
  10. Alejandro Cornejo, Seth Gilbert, and Calvin Newport. Aggregation in dynamic networks. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 195-204. ACM, 2012. Google Scholar
  11. I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 624-633, 2014. Google Scholar
  12. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 367-376. ACM, 2014. Google Scholar
  13. M. Elkin and G. Kortsarz. A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem. SIAM journal on Computing, 35(3):672-689, 2005. Google Scholar
  14. M. Elkin and G. Kortsarz. Sublogarithmic approximation for telephone multicast. Journal of Computer and System Sciences, 72(4):648-659, 2006. Google Scholar
  15. M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman and Company, 1979. Google Scholar
  16. A. Grama. Introduction to parallel computing. Pearson Education, 2003. Google Scholar
  17. J. Iglesias, R. Rajaraman, R. Ravi, and R. Sundaram. Rumors across radio, wireless, telephone. In Proceedings of the Leibniz International Proceedings in Informatics (LIPIcs), volume 45, 2015. Google Scholar
  18. N. Jain, J. M. Lau, and L. Kale. Collectives on two-tier direct networks. In Proceedings of the European MPI Users' Group Meeting, pages 67-77, 2012. Google Scholar
  19. B. Klenk, L. Oden, and H. Fröning. Analyzing communication models for distributed thread-collaborative processors in terms of energy and time. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 318-327, 2015. Google Scholar
  20. G. Kortsarz and D. Peleg. Approximation algorithms for minimum-time broadcast. SIAM Journal on Discrete Mathematics, 8(3):401-427, 1995. Google Scholar
  21. Eyal Kushilevitz and Yishay Mansour. Computation in Noisy Radio Networks. In SODA, volume 98, pages 236-243, 1998. Google Scholar
  22. F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994. Google Scholar
  23. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  24. L. Marchal, Y. Yang, H. Casanova, and Y. Robert. A realistic network/application model for scheduling divisible loads on large-scale platforms. In Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 10-pp, 2005. Google Scholar
  25. L. Oden, B. Klenk, and H. Fröning. Energy-efficient collective reduce and allreduce operations on distributed GPUs. In Proceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), pages 483-492, 2014. Google Scholar
  26. P. Patarasuk and X. Yuan. Bandwidth efficient all-reduce operation on tree topologies. In Proceedings of the 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1-8, 2007. Google Scholar
  27. P. Patarasuk and X. Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing, 69(2):117-124, 2009. Google Scholar
  28. D. Peleg. Distributed computing. SIAM Monographs on Discrete Mathematics and Applications, 5, 2000. Google Scholar
  29. R. Rabenseifner. Optimization of collective reduction operations. In Proceedings of the International Conference on Computational Science, pages 1-9, 2004. Google Scholar
  30. R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 202-213, 1994. Google Scholar
  31. T. Rothvoß. A simpler proof for O(congestion+dilation) packet routing. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, pages 336-348, 2013. Google Scholar
  32. A. Srinivasan and C. Teo. A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM Journal on Computing, 30(6):2051-2068, 2001. Google Scholar
  33. S. Viswanathan, B. Veeravalli, and T. G. Robertazzi. Resource-aware distributed scheduling strategies for large-scale computational cluster/grid systems. IEEE Transactions on Parallel and Distributed Systems, 18(10), 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact