{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:26Z","timestamp":1740109286273,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T00:00:00Z","timestamp":1619308800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T00:00:00Z","timestamp":1619308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s00446-021-00394-7","type":"journal-article","created":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T10:06:27Z","timestamp":1619345187000},"page":"181-193","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Lower bounds for in-network computation of arbitrary functions"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8656-4023","authenticated-orcid":false,"given":"Iqra Altaf","family":"Gillani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pooja","family":"Vyavahare","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amitabha","family":"Bagchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,25]]},"reference":[{"key":"394_CR1","unstructured":"Aldous, D., Fill, J.: Reversible markov chains and random walks on graphs (2002)"},{"issue":"2","key":"394_CR2","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/j.csi.2011.03.004","volume":"36","author":"R Aqeel-ur","year":"2014","unstructured":"Aqeel-ur, R., Abbasi, A.Z., Islam, N., Shaikh, Z.A.: A review of wireless sensors and networks\u2019 applications in agriculture. Comp. Stand. Interfaces 36(2), 263\u2013270 (2014)","journal-title":"Comp. Stand. Interfaces"},{"issue":"12","key":"394_CR3","doi-asserted-by":"publisher","first-page":"6020","DOI":"10.1109\/TIT.2010.2080850","volume":"56","author":"O Ayaso","year":"2010","unstructured":"Ayaso, O., Shah, D., Dahleh, M.A.: Information theoretic bounds for distributed computation over networks of point-to-point channels. IEEE Trans. Inf. Theory 56(12), 6020\u2013039 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"394_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s11134-012-9296-8","volume":"72","author":"S Banerjee","year":"2012","unstructured":"Banerjee, S., Gupta, P., Shakkottai, S.: Towards a queueing-based framework for in-network function computation. Queueing Syst. 72(3), 219\u2013250 (2012)","journal-title":"Queueing Syst."},{"key":"394_CR5","unstructured":"Becchetti, L., Bonifaci, V., Natale, E.: Pooling or sampling: Collective dynamics for electrical flow estimation. In: Proc. of the 17th International Conference on Autonomous Agents and Multi Agent Systems, AAMAS \u201918, pp. 1576\u20131584 (2018)"},{"issue":"10","key":"394_CR6","doi-asserted-by":"publisher","first-page":"5150","DOI":"10.1109\/TIT.2010.2060050","volume":"56","author":"F B\u00e9n\u00e9zit","year":"2010","unstructured":"B\u00e9n\u00e9zit, F., Dimakis, A.G., Thiran, P., Vetterli, M.: Order-optimal consensus through randomized path averaging. IEEE Trans. Inform Theory 56(10), 5150\u20135167 (2010)","journal-title":"IEEE Trans. Inform Theory"},{"key":"394_CR7","doi-asserted-by":"crossref","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Gossip algorithms: design, analysis and applications. In: Proceedings of the 24th annual joint conference of the IEEE computer and communications societies, INFOCOM \u201905, vol.\u00a03, pp. 1653\u20131664. IEEE (2005)","DOI":"10.1109\/INFCOM.2005.1498447"},{"key":"394_CR8","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proceedings of the 43rd annual ACM Symposium on theory of computing, STOC \u201911, pp. 273\u2013282. ACM (2011)","DOI":"10.1145\/1993636.1993674"},{"issue":"3","key":"394_CR9","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1109\/TSP.2007.908946","volume":"56","author":"ADG Dimakis","year":"2008","unstructured":"Dimakis, A.D.G., Sarwate, A.D., Wainwright, M.J.: Geographic gossip: efficient averaging for sensor networks. IEEE Trans. Signal Process. 56(3), 1205\u20131216 (2008)","journal-title":"IEEE Trans. Signal Process."},{"key":"394_CR10","doi-asserted-by":"crossref","unstructured":"Dutta, C., Radhakrishnan, J.: Lower bounds for noisy wireless networks using sampling algorithms. In: Proceedings of 49th annual IEEE symposium on foundations of computer science, FOCS \u201908, pp. 394\u2013402. IEEE (2008)","DOI":"10.1109\/FOCS.2008.72"},{"issue":"1\u20132","key":"394_CR11","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01159285","volume":"11","author":"L Georgiadis","year":"1992","unstructured":"Georgiadis, L., Szpankowski, W.: Stability of token passing rings. Queueing Syst. 11(1\u20132), 7\u201333 (1992)","journal-title":"Queueing Syst."},{"key":"394_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2020.106040","author":"IA Gillani","year":"2021","unstructured":"Gillani, I.A., Bagchi, A.: A queueing network-based distributed Laplacian solver for directed graphs. Inf. Proc. Lett. (2021). https:\/\/doi.org\/10.1016\/j.ipl.2020.106040","journal-title":"Inf. Proc. Lett."},{"key":"394_CR13","doi-asserted-by":"publisher","unstructured":"Gillani, I.A., Bagchi, A., Ranu, S.: A group-to-group version of random walk betweenness centrality. In: Proceedings of 8th ACM IKDD CODS and 26th COMAD, CODS-COMAD \u201921 (2021). https:\/\/doi.org\/10.1145\/3430984.3431020","DOI":"10.1145\/3430984.3431020"},{"key":"394_CR14","unstructured":"Gillani, I.A., Bagchi, A., Vyavahare, P.: Decentralized random walk-based data collection in networks (2017). ArXiv:1701.05296v4 [cs.NI]"},{"key":"394_CR15","unstructured":"Gillani, I.A., Bagchi, A., Vyavahare, P.: A stochastic process on a network with connections to Laplacian systems of equations (2017). ArXiv:1701.05296 [cs.NI]"},{"issue":"4","key":"394_CR16","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1109\/JSAC.2005.843543","volume":"23","author":"A Giridhar","year":"2005","unstructured":"Giridhar, A., Kumar, P.R.: Computing and communicating functions over sensor networks. IEEE J. Sel. Area. Comm. 23(4), 755\u2013764 (2005)","journal-title":"IEEE J. Sel. Area. Comm."},{"key":"394_CR17","doi-asserted-by":"publisher","DOI":"10.1002\/9781118625651","volume-title":"Fundamentals of Queueing Theory","author":"D Gross","year":"2008","unstructured":"Gross, D.: Fundamentals of Queueing Theory. Wiley, New York (2008)"},{"issue":"1","key":"394_CR18","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TNET.2002.808417","volume":"11","author":"C Intanagonwiwat","year":"2003","unstructured":"Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J., Silva, F.: Directed diffusion for wireless sensor networking. IEEE\/ACM Trans. Netw. 11(1), 2\u201316 (2003)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"8","key":"394_CR19","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.3390\/s17081781","volume":"17","author":"H Jawad","year":"2017","unstructured":"Jawad, H., Nordin, R., Gharghan, S., Jawad, A., Ismail, M.: Energy-efficient wireless sensor networks for precision agriculture: a review. Sensors 17(8), 1781 (2017)","journal-title":"Sensors"},{"issue":"5","key":"394_CR20","doi-asserted-by":"publisher","first-page":"2615","DOI":"10.1109\/TNET.2017.2703867","volume":"25","author":"NM Jones","year":"2017","unstructured":"Jones, N.M., Paschos, G.S., Shrader, B., Modiano, E.: An overlay architecture for throughput optimal multipath routing. IEEE\/ACM Trans. Netw. 25(5), 2615\u20132628 (2017)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"1","key":"394_CR21","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1109\/TIT.2013.2293214","volume":"60","author":"S Kamath","year":"2014","unstructured":"Kamath, S., Manjunath, D., Mazumdar, R.: On distributed function computation in structure-free random wireless networks. IEEE Trans. on Inform. Theory 60(1), 432\u2013442 (2014)","journal-title":"IEEE Trans. on Inform. Theory"},{"key":"394_CR22","doi-asserted-by":"crossref","unstructured":"Kamra, A., Misra, V., Feldman, J., Rubenstein, D.: Growth codes: maximizing sensor network data persistence. In: Proceedings of the 2006 Conference on applications, technologies, architectures, and protocols for computer communications, SIGCOMM \u201906, pp. 255\u2013266. ACM (2006)","DOI":"10.1145\/1159913.1159943"},{"issue":"4","key":"394_CR23","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1109\/JSAC.2013.130408","volume":"31","author":"S Kannan","year":"2013","unstructured":"Kannan, S., Viswanath, P.: Multi-session function computation and multicasting in undirected graphs. IEEE J. Sel. Area. Comm. 31(4), 702\u2013713 (2013)","journal-title":"IEEE J. Sel. Area. Comm."},{"issue":"12","key":"394_CR24","doi-asserted-by":"publisher","first-page":"7671","DOI":"10.1109\/TIT.2011.2168902","volume":"57","author":"N Karamchandani","year":"2011","unstructured":"Karamchandani, N., Appuswamy, R., Franceschetti, M.: Time and energy complexity of function computation over networks. IEEE Trans. Inf. Theory 57(12), 7671\u20137684 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"394_CR25","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Lee, Y.T., Orecchia, L., Sidford, A.: An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In: Proceedings of the 25th annual ACM-SIAM Symposium on discrete algorithms, SODA \u201914, pp. 217\u2013226. SIAM (2014)","DOI":"10.1137\/1.9781611973402.16"},{"issue":"6","key":"394_CR26","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"394_CR27","doi-asserted-by":"crossref","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Soc. (2009)","DOI":"10.1090\/mbk\/058"},{"issue":"4","key":"394_CR28","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/2479942.2479950","volume":"40","author":"J Liu","year":"2013","unstructured":"Liu, J., Xia, C.H., Shroff, N.B., Zhang, X.: On distributed computation rate optimization for deploying cloud computing programming frameworks. SIGMETRICS Perform. Eval. Rev. 40(4), 63\u201372 (2013)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"394_CR29","doi-asserted-by":"crossref","unstructured":"Loynes, R.M.: The stability of a queue with non-independent inter-arrival and service times. In: Mathematical Proceedings of the Cambridge philosophical society, vol.\u00a058, pp. 497\u2013520. Cambridge University Press (1962)","DOI":"10.1017\/S0305004100036781"},{"issue":"4","key":"394_CR30","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1109\/JSAC.2013.130411","volume":"31","author":"Z Lu","year":"2013","unstructured":"Lu, Z., Wen, Y., Fan, R., Tan, S.L., Biswas, J.J.: Toward efficient distributed algorithms for in-network binary operator tree placement in wireless sensor networks. IEEE J. Sel. Area. Comm. 31(4), 743\u2013755 (2013)","journal-title":"IEEE J. Sel. Area. Comm."},{"issue":"5","key":"394_CR31","doi-asserted-by":"publisher","first-page":"1579","DOI":"10.1109\/18.771161","volume":"45","author":"W Luo","year":"1999","unstructured":"Luo, W., Ephremides, A.: Stability of $$N$$ interacting queues in random-access systems. IEEE Trans. Info. Theory 45(5), 1579\u20131587 (1999)","journal-title":"IEEE Trans. Info. Theory"},{"key":"394_CR32","doi-asserted-by":"crossref","unstructured":"Mosk-Aoyama, D., Shah, D.: Computing separable functions via gossip. In: Proceedings of the 25th annual ACM symposium on principles of distributed computing, PODC \u201906, pp. 113\u2013122. ACM (2006)","DOI":"10.1145\/1146381.1146401"},{"key":"394_CR33","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.compag.2014.04.012","volume":"105","author":"DL Ndzi","year":"2014","unstructured":"Ndzi, D.L., Harun, A., Ramli, F.M., Kamarudin, M.L., Zakaria, A., Shakaff, A.Y.M., Jaafar, M.N., Zhou, S., Farook, R.S.: Wireless sensor network coverage measurement and planning in mixed crop farming. Comput. Electr. Agric. 105, 83\u201394 (2014)","journal-title":"Comput. Electr. Agric."},{"key":"394_CR34","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: Distributed complexity of large-scale graph computations. In: Proceedings of the 30th ACM symposium on parallelism and architectures, SPAA \u201918, pp. 405\u2013414. ACM (2018)","DOI":"10.1145\/3210377.3210409"},{"issue":"12","key":"394_CR35","doi-asserted-by":"publisher","first-page":"7135","DOI":"10.1109\/TIT.2016.2530398","volume":"62","author":"M Sefidgaran","year":"2016","unstructured":"Sefidgaran, M., Tchamkerten, A.: Distributed function computation over a rooted directed tree. IEEE Trans. Inf. Theory 62(12), 7135\u20137152 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"394_CR36","doi-asserted-by":"crossref","unstructured":"Shah, D.: Network gossip algorithms. In: Proceedings of the IEEE international conference on acoustics, speech and signal processing, ICASSP \u201909, pp. 3673\u20133676. IEEE (2009)","DOI":"10.1109\/ICASSP.2009.4960423"},{"issue":"4","key":"394_CR37","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1109\/JSAC.2013.130409","volume":"31","author":"V Shah","year":"2013","unstructured":"Shah, V., Dey, B.K., Manjunath, D.: Network flows for function computation. IEEE J. Sel. Area. Comm. 31(4), 714\u2013730 (2013)","journal-title":"IEEE J. Sel. Area. Comm."},{"key":"394_CR38","doi-asserted-by":"crossref","unstructured":"Sinclair, A.: Algorithms for random generation and counting. Progress in theoretical computer science (1993)","DOI":"10.1007\/978-1-4612-0323-0"},{"issue":"2","key":"394_CR39","doi-asserted-by":"publisher","first-page":"498","DOI":"10.2307\/1427448","volume":"26","author":"W Szpankowski","year":"1994","unstructured":"Szpankowski, W.: Stability conditions for some distributed systems: Buffered random access systems. Adv. Appl. Prob. 26(2), 498\u2013515 (1994)","journal-title":"Adv. Appl. Prob."},{"issue":"1","key":"394_CR40","first-page":"1751","volume":"15","author":"U Von Luxburg","year":"2014","unstructured":"Von Luxburg, U., Radl, A., Hein, M.: Hitting and commute times in large random neighborhood graphs. J. Mach. Learn. Res. 15(1), 1751\u20131798 (2014)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"394_CR41","doi-asserted-by":"publisher","first-page":"2019","DOI":"10.1109\/TNET.2015.2445835","volume":"24","author":"P Vyavahare","year":"2016","unstructured":"Vyavahare, P., Limaye, N., Manjunath, D.: Optimal embedding of functions for in-network computation: complexity analysis and algorithms. IEEE\/ACM Trans. Netw. 24(4), 2019\u20132032 (2016)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"394_CR42","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/j.jpdc.2017.05.008","volume":"109","author":"G Wang","year":"2017","unstructured":"Wang, G., Wang, Z., Wu, J.: A local average broadcast gossip algorithm for fast global consensus over graphs. J Parallel Distrib. Comput. 109, 301\u2013309 (2017)","journal-title":"J Parallel Distrib. Comput."},{"issue":"4","key":"394_CR43","doi-asserted-by":"publisher","first-page":"2314","DOI":"10.1109\/TIT.2017.2664813","volume":"63","author":"A Xu","year":"2017","unstructured":"Xu, A., Raginsky, M.: Information-theoretic lower bounds for distributed function computation. IEEE Trans. Inf. Theory 63(4), 2314\u20132337 (2017)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00394-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00394-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00394-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,29]],"date-time":"2024-08-29T10:05:16Z","timestamp":1724925916000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00394-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,25]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["394"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00394-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2021,4,25]]},"assertion":[{"value":"12 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}