×
Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav

Parallel Bayesian search with no coordination. (English) Zbl 1427.68359

J. ACM 66, No. 3, Article No. 17, 28 p. (2019).

Cited in 4 Documents

MSC:

68W20 Randomized algorithms
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W10 Parallel algorithms in computer science
68W15 Distributed algorithms

Keywords:

Bayesian search; distributed computing; fault tolerance; parallel computing; randomized algorithms; treasure hunt
Cite Review PDF
Full Text: DOI HAL

References:

[1] Noga Alon, Chen Avin, Michal Koucky, Gady Kozma, Zvi Lotker, and Mark R. Tuttle. 2008. Many random walks are faster than one. In Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA’08). ACM, New York, 119-128. · Zbl 1223.05284
[2] Steve Alpern, Robbert Fokkink, Leszek Gasieniec, Roy Lindelauf, and V. S. Subrahmanian. 2013. Search Theory: A Game Theoretic Perspective. Springer. · Zbl 1263.91001
[3] Steve Alpern and Shmuel Gal. 2003. The theory of search games and rendezvous. International Series in Operations Research 8 Management Science. Springer. · Zbl 1034.91017
[4] R. A. Baezayates, J. C. Culberson, and G. J. E. Rawlins. 1993. Searching in the plane. Information and Computation 106, 2 (Oct. 1993), 234-252. · Zbl 0781.68044
[5] A. Beck. 1964. On the linear search problem. Israel Journal of Math 2, 4 (1964), 221-228. · Zbl 0168.39502
[6] David Blackwell. 1962. Notes on dynamic programming. Unpublished notes, University of California, Berkeley.
[7] Lihi Cohen, Yuval Emek, Oren Louidor, and Jara Uitto. 2017. Exploring an infinite space with finite memory scouts. In Proceedings of the T28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17). 207-224. · Zbl 1411.68078
[8] Colin Cooper, Alan M. Frieze, and Tomasz Radzik. 2009. Multiple random walks in random regular graphs. SIAM Journal on Discrete Mathematics 23, 4 (2009), 1738-1761. · Zbl 1207.05179
[9] Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, and Jaroslav Opatrny. 2016. Search on a line with faulty robots. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC’16). ACM, New York, 405-414. · Zbl 1375.68187
[10] 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. · Zbl 1394.68033
[11] Assaf David and Zamir Shmuel. 1985. Optimal sequential search: A Bayesian approach. The Annals of Statistics 13, 3 (1985), 1213-1221. · Zbl 0589.90045
[12] Klim Efremenko and Omer Reingold. 2009. How well do random walks parallelize? In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Irit Dinur, Klaus Jansen, Joseph Naor, and José Rolim (Eds.). Springer, Berlin, 476-489. · Zbl 1255.05180
[13] Robert Elsässer and Thomas Sauerwald. 2011. Tight bounds for the cover time of multiple random walks. Theoretical. Computer Science 412, 24 (2011), 2623-2641. · Zbl 1227.68030
[14] Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. 2014. Solving the ANTS problem with asynchronous finite state machines. In Proceedings of Automata, Languages, and Programming - 41st International Colloquium (ICALP’14), Part II. 471-482. · Zbl 1411.68158
[15] Ofer Feinerman and Amos Korman. 2012. Memory lower bounds for randomized collaborative search and implications for biology. In Proceedings of the 26th International Symposium on Distributed Computing (DISC’12). 61-75. · Zbl 1321.68415
[16] Ofer Feinerman, Amos Korman, Zvi Lotker, and Jean-Sébastien Sereni. 2012. Collaborative search on the plane without communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’12). 77-86. · Zbl 1301.68230
[17] Helmut Finner. 1992. A generalization of holder’s inequality and some probability inequalities. The Annals of Probability 20, 4 (Oct. 1992), 1893-1901. · Zbl 0761.60013
[18] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2012. Distributed computing by oblivious mobile robots. Morgan 8 Claypool Publishers. · Zbl 1286.68484
[19] Pierre Fraigniaud, Amos Korman, and Yoav Rodeh. 2016. Parallel exhaustive search without coordination. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC’16). 312-323. · Zbl 1373.68202
[20] Ming-Yang Kao, John H. Reif, and Stephen R. Tate. 1993. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’93). Society for Industrial and Applied Mathematics, Philadelphia, PA, 441-447. http://dl.acm.org/citation.cfm?id=313559.313848. · Zbl 0801.68039
[21] Amos Korman and Yoav Rodeh. 2017. Parallel search without coordination. In Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO’17). · Zbl 1496.68379
[22] Christoph Lenzen, Nancy A. Lynch, Calvin C. Newport, and Tsvetomira Radeva. 2014. Trade-offs between selection complexity and performance when searching the plane without communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC’14). 252-261. · Zbl 1321.68480
[23] M. C. Chew, Jr. 1967. A sequential search procedure. The Annals of Mathematical Statistics 38, 2 (1967), 494-502. · Zbl 0168.17106
[24] University of California Berkeley. 2017. BOINC. https://boinc.berkeley.edu/.
[25] 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’13), Revised Selected Papers (2013), 6-21.
[26] Lawrence Stone, D. 2001. Theory of Optimal Search (2nd ed.). Topics in Operations Research Series.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.