  Coordination in a large number of networked robots is a challenging task,
especially when robots are constantly moving around the environment and there
are malicious attacks within the network. Various approaches in the literature
exist for detecting malicious robots, such as message sampling or suspicious
behavior analysis. However, these approaches require every robot to sample
every other robot in the network, leading to a slow detection process that
degrades team performance. This paper introduces a method that significantly
decreases the detection time for legitimate robots to identify malicious robots
in a scenario where legitimate robots are randomly moving around the
environment. Our method leverages the concept of ``Dynamic Crowd Vetting" by
utilizing observations from random encounters and trusted neighboring robots'
opinions to quickly improve the accuracy of detecting malicious robots. The key
intuition is that as long as each legitimate robot accurately estimates the
legitimacy of at least some fixed subset of the team, the second-hand
information they receive from trusted neighbors is enough to correct any
misclassifications and provide accurate trust estimations of the rest of the
team. We show that the size of this fixed subset can be characterized as a
function of fundamental graph and random walk properties. Furthermore, we
formally show that as the number of robots in the team increases the detection
time remains constant. We develop a closed form expression for the critical
number of time-steps required for our algorithm to successfully identify the
true legitimacy of each robot to within a specified failure probability. Our
theoretical results are validated through simulations demonstrating significant
reductions in detection time when compared to previous works that do not
leverage trusted neighbor information.
