{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T22:55:42Z","timestamp":1772060142339,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["PAMELA (ANR-16-CE23-0016-01)"],"award-info":[{"award-number":["PAMELA (ANR-16-CE23-0016-01)"]}]},{"name":"ANR","award":["DESCARTES (ANR-16-CE40-0023)"],"award-info":[{"award-number":["DESCARTES (ANR-16-CE40-0023)"]}]},{"name":"Tor Vergata University Programme","award":["ALBLOTECH project n.E89C20000620005"],"award-info":[{"award-number":["ALBLOTECH project n.E89C20000620005"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467921","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"81-91","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Search via Parallel L\u00e9vy Walks on Z2"],"prefix":"10.1145","author":[{"given":"Andrea","family":"Clementi","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \"Tor Vergata\", Rome, Italy"}]},{"given":"Francesco","family":"d'Amore","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d'Azur, Inria, CNRS, I3S, Sophia Antipolis, France"}]},{"given":"George","family":"Giakkoupis","sequence":"additional","affiliation":[{"name":"Inria, Univ Rennes, CNRS, IRISA, Rennes, France"}]},{"given":"Emanuele","family":"Natale","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d'Azur, Inria, CNRS, I3S, Sophia Antipolis, France"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000125"},{"key":"#cr-split#-e_1_3_2_2_2_1.1","doi-asserted-by":"crossref","unstructured":"Lucas Boczkowski Brieuc Guinard Amos Korman Zvi Lotker and Marc Renault. 2018. Random walks with multiple step lengths. In LATIN 2018: Theoretical Informatics. 174--186. https:\/\/doi.org\/10.1007\/978--3--319--77404--6_14[3] Denis Boyer Gabriel Ramos-Fern\u00e1ndez Octavio Miramontes Jos\u00e9 L Mateos Germinal Cocho Hern\u00e1n Larralde Humberto Ramos and Fernando Rojas. 2006. Scale-free foraging by primates emerges from their interaction with a complex environment. Proceedings of the Royal Society B: Biological Sciences 273 1595 (2006) 1743--1750. https:\/\/doi.org\/10.1098\/rspb.2005.3462 10.1007\/978--3--319--77404--6_14[3]","DOI":"10.1098\/rspb.2005.3462"},{"key":"#cr-split#-e_1_3_2_2_2_1.2","doi-asserted-by":"crossref","unstructured":"Lucas Boczkowski Brieuc Guinard Amos Korman Zvi Lotker and Marc Renault. 2018. Random walks with multiple step lengths. In LATIN 2018: Theoretical Informatics. 174--186. https:\/\/doi.org\/10.1007\/978--3--319--77404--6_14[3] Denis Boyer Gabriel Ramos-Fern\u00e1ndez Octavio Miramontes Jos\u00e9 L Mateos Germinal Cocho Hern\u00e1n Larralde Humberto Ramos and Fernando Rojas. 2006. Scale-free foraging by primates emerges from their interaction with a complex environment. Proceedings of the Royal Society B: Biological Sciences 273 1595 (2006) 1743--1750. https:\/\/doi.org\/10.1098\/rspb.2005.3462","DOI":"10.1098\/rspb.2005.3462"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.041108"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.048901"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_3_2_2_6_1","volume-title":"Search via parallel L\u00e9vy walks on Z 2 . CoRR abs\/2004.01562","author":"Clementi Andrea E. F.","year":"2021","unstructured":"Andrea E. F. Clementi , Francesco d' Amore , George Giakkoupis , and Emanuele Natale . 2021. Search via parallel L\u00e9vy walks on Z 2 . CoRR abs\/2004.01562 ( 2021 ). arXiv:2004.01562 https:\/\/arxiv.org\/abs\/2004.01562 Andrea E. F. Clementi, Francesco d'Amore, George Giakkoupis, and Emanuele Natale. 2021. Search via parallel L\u00e9vy walks on Z 2 . CoRR abs\/2004.01562 (2021). arXiv:2004.01562 https:\/\/arxiv.org\/abs\/2004.01562"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039700"},{"key":"e_1_3_2_2_8_1","volume-title":"Dubhashi and Alessandro Panconesi","author":"Devdatt","year":"2009","unstructured":"Devdatt P. Dubhashi and Alessandro Panconesi . 2009 . Concentration of measure for the analysis of randomized algorithms. Cambridge University Press . https: \/\/doi.org\/10.1017\/CBO9780511581274 10.1017\/CBO9780511581274 Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press. https: \/\/doi.org\/10.1017\/CBO9780511581274"},{"key":"e_1_3_2_2_9_1","volume-title":"Viswanathan","author":"Edwards Andrew M.","year":"2007","unstructured":"Andrew M. Edwards , Richard A. Phillips , Nicholas W. Watkins , Mervyn P. Freeman , Eugene J. Murphy , Vsevolod Afanasyev , Sergey V. Buldyrev , M. G. E. da Luz , E. P. Raposo , H. Eugene Stanley , and Gandhimohan M . Viswanathan . 2007 . Revisiting L\u00e9vy flight search patterns of wandering albatrosses, bumblebees and deer. Nature 449, 7165 (2007), 1044--1048. https:\/\/doi.org\/10.1038\/nature06199 10.1038\/nature06199 Andrew M. Edwards, Richard A. Phillips, Nicholas W. Watkins, Mervyn P. Freeman, Eugene J. Murphy, Vsevolod Afanasyev, Sergey V. Buldyrev, M. G. E. da Luz, E. P. Raposo, H. Eugene Stanley, and Gandhimohan M. Viswanathan. 2007. Revisiting L\u00e9vy flight search patterns of wandering albatrosses, bumblebees and deer. Nature 449, 7165 (2007), 1044--1048. https:\/\/doi.org\/10.1038\/nature06199"},{"key":"e_1_3_2_2_10_1","volume-title":"12th International Workshop, APPROX. 476--489","author":"Efremenko Klim","year":"2009","unstructured":"Klim Efremenko and Omer Reingold . 2009 . How Well Do Random Walks Parallelize?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 12th International Workshop, APPROX. 476--489 . https:\/\/doi.org\/10.1007\/978--3--642-03685--9_36 10.1007\/978--3--642-03685--9_36 Klim Efremenko and Omer Reingold. 2009. How Well Do Random Walks Parallelize?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX. 476--489. https:\/\/doi.org\/10.1007\/978--3--642-03685--9_36"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.054"},{"key":"e_1_3_2_2_13_1","volume-title":"41st International Colloquium, ICALP","author":"Emek Yuval","year":"2014","unstructured":"Yuval Emek , Tobias Langner , Jara Uitto , and Roger Wattenhofer . 2014 . Solving the ANTS Problem with Asynchronous Finite State Machines. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014. 471-- 482. https:\/\/doi.org\/10.1007\/978--3--662--43951--7_40 10.1007\/978--3--662--43951--7_40 Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. 2014. Solving the ANTS Problem with Asynchronous Finite State Machines. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014. 471-- 482. https:\/\/doi.org\/10.1007\/978--3--662--43951--7_40"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0285-8"},{"key":"e_1_3_2_2_15_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller William","unstructured":"William Feller . 1968. An Introduction to Probability Theory and Its Applications . Vol. 1 . Wiley . William Feller. 1968. An Introduction to Probability Theory and Its Applications. Vol. 1. Wiley."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0006587"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897541"},{"key":"e_1_3_2_2_18_1","volume-title":"The Search Efficiency of Intermittent L\u00e9vy walks Optimally Scales with Target Size. CoRR abs\/2003.13041","author":"Guinard Brieuc","year":"2020","unstructured":"Brieuc Guinard and Amos Korman . 2020. The Search Efficiency of Intermittent L\u00e9vy walks Optimally Scales with Target Size. CoRR abs\/2003.13041 ( 2020 ). arXiv:2003.13041 https:\/\/arxiv.org\/abs\/2003.13041 Brieuc Guinard and Amos Korman. 2020. The Search Efficiency of Intermittent L\u00e9vy walks Optimally Scales with Target Size. CoRR abs\/2003.13041 (2020). arXiv:2003.13041 https:\/\/arxiv.org\/abs\/2003.13041"},{"key":"e_1_3_2_2_19_1","volume-title":"Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020","author":"Guinard Brieuc","year":"2020","unstructured":"Brieuc Guinard and Amos Korman . 2020 . Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020 . 28:1--28:14. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.28 10.4230\/LIPIcs.STACS.2020.28 Brieuc Guinard and Amos Korman. 2020. Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020. 28:1--28:14. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.28"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09116"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1121201109"},{"key":"e_1_3_2_2_22_1","volume-title":"Multiple Random Walks on Paths and Grids. In 34th Symposium on Theoretical Aspects of Computer Science, STACS, Heribert Vollmer and Brigitte Vall\u00e9e (Eds.). 44:1--44:14","author":"Ivaskovic Andrej","year":"2017","unstructured":"Andrej Ivaskovic , Adrian Kosowski , Dominik Pajak , and Thomas Sauerwald . 2017 . Multiple Random Walks on Paths and Grids. In 34th Symposium on Theoretical Aspects of Computer Science, STACS, Heribert Vollmer and Brigitte Vall\u00e9e (Eds.). 44:1--44:14 . https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.44 10.4230\/LIPIcs.STACS.2017.44 Andrej Ivaskovic, Adrian Kosowski, Dominik Pajak, and Thomas Sauerwald. 2017. Multiple Random Walks on Paths and Grids. In 34th Symposium on Theoretical Aspects of Computer Science, STACS, Heribert Vollmer and Brigitte Vall\u00e9e (Eds.). 44:1--44:14. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.44"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.59"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0283-x"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.124.080601"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.048902"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ab41bb"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1318616111"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2013.0079"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsos.160941"},{"key":"e_1_3_2_2_32_1","volume-title":"Current status and future directions of L\u00e9vy walk research. Biology Open 7, 1","author":"Reynolds Andy M.","year":"2018","unstructured":"Andy M. Reynolds . 2018. Current status and future directions of L\u00e9vy walk research. Biology Open 7, 1 ( 2018 ), bio030106. https:\/\/doi.org\/10.1242\/bio.030106 10.1242\/bio.030106 Andy M. Reynolds. 2018. Current status and future directions of L\u00e9vy walk research. Biology Open 7, 1 (2018), bio030106. https:\/\/doi.org\/10.1242\/bio.030106"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1242\/jeb.009563"},{"key":"e_1_3_2_2_34_1","volume-title":"Shlesinger and Joseph Klafter","author":"Michael","year":"1986","unstructured":"Michael F. Shlesinger and Joseph Klafter . 1986 . L\u00e9vy walks versus L\u00e9vy flights. In On Growth and Form: Fractal and Non-Fractal Patterns in Physics. Springer Netherlands , Dordrecht, 279--283. https:\/\/doi.org\/10.1007\/978--94-009--5165--5_29 10.1007\/978--94-009--5165--5_29 Michael F. Shlesinger and Joseph Klafter. 1986. L\u00e9vy walks versus L\u00e9vy flights. In On Growth and Form: Fractal and Non-Fractal Patterns in Physics. Springer Netherlands, Dordrecht, 279--283. https:\/\/doi.org\/10.1007\/978--94-009--5165--5_29"},{"key":"e_1_3_2_2_35_1","volume-title":"Jonathan W Pitchford, Alex James, Mohammed Z Ahmed, Andrew S Brierley, Mark A Hindell, et al.","author":"Sims David W","year":"2008","unstructured":"David W Sims , Emily J Southall , Nicolas E Humphries , Graeme C Hays , Corey JA Bradshaw , Jonathan W Pitchford, Alex James, Mohammed Z Ahmed, Andrew S Brierley, Mark A Hindell, et al. 2008 . Scaling laws of marine predator search behaviour. Nature 451, 7182 (2008), 1098--1102. https:\/\/doi.org\/10.1038\/nature06518 10.1038\/nature06518 David W Sims, Emily J Southall, Nicolas E Humphries, Graeme C Hays, Corey JA Bradshaw, Jonathan W Pitchford, Alex James, Mohammed Z Ahmed, Andrew S Brierley, Mark A Hindell, et al. 2008. Scaling laws of marine predator search behaviour. Nature 451, 7182 (2008), 1098--1102. https:\/\/doi.org\/10.1038\/nature06518"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v16-931"},{"key":"#cr-split#-e_1_3_2_2_37_1.1","doi-asserted-by":"crossref","unstructured":"G. M. Viswanathan V. Afanasyev S. V. Buldyrev E. J. Murphy P. A. Prince and H. E. Stanley. 1996. L\u00e9vy flight search patterns of wandering albatrosses. Nature 381 6581 (1996) 413--415. https:\/\/doi.org\/10.1038\/381413a0 10.1038\/381413a0","DOI":"10.1038\/381413a0"},{"key":"#cr-split#-e_1_3_2_2_37_1.2","doi-asserted-by":"crossref","unstructured":"G. M. Viswanathan V. Afanasyev S. V. Buldyrev E. J. Murphy P. A. Prince and H. E. Stanley. 1996. L\u00e9vy flight search patterns of wandering albatrosses. Nature 381 6581 (1996) 413--415. https:\/\/doi.org\/10.1038\/381413a0","DOI":"10.1038\/381413a0"},{"key":"e_1_3_2_2_38_1","volume-title":"Optimizing the success of random searches. Nature 401, 6756","author":"Viswanathan G. M.","year":"1999","unstructured":"G. M. Viswanathan , Sergey V. Buldyrev , Shlomo Havlin , M. G. E. da Luz , E. P. Raposo , and H. Eugene Stanley . 1999. Optimizing the success of random searches. Nature 401, 6756 ( 1999 ), 911--914. https:\/\/doi.org\/10.1038\/44831 10.1038\/44831 G. M. Viswanathan, Sergey V. Buldyrev, Shlomo Havlin, M. G. E. da Luz, E. P. Raposo, and H. Eugene Stanley. 1999. Optimizing the success of random searches. Nature 401, 6756 (1999), 911--914. https:\/\/doi.org\/10.1038\/44831"},{"key":"e_1_3_2_2_39_1","volume-title":"The Physics of Foraging: An Introduction to Random Searches and Biological Encounters","author":"Viswanathan Gandhimohan M.","year":"1902","unstructured":"Gandhimohan M. Viswanathan , Marcos G. E. da Luz , Ernesto P. Raposo , and H. Eugene Stanley . 2011. The Physics of Foraging: An Introduction to Random Searches and Biological Encounters . Cambridge University Press , Cambridge ; New York. https:\/\/doi.org\/10.1017\/CBO978051 1902 680 10.1017\/CBO9780511902680 Gandhimohan M. Viswanathan, Marcos G. E. da Luz, Ernesto P. Raposo, and H. Eugene Stanley. 2011. The Physics of Foraging: An Introduction to Random Searches and Biological Encounters. Cambridge University Press, Cambridge ; New York. https:\/\/doi.org\/10.1017\/CBO9780511902680"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.plrev.2008.03.002"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/1940354"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-020-00182-2"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.87.483"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","location":"Virtual Event Italy","acronym":"PODC '21","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467921","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467921","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":45,"alternative-id":["10.1145\/3465084.3467921","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467921","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}