Distributed chasing of network intruders

Abstract. This paper addresses the graph searching problem in a dis-tributed setting. We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentral-ized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves without knowing the topology of the network in advance. It performs in an asyn-chronous environment, i.e., it implements the necessary synchronization mechanism in a decentralized manner. In every network, our protocol performs a connected strategy using at most k + 1 searchers, where k is the minimum number of searchers required to clear the network in a monotone connected way, computed in the centralized and synchronous setting.