{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:04:23Z","timestamp":1787504663827,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642240997","type":"print"},{"value":"9783642241000","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-24100-0_40","type":"book-chapter","created":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T02:20:40Z","timestamp":1318990840000},"page":"416-431","source":"Crossref","is-referenced-by-count":11,"title":["The Complexity of Data Aggregation in Directed Networks"],"prefix":"10.1007","author":[{"given":"Fabian","family":"Kuhn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rotem","family":"Oshman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems (detailed summary). In: Proc. 19th ACM Symp. on Theory of Computing (STOC), pp. 230\u2013240 (1987)","DOI":"10.1145\/28395.28421"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Regev, O.: An optimal lower bound on the communication complexity of gap-hamming-distance. In: Proc. 43rd ACM Symp. on Theory of Computing (STOC), pp. 51\u201360 (2011)","DOI":"10.1145\/1993636.1993644"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Lynch, N.A.: The impact of synchronous communication on the problem of electing a leader in a ring. In: Proc. 16th ACM Symp. on Theory of Computing (STOC), pp. 493\u2013503 (1984)","DOI":"10.1145\/800057.808719"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Indyk, P., Woodruff, D.: Tight lower bounds for the distinct elements problem. In: Proc. 44th IEEE Symp. on Foundations of Computer Science (FOCS), pp. 283\u2013288 (October 2003)","DOI":"10.1109\/SFCS.2003.1238202"},{"issue":"4","key":"40_CR5","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math.\u00a05(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 482\u2013491 (2003)","DOI":"10.1109\/SFCS.2003.1238221"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Locher, T., Schmid, S.: Distributed computation of the mode. In: Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC), pp. 15\u201324 (2008)","DOI":"10.1145\/1400751.1400756"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Locher, T., Wattenhofer, R.: Tight bounds for distributed selection. In: Proc. 19th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 145\u2013153 (2007)","DOI":"10.1145\/1248377.1248401"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: Proc. 42nd ACM Symp. on Theory of Computing (STOC), pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"40_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge (1997)"},{"issue":"7","key":"40_CR11","doi-asserted-by":"publisher","first-page":"2997","DOI":"10.1109\/TIT.2008.924648","volume":"54","author":"D. Mosk-Aoyama","year":"2008","unstructured":"Mosk-Aoyama, D., Shah, D.: Fast distributed algorithms for computing separable functions. IEEE Transactions on Information Theory\u00a054(7), 2997\u20133007 (2008)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"40_CR12","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/71.588617","volume":"8","author":"A. Negro","year":"1997","unstructured":"Negro, A., Santoro, N., Urrutia, J.: Efficient distributed selection with bounded messages. IEEE Trans. Parallel and Distributed Systems\u00a08(4), 397\u2013401 (1997)","journal-title":"IEEE Trans. Parallel and Distributed Systems"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Patt-Shamir, B.: A note on efficient aggregate queries in sensor networks. In: Proc. 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 283\u2013289 (2004)","DOI":"10.1145\/1011767.1011809"},{"key":"40_CR14","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A.A. Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci.\u00a0106, 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"40_CR15","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/0743-7315(88)90029-9","volume":"5","author":"N. Santoro","year":"1988","unstructured":"Santoro, N., Scheutzow, M., Sidney, J.B.: On the expected complexity of distributed selection. J. Parallel and Distributed Computing\u00a05(2), 194\u2013203 (1988)","journal-title":"J. Parallel and Distributed Computing"},{"issue":"1","key":"40_CR16","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0304-3975(92)90368-P","volume":"100","author":"N. Santoro","year":"1992","unstructured":"Santoro, N., Sidney, J.B., Sidney, S.J.: A distributed selection algorithm and its expected communication complexity. Theoretical Computer Science\u00a0100(1), 185\u2013204 (1992)","journal-title":"Theoretical Computer Science"},{"key":"40_CR17","doi-asserted-by":"crossref","unstructured":"Shrira, L., Francez, N., Rodeh, M.: Distributed k-selection: From a sequential to a distributed algorithm. In: Proc. 2nd ACM Symp. on Principles of Distributed Computing (PODC), pp. 143\u2013153 (1983)","DOI":"10.1145\/800221.806717"},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1109\/TSE.1985.231858","volume":"11","author":"D.M. Topkis","year":"1985","unstructured":"Topkis, D.M.: Concurrent broadcast for information dissemination. IEEE Trans. Softw. Eng.\u00a011, 1107\u20131112 (1985)","journal-title":"IEEE Trans. Softw. Eng."}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-24100-0_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T22:47:51Z","timestamp":1560811671000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-24100-0_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642240997","9783642241000"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-24100-0_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}