Back to Search
Start Over
The cost of monotonicity in distributed graph searching
- Source :
- Proceedings of the 11th International Conference On Principles Of Distributed Systems, OPODIS 2007, OPODIS 2007, Dec 2007, Pointe à Pitre, Guadeloupe, France. pp.415-428, ⟨10.1007/978-3-540-77096-1_30⟩, Distributed Computing, Distributed Computing, Springer Verlag, 2009, 22 (2), pp.117-127. ⟨10.1007/s00446-009-0089-1⟩, Lecture Notes in Computer Science ISBN: 9783540770954, OPODIS, Distributed Computing, 2009, 22 (2), pp.117-127. ⟨10.1007/s00446-009-0089-1⟩
- Publication Year :
- 2009
- Publisher :
- Springer Science and Business Media LLC, 2009.
-
Abstract
- International audience; Blin {\it et al.} (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it 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 {\it 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 $\Theta(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 graph in a decentralized manner, when the searchers have no a priori information about the graph. 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 {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it 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 any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has {\it competitive ratio} $\Theta(\frac{n}{\log n})$. That is, we prove that, for any distributed protocol $\cal P$, there exists a constant $c$ such that for any sufficiently large $n$, there exists a $n$-node graph $G$ such that $\cal P$ requires at least $c\frac{n}{\log n}\, \mcs(G)$ searchers to clear $G$. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n})\, \mcs(G)$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way.
- Subjects :
- Monotonicity
Mathematical optimization
Theoretical computer science
Computer Networks and Communications
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
050801 communication & media studies
0102 computer and information sciences
02 engineering and technology
Strength of a graph
Biconnected graph
01 natural sciences
Theoretical Computer Science
law.invention
0508 media and communications
Graph power
law
Line graph
0202 electrical engineering, electronic engineering, information engineering
Graph property
Complement graph
Graph searching
Distance-hereditary graph
Mobile agent
Discrete mathematics
020203 distributed computing
05 social sciences
Voltage graph
Directed graph
Butterfly graph
Competitive ratio
Graph bandwidth
Computational Theory and Mathematics
010201 computation theory & mathematics
Hardware and Architecture
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Null graph
Graph factorization
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- ISBN :
- 978-3-540-77095-4
- ISSN :
- 14320452 and 01782770
- ISBNs :
- 9783540770954
- Volume :
- 22
- Database :
- OpenAIRE
- Journal :
- Distributed Computing
- Accession number :
- edsair.doi.dedup.....02bad6efb96aeb0fbf6dcedf97eef95a