Skip to main content
Top

2009 | OriginalPaper | Chapter

Synchronization Helps Robots to Detect Black Holes in Directed Graphs

Authors : Adrian Kosowski, Alfredo Navarra, Cristina M. Pinotti

Published in: Principles of Distributed Systems

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

The paper considers a team of robots which has to explore a graph

G

where some nodes can be harmful. Robots are initially located at the so called

home base

node. The dangerous nodes are the so called

black hole

nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore

G

in such a way that the minimum number of robots is wasted. The exploration ends if there is at least one surviving robot which knows all the edges leading to the black holes. As many variations of the problem have been considered so far, the solution and its measure heavily depend on the initial knowledge and the capabilities of the robots. In this paper, we assume that

G

is a directed graph, the robots are associated with unique identifiers, they know the number of nodes

n

of

G

(or at least an upper bound on

n

), and they know the number of edges Δ leading to the black holes. Each node is associated with a white board where robots can read and write information in a mutual exclusive way.

A recently posed question [Czyzowicz et al.,

Proc. SIROCCO’09

] is whether some number of robots, expressed as a function of parameter Δ only, is sufficient to detect black holes in directed graphs of arbitrarily large order

n

. We give a positive answer to this question for the synchronous case, i.e., when the robots share a common clock, showing that

O

(Δ·2

Δ

) robots are sufficient to solve the problem. This bound is nearly tight, since it is known that at least 2

Δ

robots are required for some instances. Quite surprisingly, we also show that unlike in the case of undirected graphs, for the directed version of the problem, synchronization can sometimes make a difference: for Δ= 1, 2 robots are always sufficient and sometimes required to explore the graph regardless of whether synchronization is present; however, for Δ= 2, in the synchronous case 4 robots are always sufficient, whereas in the asynchronous case at least 5 robots are sometimes required.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
Synchronization Helps Robots to Detect Black Holes in Directed Graphs
Authors
Adrian Kosowski
Alfredo Navarra
Cristina M. Pinotti
Copyright Year
2009
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-10877-8_9

Premium Partner