Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
| hal.structure.identifier | Distributed Computing Research Group [Ottawa] | |
| dc.contributor.author | FLOCCHINI, Paola | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | ILCINKAS, David | |
| hal.structure.identifier | School of Computer Science [Ottawa] | |
| dc.contributor.author | SANTORO, Nicola | |
| dc.contributor.editor | Gadi Taubenfeld | |
| dc.date.accessioned | 2024-04-15T09:53:40Z | |
| dc.date.available | 2024-04-15T09:53:40Z | |
| dc.date.issued | 2008-09 | |
| dc.date.conference | 2008-09 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198621 | |
| dc.description.abstractEn | We prove that, for the black hole search problem, the pure token model is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of {\em two} asynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node) can locate the black hole in an arbitrary network of known topology; this can be done with $\Theta(n \log n)$ moves, where $n$ is the number of nodes, even when the links are not FIFO. | |
| dc.description.sponsorship | Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322 | |
| dc.language.iso | en | |
| dc.publisher | Springer Berlin / Heidelberg | |
| dc.source.title | Proceedings of the 22nd International Symposium on Distributed Computing | |
| dc.subject.en | distributed computing | |
| dc.subject.en | graph exploration | |
| dc.subject.en | mobile agents | |
| dc.subject.en | autonomous robots | |
| dc.subject.en | dangerous graphs | |
| dc.title.en | Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/978-3-540-87779-0_16 | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| bordeaux.page | 227-241 | |
| bordeaux.volume | 5218 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | DISC 2008 | |
| bordeaux.country | FR | |
| bordeaux.title.proceeding | Proceedings of the 22nd International Symposium on Distributed Computing | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00341523 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00341523v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2022nd%20International%20Symposium%20on%20Distributed%20Computing&rft.date=2008-09&rft.volume=5218&rft.spage=227-241&rft.epage=227-241&rft.au=FLOCCHINI,%20Paola&ILCINKAS,%20David&SANTORO,%20Nicola&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||