{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T04:32:06Z","timestamp":1768451526668,"version":"3.49.0"},"reference-count":30,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["AF-18139940"],"award-info":[{"award-number":["AF-18139940"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:p> We consider the problem of fault-tolerant parallel search on an infinite line by [Formula: see text] robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed [Formula: see text] and can communicate wirelessly among themselves. However, among the [Formula: see text] robots, there are [Formula: see text] robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient evidence that the target has been found. We aim to design algorithms that minimize the value of [Formula: see text], the time to find a target at a (unknown) distance [Formula: see text] from the origin by [Formula: see text] robots among which [Formula: see text] are faulty. We give several different algorithms whose running time depends on the ratio [Formula: see text], the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots. <\/jats:p>","DOI":"10.1142\/s0129054121500209","type":"journal-article","created":{"date-parts":[[2021,1,14]],"date-time":"2021-01-14T01:13:45Z","timestamp":1610586825000},"page":"369-387","source":"Crossref","is-referenced-by-count":8,"title":["Search on a Line by Byzantine Robots"],"prefix":"10.1142","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9026-1217","authenticated-orcid":false,"given":"Jurek","family":"Czyzowicz","sequence":"first","affiliation":[{"name":"D\u00e9pt. d\u2019informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, QC, Canada"}]},{"given":"Konstantinos","family":"Georgiou","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Ryerson University, Toronto, ON, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8959-4428","authenticated-orcid":false,"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, ON, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0941-4010","authenticated-orcid":false,"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, Wesleyan University, Middletown CT, USA"}]},{"given":"Lata","family":"Narayanan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Soft. Engineering, Concordia University, Montreal, QC, Canada"}]},{"given":"Jaroslav","family":"Opatrny","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Soft. Engineering, Concordia University, Montreal, QC, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4336-5336","authenticated-orcid":false,"given":"Sunil","family":"Shende","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rutgers University, Camden, NJ, USA"}]}],"member":"219","published-online":{"date-parts":[[2021,1,13]]},"reference":[{"key":"S0129054121500209BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/050645221"},{"key":"S0129054121500209BIB002","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732428X"},{"key":"S0129054121500209BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0067-x"},{"key":"S0129054121500209BIB004","volume-title":"The Theory of Search Games and Rendezvous","volume":"55","author":"Alpern S.","year":"2002"},{"key":"S0129054121500209BIB005","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1054"},{"key":"S0129054121500209BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759737"},{"key":"S0129054121500209BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760028"},{"key":"S0129054121500209BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761156"},{"key":"S0129054121500209BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/BF02798690"},{"key":"S0129054121500209BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/BF02762672"},{"key":"S0129054121500209BIB012","doi-asserted-by":"publisher","DOI":"10.1137\/1005070"},{"key":"S0129054121500209BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30139-6_12"},{"key":"S0129054121500209BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_18"},{"key":"S0129054121500209BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22450-8_27"},{"key":"S0129054121500209BIB016","first-page":"164","volume-title":"International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)","author":"Chrobak Marek","year":"2015"},{"key":"S0129054121500209BIB017","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446475"},{"key":"S0129054121500209BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48971-0_30"},{"key":"S0129054121500209BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933102"},{"key":"S0129054121500209BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.018"},{"key":"S0129054121500209BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185382"},{"key":"S0129054121500209BIB022","doi-asserted-by":"publisher","DOI":"10.1145\/2629656"},{"key":"S0129054121500209BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.040"},{"key":"S0129054121500209BIB024","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799348670"},{"key":"S0129054121500209BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2491-2_5"},{"key":"S0129054121500209BIB026","first-page":"8","volume-title":"SODA","author":"Kleinberg J.","year":"1994"},{"key":"S0129054121500209BIB027","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806760"},{"key":"S0129054121500209BIB028","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212745"},{"key":"S0129054121500209BIB029","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"S0129054121500209BIB030","volume-title":"Distributed Algorithms","author":"Lynch N. A.","year":"1996"},{"key":"S0129054121500209BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035787"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121500209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T06:11:11Z","timestamp":1624428671000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121500209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,13]]},"references-count":30,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["10.1142\/S0129054121500209"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121500209","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,13]]}}}