Search on a Line by Byzantine Robots

Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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 wirelessly 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 evidence 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 (unknown) 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.

Original languageEnglish (US)
Pages (from-to)369-387
Number of pages19
JournalInternational Journal of Foundations of Computer Science
Volume32
Issue number4
DOIs
StatePublished - Jun 2021

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Keywords

  • Cow path problem
  • byzantine faults
  • mobile robots
  • parallel search
  • wireless communication

Fingerprint

Dive into the research topics of 'Search on a Line by Byzantine Robots'. Together they form a unique fingerprint.

Cite this