Blin et al. (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. Unknown means that the searchers are provided no a priori information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin et al. is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any n-node graph in a monotone way, it is necessary and sufficient to provide Θ(n log n) bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any unknown graph in a decentralized manner. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be connected, i.e., the clear part of the graph must remain permanently connected, and monotone, i.e., the clear part of the graph only grows. The search number mcs(G) of a graph G is the smallest number of searchers necessary to clear G in a monotone connected way in centralized settings. We prove that Θ( n log n ) mcs(G) searchers are necessary and sufficient to clear any unknown n-node graph G in a monotone connected way, in decentralized settings. More precisely, we prove that any distributed protocol aiming at clearing all graphs in the above settings has competitive ratio Θ(n/ log n). That is, we prove that, for any distributed protocol P, there are arbitrarily large n-node graphs G such that P requires at least Ω( n log n ) mcs(G) searchers to clear G. Moreover, we propose a distributed protocol that allows O( n log n ) mcs(G) searchers to clear any unknown asynchronous n-node graph G in a monotone connected way.
If one requires a distributed search strategy to be monotone, then it is known that the competitive ratio (the ratio of the number of searchers it uses in the worst case and the optimal offline number of searchers needed) of such a strategy is ω(n/ log n) REF .
The Cost of Monotonicity in Distributed Graph Searching
OPODIS
Computer Science