TY - GEN
T1 - Search on a line by byzantine robots
AU - Czyzowicz, Jurek
AU - Georgiou, Konstantinos
AU - Kranakis, Evangelos
AU - Krizanc, Danny
AU - Narayanan, Lata
AU - Opatrny, Jaroslav
AU - Shende, Sunil
N1 - Publisher Copyright: © Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende.
PY - 2016/12/1
Y1 - 2016/12/1
N2 - We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f 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 verification that the target has been found. We aim to design algorithms that minimize the value of Sd (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.
AB - We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f 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 verification that the target has been found. We aim to design algorithms that minimize the value of Sd (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.
KW - Byzantine faults
KW - Cow path problem
KW - Mobile robots
KW - Parallel search
KW - Wireless communication
UR - http://www.scopus.com/inward/record.url?scp=85010767461&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85010767461&partnerID=8YFLogxK
U2 - https://doi.org/10.4230/LIPIcs.ISAAC.2016.27
DO - https://doi.org/10.4230/LIPIcs.ISAAC.2016.27
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 27.1-27.12
BT - 27th International Symposium on Algorithms and Computation, ISAAC 2016
A2 - Hong, Seok-Hee
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 27th International Symposium on Algorithms and Computation, ISAAC 2016
Y2 - 12 December 2016 through 14 December 2016
ER -