{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:53Z","timestamp":1759638713834,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["648032"],"award-info":[{"award-number":["648032"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            Coordinating the actions of agents (e.g., volunteers analyzing radio signals in SETI@home) yields efficient\n            <jats:italic>search<\/jats:italic>\n            algorithms. However, such an efficiency is often at the cost of implementing complex coordination mechanisms which may be expensive in terms of communication and\/or computation overheads. Instead,\n            <jats:italic>non-coordinating<\/jats:italic>\n            algorithms, in which each agent operates independently from the others, are typically very simple, and easy to implement. They are also inherently robust to slight misbehaviors, or even crashes of agents. In this article, we investigate the \u201cprice of non-coordinating,\u201d in terms of search performance, and we show that this price is actually quite small. Specifically, we consider a parallel version of a classical\n            <jats:italic>Bayesian<\/jats:italic>\n            search problem, where set of\n            <jats:italic>k<\/jats:italic>\n            \u22651 searchers are looking for a treasure placed in one of the boxes indexed by positive integers, according to some distribution\u00a0\n            <jats:italic>p<\/jats:italic>\n            . Each searcher can open a random box at each step, and the objective is to find the treasure in a minimum number of steps. We show that there is a very simple non-coordinating algorithm which has expected running time at most 4(1\u22121\/\n            <jats:italic>k<\/jats:italic>\n            +1)\n            <jats:sup>2<\/jats:sup>\n            OPT+10, where OPT is the expected running time of the best fully coordinated algorithm. Our algorithm does not even use the precise description of the distribution\n            <jats:italic>p<\/jats:italic>\n            , but only the relative likelihood of the boxes. We prove that, under this restriction, our algorithm has the best possible competitive ratio with respect to OPT. For the case where a complete description of the distribution\n            <jats:italic>p<\/jats:italic>\n            is given to the search algorithm, we describe an optimal non-coordinating algorithm for Bayesian search. This latter algorithm can be twice as fast as our former algorithm in practical scenarios such as uniform distributions. All these results provide a complete characterization of non-coordinating Bayesian search. The take-away message is that, for their simplicity and robustness, non-coordinating algorithms are viable alternatives to complex coordinating mechanisms subject to significant overheads. Most of these results apply as well to\n            <jats:italic>linear<\/jats:italic>\n            search, in which the indices of the boxes reflect their relative importance, and where important boxes must be visited first.\n          <\/jats:p>","DOI":"10.1145\/3304111","type":"journal-article","created":{"date-parts":[[2019,4,8]],"date-time":"2019-04-08T13:37:23Z","timestamp":1554730643000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Parallel Bayesian Search with No Coordination"],"prefix":"10.1145","volume":"66","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[{"name":"CNRS and University Paris Diderot, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8652-9228","authenticated-orcid":false,"given":"Amos","family":"Korman","sequence":"additional","affiliation":[{"name":"CNRS and University Paris Diderot, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7224-6451","authenticated-orcid":false,"given":"Yoav","family":"Rodeh","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378557"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2500910"},{"key":"e_1_2_1_3_1","series-title":"International Series in Operations Research 8 Management Science","volume-title":"The theory of search games and rendezvous","author":"Alpern Steve","unstructured":"Steve Alpern and Shmuel Gal . 2003. The theory of search games and rendezvous . International Series in Operations Research 8 Management Science . Springer . Steve Alpern and Shmuel Gal. 2003. The theory of search games and rendezvous. International Series in Operations Research 8 Management Science. Springer."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1054"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759737"},{"volume-title":"Notes on dynamic programming. Unpublished notes","author":"Blackwell David","key":"e_1_2_1_6_1","unstructured":"David Blackwell . 1962. Notes on dynamic programming. Unpublished notes , University of California , Berkeley. David Blackwell. 1962. Notes on dynamic programming. Unpublished notes, University of California, Berkeley."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039700"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958171.1958176"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933102"},{"key":"e_1_2_1_10_1","volume-title":"No. 109","author":"Das Shantanu","year":"2013","unstructured":"Shantanu Das . 2013. Mobile agents in distributed computing: Network exploration. Bulletin of the European Association for Theoretical Computer Science (EATCS) , No. 109 ( 2013 ), 54--69. Shantanu Das. 2013. Mobile agents in distributed computing: Network exploration. Bulletin of the European Association for Theoretical Computer Science (EATCS), No. 109 (2013), 54--69."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349665"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_36"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.010"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_40"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332444"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989534"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2423886"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897541"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313848"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72050-0_12"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611463"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698965"},{"key":"e_1_2_1_24_1","unstructured":"University of California Berkeley. 2017. BOINC. https:\/\/boinc.berkeley.edu\/.  University of California Berkeley. 2017. BOINC. https:\/\/boinc.berkeley.edu\/."},{"key":"e_1_2_1_25_1","volume-title":"Algorithms for Sensor Systems - Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS\u201913)","author":"Prencipe Giuseppe","year":"2013","unstructured":"Giuseppe Prencipe . 2013 . Autonomous mobile robots: A distributed computing perspective . In Algorithms for Sensor Systems - Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS\u201913) , Revised Selected Papers (2013), 6--21. Giuseppe Prencipe. 2013. Autonomous mobile robots: A distributed computing perspective. In Algorithms for Sensor Systems - Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS\u201913), Revised Selected Papers (2013), 6--21."},{"key":"e_1_2_1_26_1","volume-title":"Theory of Optimal Search","author":"Stone Lawrence","unstructured":"Lawrence Stone , D. 2001. Theory of Optimal Search ( 2 nd ed.). Topics in Operations Research Series . Lawrence Stone, D. 2001. Theory of Optimal Search (2nd ed.). Topics in Operations Research Series.","edition":"2"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3304111","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3304111","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:19Z","timestamp":1750208539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3304111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,5]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3304111"],"URL":"https:\/\/doi.org\/10.1145\/3304111","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2019,4,5]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}