{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T04:13:18Z","timestamp":1749615198642,"version":"3.41.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,9,19]],"date-time":"2016-09-19T00:00:00Z","timestamp":1474243200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,9,19]],"date-time":"2016-09-19T00:00:00Z","timestamp":1474243200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0939370-CCF","CCF-1217506"],"award-info":[{"award-number":["0939370-CCF","CCF-1217506"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-AF-0937274","CCF 1320279"],"award-info":[{"award-number":["CCF-AF-0937274","CCF 1320279"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Le 3107\/1-1"],"award-info":[{"award-number":["Le 3107\/1-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000010","name":"Ford Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000010","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00446-016-0283-x","type":"journal-article","created":{"date-parts":[[2016,9,19]],"date-time":"2016-09-19T06:56:49Z","timestamp":1474268209000},"page":"169-191","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Searching without communicating: tradeoffs between performance and selection complexity"],"prefix":"10.1007","volume":"30","author":[{"given":"Christoph","family":"Lenzen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nancy","family":"Lynch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Calvin","family":"Newport","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsvetomira","family":"Radeva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,19]]},"reference":[{"issue":"6014","key":"283_CR1","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1126\/science.1193210","volume":"331","author":"Y Afek","year":"2011","unstructured":"Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z.: A biological solution to a fundamental distributed computing problem. Science 331(6014), 183\u2013185 (2011)","journal-title":"Science"},{"issue":"4","key":"283_CR2","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"issue":"04","key":"283_CR3","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1017\/S0963548311000125","volume":"20","author":"N Alon","year":"2011","unstructured":"Alon, N., Avin, C., Kouck\u1ef3, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. Comb., Prob. Comput. 20(04), 481\u2013502 (2011)","journal-title":"Comb., Prob. Comput."},{"issue":"2","key":"283_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1921659.1921663","volume":"7","author":"C Ambuhl","year":"2011","unstructured":"Ambuhl, C., Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7(2), 17 (2011)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"283_CR5","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1016\/j.jtbi.2010.09.026","volume":"267","author":"M Arbilly","year":"2010","unstructured":"Arbilly, M., Motro, U., Feldman, M.W., Lotem, A.: Co-evolution of learning complexity and social foraging strategies. J. Theor. Biol. 267(4), 573\u2013581 (2010)","journal-title":"J. Theor. Biol."},{"key":"283_CR6","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 269\u2013278. ACM (1998)","DOI":"10.1145\/276698.276759"},{"issue":"1","key":"283_CR7","doi-asserted-by":"publisher","first-page":"299","DOI":"10.2307\/2371684","volume":"64","author":"A Brauer","year":"1942","unstructured":"Brauer, A.: On a problem of partitions. Am. J. Math. 64(1), 299\u2013312 (1942)","journal-title":"Am. J. Math."},{"key":"283_CR8","doi-asserted-by":"crossref","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 355\u2013361. IEEE (1990)","DOI":"10.1109\/FSCS.1990.89554"},{"key":"283_CR9","unstructured":"Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 588\u2013597. Society for Industrial and Applied Mathematics (2002)"},{"key":"283_CR10","doi-asserted-by":"crossref","unstructured":"Emek, Y., Langner, T., Uitto, J., Wattenhofer, R.: Solving the ANTS problem with asynchronous finite state machines. In: Proceedings of the International Colloquium, pp. 471\u2013482 (2014)","DOI":"10.1007\/978-3-662-43951-7_40"},{"key":"283_CR11","doi-asserted-by":"crossref","unstructured":"Emek, Y., Wattenhofer, R.: Stone age distributed computing. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 137\u2013146. ACM (2013)","DOI":"10.1145\/2484239.2484244"},{"key":"283_CR12","doi-asserted-by":"crossref","unstructured":"Feinerman, O., Korman, A.: Memory lower bounds for randomized collaborative search and implications for biology. In: Distributed Computing, pp. 61\u201375. Springer (2012)","DOI":"10.1007\/978-3-642-33651-5_5"},{"key":"283_CR13","doi-asserted-by":"crossref","unstructured":"Feinerman, O., Korman, A.: Theoretical distributed computing meets biology: A review. In: Distributed Computing and Internet Technology, pp. 1\u201318. Springer (2013)","DOI":"10.1007\/978-3-642-36071-8_1"},{"key":"283_CR14","doi-asserted-by":"crossref","unstructured":"Feinerman, O., Korman, A., Lotker, Z., Sereni, J.S.: Collaborative search on the plane without communication. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 77\u201386. ACM (2012)","DOI":"10.1145\/2332432.2332444"},{"key":"283_CR15","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"2008","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 2. Wiley, Hoboken (2008)"},{"issue":"3","key":"283_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166\u2013177 (2006)","journal-title":"Networks"},{"key":"283_CR17","doi-asserted-by":"crossref","DOI":"10.1515\/9780691188348","volume-title":"Social Foraging Theory","author":"LA Giraldeau","year":"2000","unstructured":"Giraldeau, L.A., Caraco, T.: Social Foraging Theory. Princeton University Press, Princeton (2000)"},{"issue":"3","key":"283_CR18","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1016\/S0003-3472(85)80026-9","volume":"33","author":"R Harkness","year":"1985","unstructured":"Harkness, R., Maroudas, N.: Central place foraging by an ant (Cataglyphis bicolor Fab.): a model of searching. Anim. Behav. 33(3), 916\u2013928 (1985)","journal-title":"Anim. Behav."},{"issue":"3","key":"283_CR19","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/BF00377577","volume":"72","author":"K Holder","year":"1987","unstructured":"Holder, K., Polis, G.: Optimal and central-place foraging theory applied to a desert harvester ant Pogonomyrmex californicus. Oecologia 72(3), 440\u2013448 (1987)","journal-title":"Oecologia"},{"key":"283_CR20","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Lynch, N., Newport, C., Radeva, T.: Trade-offs between selection complexity and performance when searching the plane without communication. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 252\u2013261. ACM (2014)","DOI":"10.1145\/2611462.2611463"},{"issue":"3","key":"283_CR21","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00040-002-8302-2","volume":"49","author":"M McLeman","year":"2002","unstructured":"McLeman, M., Pratt, S., Franks, N.: Navigation using visual landmarks by the ant leptothorax albipennis. Insectes Sociaux 49(3), 203\u2013208 (2002)","journal-title":"Insectes Sociaux"},{"key":"283_CR22","unstructured":"O\u2019Brien, C.: Solving ANTS with loneliness detection and constant memory. M.Eng Thesis, MIT EECS Department (2014)"},{"issue":"2","key":"283_CR23","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/jagm.1999.1043","volume":"33","author":"P Panaite","year":"1999","unstructured":"Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33(2), 281\u2013295 (1999)","journal-title":"J. Algorithms"},{"issue":"4","key":"283_CR24","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM (JACM) 55(4), 17 (2008)","journal-title":"J. ACM (JACM)"},{"issue":"7067","key":"283_CR25","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1038\/438442a","volume":"438","author":"EJ Robinson","year":"2005","unstructured":"Robinson, E.J., Jackson, D.E., Holcombe, M., Ratnieks, F.L.: Insect communication: \u201cno entry\u201d signal in ant foraging. Nature 438(7067), 442\u2013442 (2005)","journal-title":"Nature"},{"key":"283_CR26","unstructured":"Rosenthal, J.S.: Rates of convergence for data augmentation on finite sample spaces. Ann. Appl. Probab. 3(3), 819\u2013839 (1993)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-016-0283-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-016-0283-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-016-0283-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T19:50:08Z","timestamp":1749585008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-016-0283-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,19]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["283"],"URL":"https:\/\/doi.org\/10.1007\/s00446-016-0283-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2016,9,19]]},"assertion":[{"value":"28 October 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}