Synchronization helps robots to detect black holes in directed graphs

Krzysztof Kosowski; Alfredo Navarra; Cristina Pinotti

doi:10.1007/978-3-642-10877-8_9

Synchronization helps robots to detect black holes in directed graphs

Abstract

Praca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano również, że liczba potrzebnych agentów dla grafów skierowanych jest uzależniona od istnienia bądź braku synchroniczności modelu.

Citations

8

CrossRef
0

Web of Science
1 3

Scopus

Authors (3)

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Monographic publication
Type:: rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
Title of issue:: Principles of distributed systems strony 86 - 98
Language:: English
Publication year:: 2009
Bibliographic description:: Kosowski K., Navarra A., Pinotti C.: Synchronization helps robots to detect black holes in directed graphs// Principles of distributed systems/ ed. eds. Tarek F. Abdelzaher, Michel Raynal, Nicola Santoro. Berlin Heidelberg: Springer, 2009, s.86-98
DOI:: Digital Object Identifier (open in new tab) 10.1007/978-3-642-10877-8_9
Verified by:: Gdańsk University of Technology