{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T22:40:50Z","timestamp":1782513650032,"version":"3.54.5"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T00:00:00Z","timestamp":1503532800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-BS02-014"],"award-info":[{"award-number":["ANR-11-BS02-014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0367-4","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T09:50:05Z","timestamp":1503568205000},"page":"3023-3049","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A Faster Exact-Counting Protocol for Anonymous Dynamic Networks"],"prefix":"10.1007","volume":"80","author":[{"given":"Maitri","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessia","family":"Milani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miguel A.","family":"Mosteiro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,8,24]]},"reference":[{"key":"367_CR1","doi-asserted-by":"crossref","unstructured":"Almeida, P.S., Baquero, C., Farach-Colton, M., Jesus, P., Mosteiro, M.A.: Fault-tolerant aggregation: Flow-updating meets mass-distribution. In: Proceedings of the 15th International Conference on Principles of Distributed Systems. Lecture Notes in Computer Science, vol. 7109, pp. 513\u2013527. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25873-2_35"},{"key":"367_CR2","doi-asserted-by":"crossref","unstructured":"Avin, C., Kouck\u1ef3, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Automata, languages and programming, pp. 121\u2013132. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-70575-8_11"},{"key":"367_CR3","unstructured":"Baldoni, R., Di\u00a0Luna, G.A.: Counting on anonymous dynamic networks: Bounds and algorithms (2016). Manuscript"},{"issue":"4","key":"367_CR4","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/s00373-012-1175-x","volume":"29","author":"A Beveridge","year":"2013","unstructured":"Beveridge, A., Wang, M.: Exact mixing times for random walks on trees. Graphs Comb. 29(4), 757\u2013772 (2013)","journal-title":"Graphs Comb."},{"issue":"5","key":"367_CR5","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"367_CR6","doi-asserted-by":"crossref","unstructured":"Chakraborty, M., Milani, A., Mosteiro, M.A.: Counting in practical anonymous dynamic networks is polynomial. In: Proceedings of the 4th International Conference on Networked Systems. Lecture Notes in Computer Science, vol. 9944, pp. 131\u2013136. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-46140-3_10"},{"key":"367_CR7","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G.A., Baldoni, R.: Brief announcement: Investigating the cost of anonymity on dynamic networks. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 339\u2013341. ACM, New York (2015)","DOI":"10.1145\/2767386.2767442"},{"key":"367_CR8","unstructured":"Di\u00a0Luna, G.A., Baldoni, R.: Non trivial computations in anonymous dynamic networks. In: Proceedings of the 19th International Conference on Principles of Distributed Systems, Leibniz International Proceedings in Informatics (LIPIcs), vol. 46, pp. 1\u201316. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016)"},{"key":"367_CR9","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G.A., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Counting the number of homonyms in dynamic networks. In: Proceedings of 15th International Symposium Stabilization, Safety, and Security of Distributed Systems. Lecture Notes in Computer Science, vol. 8255, pp. 311\u2013325. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03089-0_22"},{"key":"367_CR10","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G.A., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Conscious and unconscious counting on anonymous dynamic networks. In: Proceedings of the 15th International Conference on Distributed Computing and Networking. Lecture Notes in Computer Science, vol. 8314, pp. 257\u2013271. Springer, Berlin (2014)","DOI":"10.1007\/978-3-642-45249-9_17"},{"key":"367_CR11","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G.A., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Counting in anonymous dynamic networks under worst-case adversary. In: Proceedings of the 34th International Conference on Distributed Computing Systems, pp. 338\u2013347. IEEE (2014)","DOI":"10.1109\/ICDCS.2014.42"},{"key":"367_CR12","doi-asserted-by":"crossref","unstructured":"Di\u00a0Luna, G.A., Bonomi, S., Chatzigiannakis, I., Baldoni, R.: Counting in anonymous dynamic networks: An experimental perspective. In: Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics. Lecture Notes in Computer Science, vol. 8243, pp. 139\u2013154. Springer, Berlin (2014)","DOI":"10.1007\/978-3-642-45346-5_11"},{"key":"367_CR13","doi-asserted-by":"crossref","unstructured":"Fall, K.: A delay-tolerant network architecture for challenged internets. In: Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 27\u201334. ACM, New York (2003)","DOI":"10.1145\/863955.863960"},{"issue":"4","key":"367_CR14","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s00446-012-0165-9","volume":"25","author":"A Fern\u00e1ndez Anta","year":"2012","unstructured":"Fern\u00e1ndez Anta, A., Milani, A., Mosteiro, M.A., Zaks, S.: Opportunistic information dissemination in mobile ad-hoc networks: The profit of global synchrony. Distrib. Comput. 25(4), 279\u2013296 (2012)","journal-title":"Distrib. Comput."},{"issue":"2","key":"367_CR15","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.jpdc.2012.09.013","volume":"73","author":"A Fern\u00e1ndez Anta","year":"2013","unstructured":"Fern\u00e1ndez Anta, A., Mosteiro, M.A., Thraves, C.: An early-stopping protocol for computing aggregate functions in sensor networks. J. Parallel Distrib. Comput. 73(2), 111\u2013121 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"key":"367_CR16","doi-asserted-by":"crossref","unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of the 44th IEEE Annual Symposium on Foundations of Computer Science, pp. 482\u2013491. IEEE (2003)","DOI":"10.1109\/SFCS.2003.1238221"},{"key":"367_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 513\u2013522. ACM, New York (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"367_CR18","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2009","unstructured":"Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009)"},{"key":"367_CR19","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Brief announcement: Naming and counting in anonymous unknown dynamic networks. In: Proceedings of the 26th International Conference on Distributed Computing, pp. 437\u2013438. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33651-5_46"},{"key":"367_CR20","doi-asserted-by":"crossref","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Naming and counting in anonymous unknown dynamic networks. In: Proceedings of 15th International Symposium Stabilization, Safety, and Security of Distributed Systems, pp. 281\u2013295. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-03089-0_20"},{"issue":"1","key":"367_CR21","doi-asserted-by":"crossref","first-page":"2016","DOI":"10.1016\/j.jpdc.2013.07.007","volume":"74","author":"O Michail","year":"2014","unstructured":"Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks. J. Parallel Distrib. Comput. 74(1), 2016\u20132026 (2014)","journal-title":"J. Parallel Distrib. Comput."},{"key":"367_CR22","unstructured":"Milani, A., Mosteiro, M.A.: A Faster Counting Protocol for Anonymous Dynamic Networks. In: Proceedings of the 19th International Conference on Principles of Distributed Systems, Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a046, pp. 1\u201313. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016)"},{"issue":"11","key":"367_CR23","doi-asserted-by":"crossref","first-page":"2506","DOI":"10.1109\/TAC.2009.2031203","volume":"54","author":"A Nedic","year":"2009","unstructured":"Nedic, A., Olshevsky, A., Ozdaglar, A., Tsitsiklis, J.N.: On distributed averaging algorithms and quantization effects. IEEE Trans. Autom. Control 54(11), 2506\u20132517 (2009)","journal-title":"IEEE Trans. Autom. Control"},{"key":"367_CR24","volume-title":"Combinatorial Algorithms for Computers and Calculators","author":"A Nijenhuis","year":"1978","unstructured":"Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms for Computers and Calculators, 2d edn. Academic Press, New York (1978)","edition":"2d"},{"key":"367_CR25","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, pp. 104\u2013110. ACM, New York (2005)","DOI":"10.1145\/1080810.1080828"},{"issue":"11","key":"367_CR26","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1109\/MCOM.2006.248176","volume":"44","author":"L Pelusi","year":"2006","unstructured":"Pelusi, L., Passarella, A., Conti, M.: Opportunistic networking: Data forwarding in disconnected mobile ad hoc networks. Commun. Mag. IEEE 44(11), 134\u2013141 (2006)","journal-title":"Commun. Mag. IEEE"},{"issue":"1","key":"367_CR27","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A Sinclair","year":"1989","unstructured":"Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing markov chains. Inf. Comput. 82(1), 93\u2013133 (1989)","journal-title":"Inf. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0367-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0367-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0367-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T15:29:15Z","timestamp":1570030155000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0367-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,24]]},"references-count":27,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["367"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0367-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,24]]}}}